ldenenbe@bbncc5.UUCP (Larry Denenberg) (01/03/86)
Remember all those details of my last posting that you didn't wade through?
Well, forget them: Here's a solution in 84 tickets. (I'm assuming that you
recall the notation and a few partial solutions, though.)
I received a letter from chuck@dartvax who claims an upper bound of 48
on L(18:3,6,3). That instantly yields a solution in 96 tickets to the overall
problem, as he points out. (His article never made it here so I have asked
him to repost in case others missed it too. I'm assuming his solution is
correct, sight unseen. Dartmouth people are trustworthy.)
Now let's take the uneven-sized blocks idea of spitzer@faust a little further.
Suppose we break up the universe into blocks of 4, 14, and 18, noting that
L(36:6,6,3) <= L(4:3,6,3) + L(14:3,6,3) + L(18:3,6,3) + L(4:2,14:2,18:2,6,3)
The first term here is obviously 1, and we're using chuck's bound of 48 for
the third term. The final term is easy: seven tickets, each with all four
of the first group and two of the second group, handle it with no sweat. Now
L(14:3,6,3) <= L(12:3,6,3) + L(12:2,4,2) <= 17 + 13
since you just cover all triplets in the first twelve numbers, then cover
all pairs in those numbers using four numbers at a time and put the final
two numbers on each of the last 13 tickets. (The bounds of 17 and 13 come
from my last article.) Grand total 1+17+13+48+7 = 86 tickets.
But the first ticket is clearly unnecessary since you cover all four of
its numbers with each ticket in the group of seven. Moreover, at least
one of the tickets in the group of 17 is unnecessary by the tricks of the
previous posting; one of those 17 is needed for only three triplets, and
these can be covered by the 13 as they do their other work. Thus we're
down to 84 tickets.
The weak spot in this is the bound of 29 for L(14:3,6,3). This business of
breaking up a block and solving pieces separately seems invariably suboptimal;
most of my recent progress rests on the "indecomposable" but economical bounds
for L(12:3,6,3) and L(12:2,4,2) that I got by moving numbers around on paper,
not breaking up blocks. Yet above I broke down a block of 14 into 12 and 2
just because I know good ways of solving blocks of 12! A direct assault
on L(14:3,6,3) would undoubtedly save a few more tickets and get us into
the seventies. Looks like a job for Superhacker.
Concerning lower bounds: greg@harvard points out that at least 23 tickets
are required (since the probability of matching 3 or more with a single
ticket is less than 1 in 23). It's easy to push this to 24 by looking
closely at the unavoidable overlap. Anyone have a stronger argument?
Before anyone jumps on me, I'd like to correct a few errata in my previous
posting. First of all, (5*3)+(1*3) is 18, not 15 [it doesn't affect any
results]. Second of all, my explanation of "independent" is a paragraph too
early; the word means something slightly different where it first appears.
/Larry Denenberg
larry@{bbn-unix,harvard}ldenenbe@bbncc5.UUCP (Larry Denenberg) (01/05/86)
The 84-ticket "solution" of my last posting is, ah, inoperative. It depends
on a bound of 48 for L(18:3,6,3) which has been found to be wrong. Around
7 additional tickets are needed to fix. The details are not of interest
because greg@harvard has found another 84 ticket solution along other
(quite original) lines. His solution will be posted soon.
My sincere apologies to all.
/Larry Denenberg
larry@{bbn-unix,harvard}
A newspaper philosopher says the three most difficult words to pronounce
consecutively are 'I was mistaken.' The philosopher is himself mistaken;
the most difficult are 'I deliberately lied.' These are not only more
difficult than the others, but they are more frequently true.
Ambrose Biercegreg@harvard.UUCP (Greg) (01/05/86)
Here is my best partial answer to the 3-number lottery problem. For those of you who have missed out on the lottery stuff, here is the question: In the Massachussetts State Lottery, you choose six different numbers from one to 36 on each ticket you buy (they cost $1). Three days later the authorities will choose six numbers between 1 and 36. If those six numbers are the same as the six you chose, you win. Order does not matter. How many tickets do you need to buy to guarantee that you match three numbers with the winning ticket? Now for my best solution of 84 tickets: First, divide the numbers into the following groups: Group 1: 1 2 3 4 5 6 7 8 Group 2: 9 10 11 12 13 14 Group 3: 15 16 17 18 19 20 21 22 Group 4: 23 24 25 26 27 28 Group 5: 29 30 31 32 33 34 35 36 Now, the winning ticket has six numbers, so at least one of the following three statements is true: 1. One of the five groups has three winning numbers in it. 2. There is a number N such that group N has two winning numbers in it and group N+1 has at least one winning number in it. 3. Group 5 contains two winning numbers and group 1 contains at least one. In my strategy, if there are two numbers in group 1 and one in group 2, one of the following tickets will contain those three numbers: 1 2 3 4 9 10, 1 3 2 4 11 12, 1 4 2 3 13 14 1 2 5 6 9 10, 1 3 5 7 11 12, 1 4 5 8 13 14 1 2 7 8 9 10, 1 3 6 8 11 12, 1 4 6 7 13 14 3 4 5 6 9 10, 5 7 2 4 11 12, 2 3 5 8 13 14 3 4 7 8 9 10, 5 7 6 8 11 12, 2 3 6 7 13 14 5 6 7 8 9 10, 2 4 6 8 11 12, 5 8 6 7 13 14 Notice also that if there are three numbers in group 1, one of the above 18 tickets will contain those three numbers as well. If, for each number n in the above tickets, we substitute n+14, we get 18 tickets which match any combination of two numbers in group 3 and one in group 4, as well as any set of three numbers in group 3. If we substitute, in the above tickets, 29 for 1, 30 for 2, 31 for 3, 32 for 4, 33 for 5, 34 for 6, 35 for 7, 36 for 8, 1 for 9, 2 for 10, 3 for 11, 4 for 12, 5 for 13, and 6 for 14, and add these tickets: 29 30 31 32 7 8 29 30 33 34 7 8 29 30 35 36 7 8 31 32 33 34 7 8 31 32 35 36 7 8 33 34 35 36 7 8 he 24 tickets that result contain every combination of two numbers in group 5 and one number in group one, as well as every set of three numbers in group 5. Lastly, for covering every combination of two numbers in group 2 and one number in group 3, I choose the following tickets: 9 10 11 12 15 16, 9 10 11 13 17 18, 9 10 11 14 19 20, 9 10 11 12 21 22 9 10 13 14 15 16, 9 10 12 14 17 18, 9 10 12 13 19 20, 9 10 13 14 21 22 11 12 13 14 15 16, 11 13 12 14 17 18, 11 14 12 13 19 20, 11 12 13 14 21 22 Note that these 12 tickets also cover every set of three numbers in group 2. Similarly, by adding 14 to each of the above numbers, one covers the case of two numbers in group 4 and one in group 5, as well as three numbers in group 4. So, the total is 18 + 12 + 18 + 12 + 24 = 84 tickets, or in Larry Denenberg's L(n:a,y,m) notation: L(36:6,6,3) <= L(8:2,4,2)*(2*L(6:1,2,1)+L(8:1,2,1))+2*L(6:2,4,2)*L(8:1,2,1) <= 2*18 + 2*12 + 24 = 84. In this notation, L(n:a,y,m) is the minimum number of tickets necessary to match m numbers with the winning ticket in a lottery game with n numbers, in which the authorities choose a numbers and you choose y numbers on each ticket. -- gregregreg
ldenenbe@bbncc5.UUCP (Larry Denenberg) (01/09/86)
With Chuck (chuck%dartmouth) Simmons' corrected 48-ticket bound on L(18:3,6,3)
and (especially) using Greg (greg@harvard) Kuperberg's new ideas, we can now
give a 75-ticket solution of the overall problem.
The basic breakdown is into two groups of 18:
L(36:6,6,3) <= L(18:3,6,3) + L(18:4,6,3)
since if there aren't 3 special numbers in the first group, there must be at
least 4 in the second group. We now break the second group of 18 into three
groups of 6---call them groups A, B, and C. Think of them arranged in a
circle, so that A follows B follows C follows A. Now either (a) one of the
groups has at least three numbers, or (b) there exists a group with two
numbers followed by a group containing at least one number. (Justification:
if (a) fails, then the four special numbers are divided either 2-2-0, 2-0-2,
0-2-2, 2-1-1, 1-2-1, or 1-1-2.) So we solve L(6:2,6:1,6,3) and use it three
times, on A&B, B&C, and C&A. Now
L(6:2,6:1,6,3) <= L(6:2,4,2)*L(6:1,2,1) = 3*3 = 9
and moreover these tickets can easily be chosen so that all triplets in
the first group of 6 are covered. Grand total 48 + 3*9 = 75 tickets.
Also in the news, Arthur David (ado@elsie) Olson replies to my 13-ticket
bound on L(12:2,4,2) with "No, it's not sleazy---in fact, I can top it!"
Here is his provably optimal, 12-ticket solution on numbers 0-9,a,b:
0123 0456 0789 01ab 1457 1689 248a 259a 267b 349b 358b 367a
The simplest proof of optimality is this: each number must appear on at
least 4 tickets (since each must be paired with 11 other numbers). But that
means 12*4 = 48 spots minimum, precisely the number of spots in 12 tickets.
Similar arguments give lower bounds of 14 and 42 on L(12:3,6,3) and
L(18:3,6,3) respectively.
Chuck Simmons also gives this 15-ticket solution of L(12:3,6,3) (the numbers
here are 1-9,a,b,c, and x means "don't care"):
1234xx 5678xx 9abcxx
12569a 1278bc 13579b 1368ac 14589c 1467ab
3456bc 34789a 2457ac 24689b 2358ab 23679c
Notice that the tickets on the top row only cover four triplets each.
Even so, this will be very hard to beat.
/Larry Denenberg
larry@{bbncc5,harvard}