16
$\begingroup$

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.

$\endgroup$
6
  • 5
    $\begingroup$ You want the smallest collection of 6-element sets intersecting every 7-element set in (at least) a 3-element set. This is a problem in combinatorial designs and I don't think it's easy. $\endgroup$ Dec 9, 2019 at 11:50
  • 1
    $\begingroup$ Maybe one line of reasoning could be to reason only about one ticket and calculate the probability of that being the winning one. Then, create an inequality, multiplying n (a variable) by the found probability and solve for n * P >= 1. Not sure this is minimal, but should be a solution to the problem (I reasoned through this very quickly, so I might be wrong! :)) $\endgroup$
    – as-cii
    Dec 9, 2019 at 12:28
  • 7
    $\begingroup$ This is known as 'Lottery Wheeling' among aficionados. The unusual lottery described (a player picks 6 numbers but 7 are drawn) means there probably isn't any existing work on these specific parameters. 163 tickets will guarantee a 3-match for a lottery where the player picks 6 numbers and 6 are drawn (follow link above), so that's definitely more than enough if 7 are going to be drawn. $\endgroup$
    – AakashM
    Dec 9, 2019 at 14:29
  • 7
    $\begingroup$ In the lotto design notation, you are looking for $L(49,6,7,3)$. This paper gives an overview, including some bounds and constructions, but focuses on 2-matches. This paper has some lower bounds. $\endgroup$
    – RobPratt
    Dec 9, 2019 at 18:20
  • 1
    $\begingroup$ Is this feasible to solve with an SMT sovler? I suppose we need one binary variable for each $6$-subsets? $\endgroup$ Dec 9, 2019 at 20:37

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ +1, nice construction! But the last sentence isn't right -- the six-element sets contain a triple from every winning set, but they don't contain every triple of $G$. $\endgroup$
    – joriki
    Dec 15, 2019 at 0:10
  • 1
    $\begingroup$ Upps... Thanks @joriki $\endgroup$
    – Dr. Mathva
    Dec 15, 2019 at 10:56
  • $\begingroup$ This is a much neater construction than mine and with a tighter bound. Nice! $\endgroup$
    – mhum
    Dec 16, 2019 at 22:15
4
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ That's nice. Is there an explanation for the lower bound? (In particular is it the same one given by the earlier papers?) $\endgroup$ Dec 18, 2019 at 7:08
  • 1
    $\begingroup$ Yes, the Schonheim lower bound is in the papers. $\endgroup$
    – RobPratt
    Dec 18, 2019 at 15:42
0
+50
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Theorem 2.6 here implies a lower bound of 57, so 52 tickets are not enough. $\endgroup$
    – RobPratt
    Dec 18, 2019 at 15:40
  • $\begingroup$ @RobPratt but a 16 year old in a math olympiad isn't going to be aware of this theorem. I approached the problem in a way a student might think. Starting from a simple lottery example and then building onto that. $\endgroup$
    – Kendall
    Dec 25, 2019 at 14:43
  • $\begingroup$ Right, the theorem provides a lower bound, and the question asks for a good upper bound. My point was just that the upper bound you claimed cannot be correct because it is less than a known lower bound. Maybe there is some way to repair your answer to get a correct upper bound. $\endgroup$
    – RobPratt
    Dec 25, 2019 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .