How many tickets should Paul buy?

Question

An old friend of mine who is now studying mathematics in Germany sent me an exercise from the German Mathematics Olympiads, which was thought for 16-years-old students.

Since I used to participate in MO, my friend asked me to help him with this problem. Notwithstanding, I have the feeling that I am as lost as he is. Here the problem!

In a lottery, you are given tickets with the numbers $1,2,...,49$, of which exactly six must be ticked. In the lotto draw, seven of these 49 numbers are drawn. If at least three of the numbers marked on a lotto ticket belong to the seven numbers drawn, the lottery player has won a "third".

Paul wants to play the lottery and win a third in any case. He fills in $n$ lottery tickets and marks exactly six numbers on each ticket.

Determine the smallest $n$, such that Paul can play in a way that he is guaranteed to have a third on at least one of his lotto tickets.

At first, I evaluated the number $t$ of tripels among the $49$ numbers you can choose: $$t=\binom{49}{3}=18424$$ Out of these $18424$ tripels, $\binom{7}{3}=35$ lead Paul to win.

Now, every set of $6$ numbers -the ones chosen by Paul- contains $s$ different tripels $$s=\binom{6}{3}=20$$

How should I continue? What's the solution?

Thanks in advance and please don't hesitate to edit the question in order to improve language mistakes.

---

Fun fact: The solution did not require to prove that the given $n$ was, in fact, minimal. It sufficed with showing that $n$ allowed Paul to win. Therefore, when it came to grading (max. $7$ points), the jury did not only take the correctness of the proof into consideration, but also how small $n$ was in comparison to the answers given by other competitors.

Answer 1

You can achieve $n=120$ by taking one copy of a $C(17,6,3)$ covering of size 44 and two (shifted) copies of a $C(16,6,3)$ covering of size 38.

Answer 2

I believe I have a solution involving 226 tickets. This is almost certainly not optimal and the construction is rather inelegant, but I do think the reasoning and steps for the construction may have been feasible to obtain within the context of a math competition.

First, some notation.

• For any positive integer $n$, let $[n]$ denote the set $\{1,2,\ldots,n\}$.
• For collections of sets $\mathcal{A}$ and $\mathcal{B}$, let $\mathcal{A} \times \mathcal{B} = \{ A \cup B \;|\; A\in \mathcal{A}, B \in \mathcal{B}\}$
• For a set $X$ and positive integers $m, r, k$, we will call a "$(X,m,r,k)$-design" a collection of sets $\mathcal{S}$ such that: 1) each $S\in \mathcal{S}$ is a subset of $X$ of size $m$, and 2) for each $T \subseteq X$ of size $r$, there exists some $S\in \mathcal{S}$ such that $|S\cup T| \geq k$

Key Observation: By the pigeonhole principle, any subset of integers of size 7 contains 3 elements from the same residue class modulo 3. Hence, for this problem, it would suffice to cover all the triples in each of the 3 residue classes.

So, we've broken down the problem from upper-bounding the size of a $([49], 6, 7, 3)$-design to upper-bounding the size of a $([16], 6, 3, 3)$-design and $([17], 6, 3, 3)$-design, since there are 16 elements in $[49]$ that are 0 mod 3, 16 that are 2 mod 3, and 17 that are 1 mod 3.

---

So, let's get to work constructing a $([16], 6, 3, 3)$-design. We'll build it up in stages.

Step 1: WLOG, let's pick $A_1 = \{1,2,3,4,5,6\}$ to be a part of this design. This will obviously cover the 20 triples contained wholly in $A_1$. Let $\mathcal{A} = \{A_1\}$.

Step 2: Let's now figure out how to cover all the triples that intersect with $A_1$ in exactly 2 elements. We can decompose the problem into two parts: finding a $([6], k, 2, 2)$-design $\mathcal{B_1}$ and another $([16] \setminus [6], 6-k, 1, 1)$-design $\mathcal{B_2}$ (for some positive $k<6$). After a bit of trial and error to find a good $k$, we find that the following works pretty well

• $\mathcal{B_1} = \{ \{1,2,3,4\}, \{3,4,5,6\}, \{1,2,5,6\} \}$
• $\mathcal{B_2} = \{ \{7,8\}, \{9,10\}, \{11,12\}, \{13,14\}, \{15,16\} \}$
• $\mathcal{B} = \mathcal{B_1} \times \mathcal{B_2}$

