Winning the Lottery

Date: 07/22/2009 at 18:06:57
From: Spud
Subject: Math Problem

My question is due to a gambling scheme they have at my local pub
which I am curious about.  The setup is as follows - 

You must choose 5 numbers from 1-40 and match 3 randomly picked (just 
like the lottery with less numbers and much better chance).

I was wondering how many different combinations of 5 numbers are 
there in 40 and how many different combinations would it take to 
cover every possible outcome of numbers emerging?

Thanks - Spud.

Date: 07/26/2009 at 09:45:02
From: Doctor Vogler
Subject: Re: Math Problem

Hi Spud,

Thanks for writing to Doctor Math.  There are

  40*39*38*37*36/(1*2*3*4*5) = 658,008

combinations of 5 numbers out of 40, so that is the number of
different guesses that are available to be guessed.  But each guess of
five numbers matches

  5*4*3/(1*2*3) = 10

different picks of three numbers.

There are

  40*39*38/(1*2*3) = 9880

combinations of 3 numbers out of 40, so that is the number of
different possible random picks of three (I'll call them answers)
there are.  If each one is equally likely, then any particular guess
of five numbers (which matches 10 answers) has one chance in 988 of
matching the correct answer.

But that's not *quite* the question you asked.  Certainly you would
need to make at least 988 guesses in order to be able to cover every
possible answer.  But is there a way to construct 988 guesses so that
they cover every possible answer exactly once, with no repeats?

It turns out that the answer is no.  Here's one way to prove it. 
Suppose you have a list of guesses that covers every possible answer.
How many guesses contain the number 1?  Well, out of the 9880
possible answers, 741 of them contain a 1, and your guesses must cover
these 741 answers.  But each guess that contains a 1 only covers 6
possible answers that contain a 1, so that means that you need at
least 741/6 guesses that contain a 1.  Well, 741/6 is not an integer;
it is between 123 and 124.  So you need at least 124 guesses that
contain a 1.

In fact, there must be at least 124 guesses that contain the number x
for every x between 1 and 40.  This doesn't mean that you need
124*40=4960 guesses, because each guess contains 5 numbers, so you
would be counting each guess 5 times.  Therefore, it means that you
need at least 124*40/5=992 guesses.  That's only 4 more than our first
try, but can we solve the problem with only 992 guesses?

It turns out that the answer is no.  We can use an argument similar to
the one above to get a larger minimum.  Suppose you have a list of
guesses that covers every possible answer.  How many guesses contain
the numbers 1 and 2?  Well, out of the 9880 possible answers, 38 of
them contain a 1 and a 2, and your guesses must cover these 38
answers.  But each guess that contains a 1 and a 2 only covers 3
possible answers that contain a 1 and a 2, so that means that you need
at least 38/3 guesses that contain a 1 and a 2.  Since 38/3 is bigger
than 12, that means that you need at least 13 guesses that contain a 1
and a 2.  In fact, there must be at least 13 guesses that contain the
numbers x and y for every pair of two different integers between 1 and
40.  There are 40*39/2 = 780 such pairs, and each guess contains 10
such pairs.  So that means that you need at least 13*780/10 = 1014
guesses.

But can we solve the problem with only 1014 guesses?  It turns out
that the answer is no.  If it were true, then for every pair of
numbers, there would be exactly one third number such that those three
appear twice.  So, for example, given the pair 1 and 2, there is some
other number (say 3) such that 1,2,3 appear in two different guesses.
 But then, given the pair 1 and 3, the other number must be 2, because
we already know that 1,2,3 appear in two different guesses.  In this
sense, the 39 numbers other than 1 are paired up, but you can't pair
up an odd number of numbers.  So you can't do 1014 guesses.

Well, all this negativity might lead one to ask what you *can* do?  It
seems reasonable that you shouldn't have to use *too* many more
guesses than 1014.  Well, I'm not quite sure what the minimum number
of guesses is, but I had my computer use a kind of "greedy" algorithm
to try to find a fairly small set of guesses that covers all 9880
possible answers, and it found a set of 1211 guesses that did.  So you
don't need more than 1211 guesses, and the minimum number of guesses
needed is somewhere between 1015 and 1211.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/