Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: Notesfiles $Revision: 1.6.2.16 $; site faust.UUCP Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!faust!spitzer From: spitzer@faust.UUCP Newsgroups: net.puzzle Subject: Mass Lottery 3 number match Message-ID: <13200001@faust.UUCP> Date: Thu, 12-Dec-85 17:34:00 EST Article-I.D.: faust.13200001 Posted: Thu Dec 12 17:34:00 1985 Date-Received: Mon, 16-Dec-85 05:38:43 EST Lines: 69 Nf-ID: #N:faust:13200001:000:2501 Nf-From: faust!spitzer Dec 12 17:34:00 1985 >Now that the subject of winning 1/3 of the lottery has been nearly settled, >how many tickets do you need to buy to ensure that you will match three >numbers with the winning ticket? For those who missed the first problem, >it was posted by larry@bbn.UUCP (Larry Denenberg): > >>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. If those six are the same as your >>six, you win! >... >>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? Both the 9 and 10 ticket solutions used the same strategy (not explicitly stated): Let B be a block of tickets. B covers an interval in 1..36 if all the numbers in the interval are on at least one ticket in B. Union(B1,B2,..)=1,2,..,36 and Intersection(B1,B2..) = null (as it happens). Choose the number of blocks (5) so that at least 2 winning numbers must be covered by one block. Then construct the tickets in each block so that all possible pairs of numbers covered by the block are on at least one ticket. 10 ticket solution 9 ticket solution B covers B covers B1 1-12 B1' 1-9 B2 13-18 B2' 10-18 --------------B3 19-24----------------- --------------B4 25-30----------------- --------------B5 31-36----------------- One ticket satisfies blocks with only 6 numbers (B2-B5). Both solvers constructed the multiple ticket blocks (B1,B1',B2') by using combinations of triplets to get all pairs (ie 123 456, 123 789). Its easy to see this way that C(4,2) + 1 > C(3,2) + C(3,2). or tickets for B1 + B2 > B1' + B2' Applying the same strategy to the 3 number match gives B1 = 1-18 B2 = 19-36 Using doublets to construct the tickets 12 34 56 12 34 78 12 34 910 ... 12 56 78 12 56 910 ... 1314 1516 1718 Both B1 and B2 contain 84 tickets, C(9,3), for a total of 168. Each block contains all possible 3-way combinations of the numbers they cover, and one or the other must cover at least 3 of the 6 winning numbers. I doubt that this is the minimum, however, since generating 3-way combinations using doublets may not be that efficient and there are probably better strategies using (the equivalent of) intersecting blocks.