kelsey@aoa.UUCP (Kelsey Nickerson) (12/18/85)
In article <25@bbncc5.UUCP> larry@bbn.UUCP (Larry Denenberg) writes: >The Massachusetts State Megabucks Lottery works like this: A ticket costs >$1 and consists of six distinct numbers of your choosing between 1 and 36 >inclusive. You may buy as many tickets as you like. On Lottery Day >the Authorities choose six numbers. ... >What is the minimum number of tickets that you must buy to ensure that >at least one of your tickets matches two or more of the winning numbers? Do to a flakey news feed this past week, I have been unable to determine to what extent this problem has been previously solved. Since the followups that I have seen state that the problem is nearly solved rather than completely solved, I have decided to (once again) try to post my solution. Here is a set of nine tickets that does the job: #1: 1,2,3,4,5,6 #4: 10,11,12,13,14,15 #7: 19,20,21,22,23,24 #2: 4,5,6,7,8,9 #5: 13,14,15,16,17,18 #8: 25,26,27,28,29,30 #3: 1,2,3,7,8,9 #6: 10,11,12,16,17,18 #9: 31,32,33,34,35,36 At most three of the 6 winning numbers can fall between 19-36 else a match exists in tickets 7,8, or 9. So at least 3 of the numbers fall in the range 1-18. Then either at least 2 of the numbers fall in the range of 1-9 or at least 2 of the numbers fall in the range of 10-18. But tickets 1-3 cover all possible pairs of numbers between 1 and 9 and tickets 4-6 cover all possible pairs of numbers between 10 and 18. Q.E.D I will now show that given any 8 tickets, 6 numbers can be found such that at most one of the numbers is represented in any given ticket. Case I. There are at least five numbers not represented in any of the 8 tickets. Choose those five numbers and any other number and we are done. Case II. There are either 3 or 4 numbers not represented in any of the 8 tickets. Choose 3 of those numbers. The 8 tickets contain 48 entries spanning at least 32 different numbers. There can be at most 16 duplicate entries so at least 16 numbers are only represented once. Then at least three of the tickets must contain a number which appears only once. We choose that respective number from each of three tickets, and we now have our required 6 numbers. Case III. There are either 1 or 2 numbers not represented in any of the 8 tickets. Let the first number be one of those. In this case the 8 tickets must span at least 34 different numbers so there are at most 14 duplicate entries and at least 20 numbers which appear only once. We can clearly find four tickets each of which contains a number which does not appear anywhere else. We choose those respective four numbers. Now these 4 tickets span at most 24 different numbers, so there are at least 10 numbers which only appear on the remaining 5 tickets. We choose our 6th number from among those 10. Case IV. All 36 numbers are represented in the 8 tickets. In this case there are at most 12 duplicate entries and at least 24 numbers which appear only once. Suppose we can find 5 tickets among the 8, each of which contains a number which appears only once. We choose those respective five numbers. Again, these five tickets can span at most 30 different numbers. Then there are 6 numbers which are only represented on the remaining 4 tickets and we choose one of these for our 6th number. Now suppose there were less than 5 tickets which contained a number appearing only once. Then the 24 single entries exactly fill 4 of the tickets. We choose a number from each of these tickets. Now the remaining 4 tickets must contain the 12 numbers which were not single entries. Each of these 12 numbers must therefore appear exactly twice on these 4 tickets. Let our fifth number be any of these 12. It appears on two of the four tickets, and there can be at most 10 other numbers also appearing on those two tickets. Thus at least 1 of the 12 numbers only appears on the other 2 tickets. Let that be the 6th number. Q.E.D Kelsey @ Adaptive Optics Associates