How many tickets should Paul buy?

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.


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


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.

Tags:

Combinatorics

Probability

Contest Math

Recent Posts