# The Lufthansa Lottery

In order to pass free time while striking for better pay, some Lufthansa workers organise a lottery where

• each ticket picks three distinct numbers from $$1$$ to $$11$$ inclusive
• the draw picks five distinct numbers from $$1$$ to $$11$$ inclusive
• a ticket wins iff all its numbers were drawn.

Prove without computers that $$33$$ tickets are sufficient to guarantee a win.

• Via integer linear programming, the minimum turns out to be rot13(gjragl avar). Jul 28 at 18:51
• Thanks for accepting my answer. Did you have a particular 33-ticket solution in mind? Jul 29 at 12:39
• @RobPratt My $33$-ticket solution was all cyclic shifts of (1,2,3), (1,4,7) and (1,3,7). I was inspired to write this puzzle by this MSE question. Jul 29 at 12:44
• Because of this HNQ, I became aware that Lufthansa workers were striking. See, covert advertising does work! Jul 29 at 17:21

Here's a simple way to guarantee a win with

30 tickets.

Partition $$\{1,\dots,11\}$$ into $$A=\{1,\dots,6\}$$ and $$B=\{7,\dots,11\}$$. By the pigeonhole principle, every draw of $$5$$ numbers must contain at least $$\lceil5/2\rceil=3$$ numbers in either $$A$$ or $$B$$. So buy

$$\binom{|A|}{3}+\binom{|B|}{3}=\binom{6}{3}+\binom{5}{3} = 20 + 10 = 30$$

tickets.

• This method is quite brilliant! The solution isn't quite symmetrical though, so it stands to reason there might be enough wiggle room to shave off another ticket somehow..
– Bass
Jul 28 at 23:26
• @Bass thanks. Indeed, exactly one ticket (see my rot13 comment). Jul 29 at 0:18
• Is it common in real-world lotteries to be able to buy specific tickets? As I understand it, your solution is to buy all A-only and all B-only tickets, but how would you make sure you don't get any A/B mixed ticket when you just pick 30 tickets from the ticket box? Jul 29 at 18:48
• @MichaelKarcher You can choose your own numbers. For example, many people like to pick numbers based on birthdays of family members. Jul 29 at 18:57
• Thanks for the nudge, I get it now. I was focussed on games like a scratch-card lottery or a raffle where there are pre-printed numbers. Even the german "pick-your-own-numbers" state lottery has at least one side-game that depends on a ticket number you can't influence. Jul 29 at 19:08