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$
  • 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$ – Gerry Myerson Dec 9 '19 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 '19 at 12:28
  • 6
    $\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 '19 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$ – Rob Pratt Dec 9 '19 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$ – ablmf Dec 9 '19 at 20:37
5
$\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$
6
$\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$
  • 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 '19 at 0:10
  • 1
    $\begingroup$ Upps... Thanks @joriki $\endgroup$ – Dr. Mathva Dec 15 '19 at 10:56
  • $\begingroup$ This is a much neater construction than mine and with a tighter bound. Nice! $\endgroup$ – mhum Dec 16 '19 at 22:15
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$
  • $\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$ – Yong Hao Ng Dec 18 '19 at 7:08
  • 1
    $\begingroup$ Yes, the Schonheim lower bound is in the papers. $\endgroup$ – Rob Pratt Dec 18 '19 at 15:42
1
+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 $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) $3$ of $6$ numbers correctly AND

3) pick $(6-3)$ from the remaining $42$ non-correct numbers (This avoids the options of getting 4 or more numbers correct). This is a total of $$\binom{7}{6}\times \binom{6}{3}\times\binom{42}{3}=1607200.$$

For 1) I'm not 100% sure on if the logic matches the math. What I am trying to get is to pick 6 of the 7 numbers so that 3 can be right and 3 be wrong in step 2). Regardless, using the values I have, the probability of him getting 3 right (for $n=1$ ticket) for a third is therefore $$P=\dfrac{1607200}{85900000}=0.01871$$

Each new ticket increases his chances. Now we could complicate this and ask if his tickets have unique number choices from other tickets etc etc... but I am gonna assume that each new ticket adds to his probability of winning. Using the binomial formula $$\binom{n}{1}P(1-P)^{n-1}=\text{Probability of winning a third}$$.

For a $50$% chance I get $n=26$ tickets (rounded)

For a $90$% chance I get $n=47$ tickets (rounded)

For a $99$% chance I get $n=51.92$ tickets

For a $99.99$% chance I get $n=52.44$ tickets

So I am certain, $52$ tickets will win Paul a third.

$\endgroup$
  • 2
    $\begingroup$ Theorem 2.6 here implies a lower bound of 57, so 52 tickets are not enough. $\endgroup$ – Rob Pratt Dec 18 '19 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$ – Ken Dec 25 '19 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$ – Rob Pratt Dec 25 '19 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.