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
    Jul 28, 2022 at 18:51
  • $\begingroup$ Thanks for accepting my answer. Did you have a particular 33-ticket solution in mind? $\endgroup$
    – RobPratt
    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
    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$
    – user253751
    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
    Jul 28, 2022 at 23:26
  • $\begingroup$ @Bass thanks. Indeed, exactly one ticket (see my rot13 comment). $\endgroup$
    – RobPratt
    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
    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
    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
    Jul 29, 2022 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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