12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Via integer linear programming, the minimum turns out to be rot13(gjragl avar). $\endgroup$
    – RobPratt
    Jul 28 at 18:51
  • $\begingroup$ Thanks for accepting my answer. Did you have a particular 33-ticket solution in mind? $\endgroup$
    – RobPratt
    Jul 29 at 12:39
  • $\begingroup$ @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. $\endgroup$ Jul 29 at 12:44
  • 1
    $\begingroup$ Because of this HNQ, I became aware that Lufthansa workers were striking. See, covert advertising does work! $\endgroup$
    – user253751
    Jul 29 at 17:21

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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.. $\endgroup$
    – Bass
    Jul 28 at 23:26
  • $\begingroup$ @Bass thanks. Indeed, exactly one ticket (see my rot13 comment). $\endgroup$
    – RobPratt
    Jul 29 at 0:18
  • $\begingroup$ 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? $\endgroup$ Jul 29 at 18:48
  • 2
    $\begingroup$ @MichaelKarcher You can choose your own numbers. For example, many people like to pick numbers based on birthdays of family members. $\endgroup$
    – RobPratt
    Jul 29 at 18:57
  • $\begingroup$ 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. $\endgroup$ Jul 29 at 19:08

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.