ldenenbe@bbncc5.UUCP (Larry Denenberg) (01/01/86)
Since the best solution I've been able to obtain is possibly about to be
bettered, it's time to post it while it's still a contender. I'm about
to show how to guarantee a triple match on the Mass Lottery in 100 tickets.
First I want to introduce some notation to standardize the discussion.
Define
L(n:a,y,m) = the minimum number of tickets necessary to guarantee that
you will have an m-way match, when there are n numbers in the lottery,
the authorities pick a numbers, and you pick y numbers on each ticket.
For example, we're looking for L(36:6,6,3), and we've already established
that L(36:6,6,2) is 9.
Another way to look at it: you have a block of *n* numbers in which *a*
numbers are special, you get to buy tickets with *y* numbers each, and you
want a ticket that captures at least *m* of the special numbers. L(n:a,y,m)
is by definition the minimum number of tickets that guarantees it.
Suppose that you break the 36 numbers into two blocks of 18 each. Since
the authorities pick 6 numbers, one or the other of the blocks must contain
at least 3 numbers. So if we handle the two blocks separately, *recalling
that there may be only three numbers in a block*, we guarantee a match.
This reasoning shows that
L(36:6,6,3) <= 2 * L(18:3,6,3)
and leads to a 168-ticket solution. Notice the <= sign here; such a breakup
never guarantees that you've found the *best* solution, only a *correct*
solution. In other words, any such breakup gives only upper bounds.
Now let's generalize the L notation. To motivate, look at the solution
given by spitzer@faust, who reasons as follows: break the 36 numbers into
blocks of 6, 14, and 16 and handle them separately, assuming that one block
has 3 special numbers in it. That assumption can fail only where each
block has exactly two numbers in it. To handle that situation it suffices
to cover all cases where the first block has 2 numbers and the second block
has 1 number. I propose writing this analysis as follows:
L(36:6,6,3) <= L(6:3,6,3) + L(14:3,6,3) + L(16:3,6,3) + L(6:2,14:1,6,3)
Get it? L(6:2,14:1,6,3) says that I've got a block of 6 with two special
numbers in it, and a disjoint block of 14 with one special number in it,
and I want to match 3 numbers using tickets with 6 numbers on them.
Spitzer continues as follows: to find a bound on L(6:2,14:1,6,3) I'll buy
tickets where 4 numbers come from the block of 6 and the other 2 numbers
come from the block of 14. Covering all pairs in the block of 6 using 4
numbers at a time takes 3 (partial) tickets, and covering all numbers in
the block of 14 using 2 numbers at a time takes 7 (partial) tickets. By
buying full tickets in all combinations, I achieve the goal using 21
tickets. We write this as:
L(6:2,14:1,6,3) <= L(6:2,4,2) * L(14:1,2,1) = 3*7 = 21.
By now some of the rules for writing L's in terms of other L's should be
obvious; but mechanical manipulation is no substitute for careful thought
(of course). Can anyone think of better notation?
My solution starts off like that of ado@elsie, who points out that
L(36:6,6,3) <= 3*L(12:3,6,3) + L(12:2,12:2,6,3)
(that is, use three equal blocks of 12 instead of the 6-14-16 of spitzer).
He gets L(12:3,6,3) <= 20 without proof, but it's obviously based on
L(12:3,6,3) <= 2*L(6:3,6,3) + 2*L(6:2,6:1,6,3)
with L(6:2,6:1,6,3) <= L(6:2,4,2)*L(6:1,2,1) = 3*3.
I use the same initial breakup, but instead I show that L(12:3,6,3) is at
most 17 (which immediately saves 9 tickets over ado). How do I do it? Just
fiddling around! I sat down one day and tried a basically greedy approach
(try to find tickets that cover as many uncovered triplets as possible), then
fixed it up at the end. Probably a computer could do better. Anyway, let
the twelve numbers be 0,1,2,3,4,5,6,7,8,9,a,b (single digits are much easier
to work with). Then the following seventeen tickets cover all triplets:
013459, 456789, 0189ab, 2367ab, 012678, 23489a, 0456ab, 13579b, 14789a,
03689b, 02458b, 02357a, 12569a, 02479b, 13568a, 12346b, 3478bx.
Verify it yourself. By the way, notice the "x" in the last ticket---I didn't
need this spot at all, and any digit can be filled in there. (It's trivial
to show that L(12:3,6,3) is at least 13, by the way.)
We have now purchased 51 tickets, and have to contend with the case that each
of the three blocks of twelve has exactly two special numbers. As I wrote
above, we abandon the third block and concentrate on solving L(12:2,12:2,6,3).
We break this up as follows (still with ado@elsie, it turns out): the first
block either has both numbers in the first 6, or it has at least one number
in the second six. That is,
L(12:2,12:2,6,3) <= L(6:2,12:2,6,3) + L(6:1,12:2,6,3).
The second term is covered by buying tickets with two numbers in the first
block and four numbers in the second block:
L(6:1,12:2,6,3) <= L(6:1,2,1) * L(12:2,4,2).
The first factor here is obviously 3 and ado presents a further breakdown
of the second term that does it in 15 tickets (for a total of 45).
Now I hope ado@elsie doesn't think it's too sleazy, but I saved 6 more
by fiddling around until I solved L(12:2,4,2) in 13 tickets, to wit:
016b, 0238, 039a, 058b, 1237, 148a, 1579, 249b, 3456, 37ab, 6789, 256a, 047x.
Again, the last ticket doesn't need all its numbers. Thus we use only
13*3 = 39 tickets. (Trivial lower bound: L(12:2,4,2) is at least 12.)
Finally, we need to solve L(6:2,12:2,6,3) and I now have some reasoning of
my own. I break it down as follows: either the second block has a number
among its first 8, or it has two numbers in the last four, that is:
L(6:2,12:2,6,3) <= L(6:2,8:1,6,3) + L(6:2,4:2,6,3)
the first term is at most L(6:2,4,2)*L(8:1,2,1) = 3*4 = 12, and the second
is bounded by L(6:1,2,1)*L(4:2,4,2) = 3*1 = 3. So we use another 15 tickets.
Grand total: 51 + 39 + 15 = 105 tickets. But wait! What about 100??
Well, there are indeed a few more to be saved, but it gets a little delicate
from here on in. Let's summarize the work so far (using real ranges instead
of this abstract L bullshit):
1. Cover all triplets in 1-12: 17 tickets
2. Cover all triplets in 13-24: 17 tickets
3. Cover all triplets in 25-36: 17 tickets
4. Cover all numbers in 7-12 and all pairs in 13-24: 3*13 = 39 tickets
5. Cover all pairs in 1-6 and all numbers in 13-20: 3*4 = 12 tickets
6. Cover all numbers in 1-6 and all of 21-24: 3*1 = 3 tickets
-------------
Grand total 105 tickets
It's now obvious how to squeeze a few more out. In line 4 we buy three
sets of 13 tickets covering all the pairs from 13-24; in so doing, we cover
a lot of triplets too, maybe making some of the tickets in line 2 unnecessary.
Moreover, in line 5 we buy three sets of tickets that cover all pairs from
1-6, and maybe make some of the tickets in line 1 unnecessary. I'm going to
show how to save one ticket in line 1 and three tickets in line 2, then (by
other even sneakier means) I'll show how to save a ticket in line 6.
Recall that ticket with a blank spot, 3478bx? Well, it turns out that
if you drop it from the seventeen tickets solving L(12:3,6,3) you've only
missed the triplets 347, 378, and 78b. So drop the corresponding ticket
in line 1, and cover those three triplets by buying line 5 carefully.
There can't be any difficulty; we buy three *independent* sets of four
tickets and we only need to cover one triplet in each set. (By independent
sets I mean that the bijection between {0,1,2,3,4,5,6,7,8,9,a,b} and
{13,14,15,16,17,18,19,20,21,22,23,24} doesn't have to be the same each time.)
I'm going to spare you the details of saving three tickets in line 2. Just
drop the tickets corresponding to 3478bx, 013459, and 2367ab; you'll find
that you have 16 uncovered triplets. To cover them, you get to buy three
independent sets of 13 tickets, each with 4 numbers. The first way I tried
worked---with the first set I covered 8 of them with a little thinking and
I captured 7 more with the second set.
Now, the last lap! Line 6 above consists of the following three tickets:
1,2,21,22,23,24 3,4,21,22,23,24 5,6,21,22,23,24
It's supposed to be solving L(6:2,4:2,6,3). Suppose we drop the last of
these tickets; what can go wrong? There's only one case where we can fail:
when 5 and 6 are be selected by the authorities along with two of 21,22,23,24;
we're OK in any other case. What we're going to do is capture these cases
on line 4. Remember that ticket 047x in the solution to L(12:2,4,2)? The
x can be anything, right? Well, we simply make it a 5 always. [That is to
say, absolute 5, not the 5 of the 0-9ab "abstract" range.] We'll also
arrange that in the blocks of 13 on line 4 the set {0,4,7} maps into {21..24}
in such a way that every pair of the latter set is covered (recall that the
mapping can change from block to block). Now since [absolute] 5 is always
chosen by the authorities in the cases we're worried about, and we've got
three tickets containing 5 and every pair in {21,22,23,24}, we've covered
all the cases---ticket 5,6,21,22,23,24 can be dropped.
Just a minute (I hear you cry)! You've now lost the ability to choose the
mappings of the three blocks independently! Doesn't that screw up the
argument of the paragraph before last, where you were trying to cover all
those triplets with the same 39 tickets? Well, yes, but you don't lose as
much as you think, since you can still map everything but {0,4,7} anywhere
you like (and even these three aren't too badly constrained). It's still
no problem to cover it all. As I said; the first thing I tried worked fine.
I hope these last few paragraphs are clear. The details of the messing
around are easily reconstructed by anyone interested. Indeed, I've only
gone part of the way; possibly another ticket could be saved from line 2
with more work. But it's getting to be too much for me. I didn't
spend this much time on my Ph.D. thesis.
By the way, spitzer's 108 ticket solution can easily be improved to 105.
Just replace
L(6:2,14:2,6,3) <= L(6:2,14:1,6,3) <= L(6:2,4,2)*L(14:1,2,1) = 3*7
with
L(6:2,14:2,6,3) <= L(6:2,10:1,6,3) + L(6:2,4:2,6,3)
<= L(6:2,4,2)*L(10:1,2,1) + L(6:1,2,1)*L(4:2,4,2)
<= 3 * 5 + 3 * 1
= 15
Maybe the easiest way to crack 100 is to find better bounds on L(14:2,6,3)
or L(16:2,6,3) or both. It wouldn't take much. It would also suffice to
get L(15:2,6,3) below 40 and use a 6-15-15 breakdown.
Anybody read all this?
/Larry Denenberg
larry@{bbn-unix,harvard}