Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site harvard.UUCP Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!qantel!lll-crg!seismo!harvard!greg From: greg@harvard.UUCP (Greg) Newsgroups: net.puzzle Subject: Re: Winning 1/3 of the Lottery (*better partial spoiler*) Message-ID: <532@harvard.UUCP> Date: Mon, 25-Nov-85 15:06:28 EST Article-I.D.: harvard.532 Posted: Mon Nov 25 15:06:28 1985 Date-Received: Thu, 28-Nov-85 08:12:28 EST References: <25@bbncc5.UUCP> Reply-To: greg@harvard.UUCP (Greg) Organization: Harvard Lines: 64 Summary: I can do it in 10 tickets, and 7 tickets is not enough. 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? Here is one way of doing it in ten tickets: Let the first ticket have the numbers 1 through 6, the second 7 through 12, the third 13 through 18, and so on up to the sixth ticket. Now suppose the winning ticket does not have two numbers in common with any of these. Clearly, the winning ticket must have one number between 1 and 6 and one number between 7 and 12. Now let the seventh ticket have the numbers 1,2,3,7,8,9, and give the eighth ticket the numbers 4,5,6,10,11,12. If the winning ticket does not have two numbers in common with these last two tickets either, then there are two possibilities: there is a winning number between 1 and 3 and a winning number between 10 and 12, or there is a winning number between 4 and 6 and a winning number between 7 and 9. So make the eleventh tickets have the numbers 1,2,3,10,11,12, and the last ticket the numbers 4,5,6,7,8,9. The winning ticket, if it has dodged the first ten of your tickets, has two have two numbers in common with one of these. Now I shall show that for any seven tickets, there is a winning that does not have two numbers in common with any of the seven. I consider several cases: Case I. There are at least five numbers that none of the seven tickets contain. Let the winning ticket contain five numbers not found on any of the seven, plus any other number. Clearly it has at most one number in common with any of the seven. Case II. There are between four and two numbers that are not found on the seven tickets. Let the winning ticket contain two numbers that are not found at all. Given that there are only 42 entries on the seven tickets, at least 22 of the numbers between 1 and 36 appear only once among the tickets. At least four of the tickets, then, must have at least one number that does not appear on other tickets. For the remaining four numbers of the winning entry, pick one number (that does not appear elsewhere) on each of these four tickets that has such numbers. Case III. Only one number is not found among the seven tickets. Let the winning ticket contain this number. In this case, there are at least 28 numbers that only appear on one ticket. These numbers must be shared by at least five tickets. Pick one number on each of these five (pick numbers that only appear once, that is) for the remaining five numbers of the winning ticket. Case IV. All of the numbers are found on the seven tickets. In this final case, there are at least 30 numbers that are only found once. If there are more than 30, then the numbers that only appear once are shared among six tickets; let the winning ticket contain one of the numbers from each of these six tickets. If there are 30 such numbers and they happened to be found on six different tickets, the same strategy still works. The only pos- sibility is that there are 30 numbers that are only found once, and these 30 numbers are found on five different tickets. Note that if this is so, there isn't any room on the five tickets for numbers that appear twice. Moreover, the other two tickets are necessarily the same and contain the other six numbers. So let the winning ticket have number from each of the five tickets that contain unique numbers, and one number from one of the last two tickets. Q.E.D. -- gregregreg