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

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

1 Answer 1

Reset to default
15
$\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.

Improve this answer
$\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
    Commented Jul 28, 2022 at 23:26
  • $\begingroup$ @Bass thanks. Indeed, exactly one ticket (see my rot13 comment). $\endgroup$
    – RobPratt
    Commented Jul 29, 2022 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$
    – Michael Karcher
    Commented Jul 29, 2022 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
    Commented Jul 29, 2022 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$
    – Michael Karcher
    Commented Jul 29, 2022 at 19:08

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