How many tickets should Paul buy? 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.
 A: 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.
A: 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.
A: 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:

*

*$6$ of $7$ numbers AND


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