Winning the LotteryDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/