spitzer@faust.UUCP (12/13/85)
>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.
ado@elsie.UUCP (Arthur David Olson) (12/17/85)
Here's a 150-ticket solution. If there are at least three winning numbers between 1 and 12, then at least one of these twenty tickets has at least three winning numbers: 1 2 3 4 5 6 | 1 2 3 4 7 8 | 1 2 3 4 9 10 | 1 2 3 4 11 12 1 2 5 6 7 8 | 1 2 5 6 9 10 | 1 2 5 6 11 12 | 1 2 7 8 9 10 1 2 7 8 11 12 | 1 2 9 10 11 12 | 3 4 5 6 7 8 | 3 4 5 6 9 10 3 4 5 6 11 12 | 3 4 7 8 9 10 | 3 4 7 8 11 12 | 3 4 9 10 11 12 5 6 7 8 9 10 | 5 6 7 8 11 12 | 5 6 9 10 11 12 | 7 8 9 10 11 12 If there are at least three winning numbers between 13 and 24, then at least one of these twenty tickets has at least three winning numbers: 13 14 15 16 17 18 | 13 14 15 16 19 20 | 13 14 15 16 21 22 | 13 14 15 16 23 24 13 14 17 18 19 20 | 13 14 17 18 21 22 | 13 14 17 18 23 24 | 13 14 19 20 21 22 13 14 19 20 23 24 | 13 14 21 22 23 24 | 15 16 17 18 19 20 | 15 16 17 18 21 22 15 16 17 18 23 24 | 15 16 19 20 21 22 | 15 16 19 20 23 24 | 15 16 21 22 23 24 17 18 19 20 21 22 | 17 18 19 20 23 24 | 17 18 21 22 23 24 | 19 20 21 22 23 24 If there are at least three winning numbers between 25 and 36, then at least one of these twenty tickets has at least three winning numbers: 25 26 27 28 29 30 | 25 26 27 28 31 32 | 25 26 27 28 33 34 | 25 26 27 28 35 36 25 26 29 30 31 32 | 25 26 29 30 33 34 | 25 26 29 30 35 36 | 25 26 31 32 33 34 25 26 31 32 35 36 | 25 26 33 34 35 36 | 27 28 29 30 31 32 | 27 28 29 30 33 34 27 28 29 30 35 36 | 27 28 31 32 33 34 | 27 28 31 32 35 36 | 27 28 33 34 35 36 29 30 31 32 33 34 | 29 30 31 32 35 36 | 29 30 33 34 35 36 | 31 32 33 34 35 36 If there aren't any winners in the above tickets, then there are exactly two winning numbers between 1 and 12, exactly two winning numbers between 13 and 24, and exactly two winning numbers between 25 and 36. Here, we'll rely on the fact that there are two winning numbers between 1 and 12 and at least one winning number between 13 and 24; this being so, then at least one of these ninety tickets has three (or four) winning numbers: 1 2 3 4 13 14 | 1 2 3 4 15 16 | 1 2 3 4 17 18 | 1 2 3 4 19 20 1 2 3 4 21 22 | 1 2 3 4 23 24 | 1 2 5 6 13 14 | 1 2 5 6 15 16 1 2 5 6 17 18 | 1 2 5 6 19 20 | 1 2 5 6 21 22 | 1 2 5 6 23 24 1 2 7 8 13 14 | 1 2 7 8 15 16 | 1 2 7 8 17 18 | 1 2 7 8 19 20 1 2 7 8 21 22 | 1 2 7 8 23 24 | 1 2 9 10 13 14 | 1 2 9 10 15 16 1 2 9 10 17 18 | 1 2 9 10 19 20 | 1 2 9 10 21 22 | 1 2 9 10 23 24 1 2 11 12 13 14 | 1 2 11 12 15 16 | 1 2 11 12 17 18 | 1 2 11 12 19 20 1 2 11 12 21 22 | 1 2 11 12 23 24 | 3 4 5 6 13 14 | 3 4 5 6 15 16 3 4 5 6 17 18 | 3 4 5 6 19 20 | 3 4 5 6 21 22 | 3 4 5 6 23 24 3 4 7 8 13 14 | 3 4 7 8 15 16 | 3 4 7 8 17 18 | 3 4 7 8 19 20 3 4 7 8 21 22 | 3 4 7 8 23 24 | 3 4 9 10 13 14 | 3 4 9 10 15 16 3 4 9 10 17 18 | 3 4 9 10 19 20 | 3 4 9 10 21 22 | 3 4 9 10 23 24 3 4 11 12 13 14 | 3 4 11 12 15 16 | 3 4 11 12 17 18 | 3 4 11 12 19 20 3 4 11 12 21 22 | 3 4 11 12 23 24 | 5 6 7 8 13 14 | 5 6 7 8 15 16 5 6 7 8 17 18 | 5 6 7 8 19 20 | 5 6 7 8 21 22 | 5 6 7 8 23 24 5 6 9 10 13 14 | 5 6 9 10 15 16 | 5 6 9 10 17 18 | 5 6 9 10 19 20 5 6 9 10 21 22 | 5 6 9 10 23 24 | 5 6 11 12 13 14 | 5 6 11 12 15 16 5 6 11 12 17 18 | 5 6 11 12 19 20 | 5 6 11 12 21 22 | 5 6 11 12 23 24 7 8 9 10 13 14 | 7 8 9 10 15 16 | 7 8 9 10 17 18 | 7 8 9 10 19 20 7 8 9 10 21 22 | 7 8 9 10 23 24 | 7 8 11 12 13 14 | 7 8 11 12 15 16 7 8 11 12 17 18 | 7 8 11 12 19 20 | 7 8 11 12 21 22 | 7 8 11 12 23 24 9 10 11 12 13 14 | 9 10 11 12 15 16 | 9 10 11 12 17 18 | 9 10 11 12 19 20 9 10 11 12 21 22 | 9 10 11 12 23 24 -- UUCP: ..decvax!seismo!elsie!ado ARPA: elsie!ado@seismo.ARPA DEC, VAX and Elsie are Digital Equipment and Borden trademarks