We observe that $\mathcal{B}$ this will cover every triple in $[16]$ that intersects with $A_1$ in exactly 2 places (as well as a few others, as we'll note in the next step).

Step 3: Now, we need to consider the set of triples that intersect with $A_1$ in exactly 1 place. Again, we use the same framework as in Step 2 to find two designs that we can combine via direct product. As an extra twist, we observe that the subsets in $\mathcal{B}$ already cover those triples where the two elements in $[16] \setminus [6]$ are consecutive, so we don't need to cover those in this stage. After a little more trial and error, we can find the following:

• $\mathcal{C_1} = \{ \{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\} \}$
• $\mathcal{C_2} = \{ \{7,9,11,13,15\}, \{7,10,12,14,16\}, \{8,9,12,14,16\}, \{8,10,11,14,16\}, \{8,10,12,13,16\}, \{8,10,12,14,15\} \}$
• $\mathcal{C} = \mathcal{C_1} \times \mathcal{C_2}$.

Step 4: Now that we've handled all the triples that intersect with $A_1$, let's move on to the ones that do not intersect with $A_1$. So, let's add, arbitrarily the set $D_1 = \{7,8,9,10,11,12\}$ to our design. Let $\mathcal{D} = \{D_1\}$.

Step 5: As before, since $\mathcal{D}$ handles every triple wholly contained in $D_1$, we only need to care about the triples that only partially intersect with or wholly avoid $D_1$. But, since there are only 4 elements now outside of $A_1$ and $D_1$, our task is a lot easier. It turns out, once you handle the case of triples intersecting with $D_1$ in two places, we get all the others for free.

• $\mathcal{E_1} = \{ E \; | E \subset D_1, |E|=2 \} = $ all 2-element subsets of $D_1$
• $\mathcal{E_2} = \{ \{13,14,15,16\} \}$
• $\mathcal{E} = \mathcal{E_1} \times \mathcal{E_2}$.

Wrapping it all up: If we did all of the preceding steps correctly, then we can take our $([16], 6, 3, 3)$-design to be $\mathcal{A} \cup \mathcal{B} \cup \mathcal{C} \cup \mathcal{D} \cup \mathcal{E}$ which has a size of $1 + 3*5 + 6*6 + 1 + {{6}\choose{2}}*1 = 1+15+36+1+15 = 68$.

---

Now, we need to construct a $([17], 6, 3, 3)$-design. While we can simply try to replay the steps we did previously for the $([16], 6, 3, 3)$-design but, as it turns out, it's a little messier and doesn't give quite as tight a result (I think it's mainly because you're leftover with 11 instead 10 elements after fixing your first 6-tuple). Instead, what we can do is take our previous construction of a 68-element $([16], 6, 3, 3)$-design as a given and then augment it with a collection of sets that cover all the triples that contain 17. We observe that we can obtain such a collection by taking a $([16], 5, 2, 2)-$design and crossing it with $\{ \{17\} \}$.

So, let's work out a $([16], 5, 2, 2)$-design. We can again build it up in stages.

Step 1: As before, we'll just WLOG take $\mathcal{F} = \{ \{1,2,3,4,5\} \}$ as part of our design.

Step 2: Now, we'll handle the pairs that intersect with $[5]$ in exactly one element. Things won't pack quite as nicely as before, so we're gonna have more redundancies/inefficiencies.

• $\mathcal{G_1} = \{ \{1,2\}, \{3,4\}, \{1,5\} \}$
• $\mathcal{G_2} = \{ \{6,7,8\}, \{8,9,10\}, \{11,12,13\}, \{14, 15, 16\} \}$
• $\mathcal{G} = \mathcal{G_1} \cup \mathcal{G_2}$.

Step 3: Similar to before, we'll now take $\mathcal{H} = \{ \{6,7,8,9,10\} \}$.

Step 4: And now we'll deal the pairs that intersect with $\{6,7,8,9,10\}$ in exactly one element.

• $\mathcal{I_1} = \{ \{6,7\}, \{8,9\}, \{6, 10\} \}$
• $\mathcal{I_2} = \{ \{11,14,15\}, \{12, 13, 16\}\}$
• $\mathcal{I} = $\mathcal{I_1} \cup \mathcal{I_2}$

Step 5: Finally, we deal with the pairs contained entirely in $\{11,12,13,14,15,16\}$. Note that we don't need to cover any pairs that were already covered by $\mathcal{H_2}$ and $\mathcal{I_2}$ from the previous steps. Hence, it suffices to consider $\mathcal{J} = \{\{11,13,14,15,16\}, \{12,13,14,15,16\}\}$.

Wrapping it all up: We'll construct our $([16], 5, 2, 2)$-design as $\mathcal{F} \cup \mathcal{G} \cup \mathcal{H} \cup \mathcal{I} \cup \mathcal{J}$ which has a size of $1 + 3*4 + 1 + 3*2 + 2 = 1 + 12 +1+ 6 +2 = 22$. So, we conclude that we can upper bound the size of a $([17], 6, 3, 3)$-design by $68+22 = 90$.

---

Conclusion: We obtain an upper bound on a $([49], 6, 7, 3)$-design by using our key observation and taking the sum of the upper bounds of two $([16], 6, 3, 3)$-designs and one $([17], 6, 3, 3)$-design to obtain an overall upper bound of $68 + 68 + 90 = 226$.

Answer 3

I've found a proof for $n=\textbf{196}$. In fact, Paul can guarantee a third with the following strategy.

Observe that if you consider the set $G=\{1, 2, ..., 49 \}$ as the union of three sets $A, B$ and $C$, then the Pigeon Principle tells us that at least three of the winning numbers belong to one of the sets. Hence, if Paul buys a lot of tickets and chooses respectively six numbers belonging only to $A$, only to $B$ or only to $C$, such that every triple of $A$, $B$ and $C$ is marked, then Paul has at least one third. The sets $A, B$ and $C$ don't have to be disjoint.

Let us now prove the following Lemma

Lemma: Let $k\geqslant3$ and denote by $M$ a set of $2k$ elements. You can choose $\displaystyle \binom{k}{3}$ subsets of six elements respectively, such that every three-element-subset of $M$ is contained in these six-elemt-subsets.

Proof: Set $M=\{a_1, a_2,...,a_k, b_1, ..., b_k\}$ and construct $k$ two-element subsets $M_i=\{a_i,b_i\}$ for $i=1,2,...,k$. For each three pairwise disjoint subsets construct their union set. We, thus, obtain $\binom{k}{3}$ six-element union-sets. Since three arbitrary elements of $M$ are distributed in three two-element sets $M_i$ at most, every triple belongs to at least one of the $\binom{k}{3}$ six-elements union-sets.

We apply the lemma to the following sets $A=\{1,2,...,18\}, B=\{19, 20, ..., 34\}$ and $\{35, 36, ...,49\}$. Therefore we obtain $$\binom{9}{3}+\binom{8}{3}+\binom{8}{3}=196$$ six-element sets, which – as shown above – include a triple of every winning set.

Answer 4

I'm going to use probability for this one. The probability of winning the lottery is = $\dfrac{\text{the number of winning lottery numbers}}{\text{the total possible amount of numbers}}$. The total amount of numbers possible is given by $\binom{49}{6}=13983816$. The set of winning lottery numbers is $1$. Therefore the odds of winning are $\dfrac{1}{13983816}$.

Now to your problem. Here $49$ numbers are available and $7$ are chosen for a total of $\binom{49}{7}=85 900000$ total possible number combinations. Now the hard part.

To win a third, Paul needs to pick at least $3$ of $7$ numbers correctly but he gets to pick $6$ numbers on each card. Paul therefore needs to pick:

1. $6$ of $7$ numbers AND

2. At least $3$ of $6$ numbers correctly

Now to get no numbers correct, or 1 number correct or 2 numbers correct is $\binom{7}{6}\left[\binom{42}{6}+\binom{6}{1}\binom{42}{5}+\binom{6}{2}\binom{42}{4}\right]=84201208$ ways.

So the probability of not winning a third is $\frac{84201208}{85900000}=\frac{1503593}{1533939}$

Now, the question asks "Determine the smallest $n$, such that Paul can play in a way that he is guaranteed to have a third on at least one of his lotto tickets." We know the probability to have at least one of something is 1 less the probability of having none of them.

So now we need to solve $Pr=1-\left(\frac{1503593}{1533939}\right)^n$ that will 'guarantee' a third. That is, it is the probability (confidence) for $n$ many tickets.

Using $n=57$ (i.e. the lower bound given by Robpratt) gives $Pr=0.6798$ which we can link to the confidence interval for 1 standard deviation. As $n=58$ lands outside of $0.68268$.

The question now becomes what you consider to be a guarantee of winning. Is $90\%$ a guarantee? $99\%$?

I have done the following for different $n$ values:

$90\% - n = 116$

$99\% - n = 231$

$99.9\% - n = 346$

$99.99\% - n = 461$

Again, this answer is to approach the question the same way a 16 year old in a math Olympiad might approach it. While also trying to correct for the lower bound put forth by Rob.