ldenenbe@bbncc5.UUCP (Larry Denenberg) (11/19/85)
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! (There may be many winners, since other players may have chosen the same set of six numbers. You split the Big Bucks equally.) There are lesser prizes for matching five, four, and three 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?
greg@harvard.UUCP (Greg) (11/20/85)
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. 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? Well, if you're incredibly unlucky, you may end up buying every single ticket which has only one number in common with the winning ticket, and also every single ticket which has no numbers in common with the winning ticket. The question remains, how many such tickets are there? Let A1, A2, ..., A6 be the winning ticket. On a given unlucky ticket, there are 35 possibilities (anything other than A1) for the first number, 35 possibilities for the second number (anything other than A2), and so on. This gives us 35^6 unlucky combinations so far. But in addition, there are the combinations which have one number in common with the winning ticket. In that case, there are 6*35^5 possibilities, because there are six positions for the matching numbers and 35^5 combinations for the nonmatching numbers. Thus, if you want to be sure of matching two numbers with the winning ticket, you must buy 41 * 35^5 + 1 tickets. -- gregregreg
akhanna@bbncc5.UUCP (Atul Khanna) (11/21/85)
In article <516@harvard.UUCP> greg@harvard.UUCP (Greg) writes: >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. 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? > >Well, if you're incredibly unlucky, you may end up buying every single >ticket which has only one number in common with the winning ticket, and also >every single ticket which has no numbers in common with the winning ticket. >The question remains, how many such tickets are there? > >Let A1, A2, ..., A6 be the winning ticket. On a given unlucky ticket, there >are 35 possibilities (anything other than A1) for the first number, 35 >possibilities for the second number (anything other than A2), and so on. >This gives us 35^6 unlucky combinations so far. But in addition, there are >the combinations which have one number in common with the winning ticket. >In that case, there are 6*35^5 possibilities, because there are six positions >for the matching numbers and 35^5 combinations for the nonmatching numbers. > >Thus, if you want to be sure of matching two numbers with the winning ticket, >you must buy 41 * 35^5 + 1 tickets. >-- Not quite - the problem states that the 6 numbers are distinct, i.e. order does not matter. That makes the problem more interesting. -- Atul C Khanna BBN Communications Corporation, Cambridge MA
ldenenbe@bbncc5.UUCP (Larry Denenberg) (11/22/85)
In article <516@harvard.UUCP> greg@harvard.UUCP (Greg) writes: >In article <25@bbncc5.UUCP> larry@bbncc5.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. 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? > >Well, if you're incredibly unlucky, you may end up buying every single >ticket which has only one number in common with the winning ticket, and also >every single ticket which has no numbers in common with the winning ticket. >The question remains, how many such tickets are there? >. . . Let me be more clear. 1) Each lottery ticket contains a *set* of six numbers. That is, order is not significant AND the six numbers are distinct. 2) You're trying to be *clever*, not lucky. You want a ticket that matches two or more numbers, but you want to buy as few tickets as possible. For example, suppose that I had asked you to guarantee that you would match *one* or more numbers. Then the answer is six: you just have to cover all of the numbers, and you can do this with six tickets. (In fact you would have to cover only 31 of the numbers, but you still need six tickets.) Don't forget that you get to choose which numbers are on your ticket. Stated precisely, the puzzle is this: Let a *ticket* be a subset of {1,2,...,36} with cardinality six. What is the minimum cardinality of a set T of tickets with the property that for *every* ticket t there exists a ticket in T whose intersection with t has cardinality two or more?
greg@harvard.UUCP (Greg) (11/24/85)
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. 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? Well, I can give a crummy lower bound and pretty good upper bound. The lower bound is six tickets, because if you take five tickets, there are at least six numbers which you haven't chosen, and the winning ticket might be those six numbers. The pretty good upper bound is as follows: Arrange the numbers from one to 36 on a 6 x 6 chessboard (in an order you wish). Now write down each column on the first six tickets, and each row on the next six tickets. So far we have twelve tickets. Clearly, there are 6! = 720 tickets that do not have two numbers in common with these: For the winning ticket, you may pick any number out of the first column, any other number out of the second, any besides the first two for the third, and so on. The winning ticket may not have two numbers in the same row or column. Now for the remaining six tickets do the following: For ticket 1, write the second row of the first column and the first row of the other columns; for ticket 2, the third row of the first column and the second row of the other columns; and so on. For the last ticket, pick the first row of the first column and the last row of the other columns. We know that the winning ticket has to intersect with one of these last six if it doesn't intersect with one of the first twelve. Why? Well, the winning ticket must have some number in the first column, say the one on row n. It must also have some number on row n+1 mod 6, and that number cannot be in the first column of the sqaure. Therefore the winning ticket intersects twice with the ticket which has the number of row n, column 1, and all the numbers on row n+1 mod 6, columns i>1. I don't know if it can be done in 17 tickets, but my guess is yes, because the last six tickets were used poorly. -- gregregreg
greg@harvard.UUCP (Greg) (11/25/85)
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
dsr@uvacs.UUCP (Dana S. Richards) (11/26/85)
> 1) Each lottery ticket contains a *set* of six numbers. That is, order > is not significant AND the six numbers are distinct. > > 2) You're trying to be *clever*, not lucky. You want a ticket that > matches two or more numbers, but you want to buy as few tickets as > possible. For example, suppose that I had asked you to guarantee > that you would match *one* or more numbers. Then the answer is six: > you just have to cover all of the numbers, and you can do this with > six tickets. (In fact you would have to cover only 31 of the numbers, > but you still need six tickets.) Don't forget that you get to choose > which numbers are on your ticket. > > Stated precisely, the puzzle is this: Let a *ticket* be a subset of > {1,2,...,36} with cardinality six. What is the minimum cardinality > of a set T of tickets with the property that for *every* ticket t there > exists a ticket in T whose intersection with t has cardinality two or more? This is hard it seems. I looked at the presumably simpler problem of minimizing T given that you much intersect a randomly chosen pair; recall a random ticket gives rise to C(6,2)=15 such pairs. IF we used {1,...,49} and cardinality 7 then we can be optimal; i.e. use T=C(49,2)/C(7,2)=56 tickets. The idea (and I have not been careful and relied on memory) is to use a complete set of 6 mutually orthogonal order 7 latin squares with the 2 trivial order 7 designs (i.e. constant rows and columns). However this approach does not work for the cardinality 6 case since such designs do not exist. Since the simpler problem is messier for 6 I would be surprised if the original problem had an elegant solution.
steve@anasazi.UUCP (Steve Villee) (11/26/85)
> 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! (There may be many winners, since other players may have > chosen the same set of six numbers. You split the Big Bucks equally.) > There are lesser prizes for matching five, four, and three 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? The following tickets will do it, although there may be a smaller set. #1: 1, 2, 3, 4, 5, 6 #2: 1, 2, 3, 7, 8, 9 #3: 1, 2, 3, 10, 11, 12 #4: 1, 2, 3, 13, 14, 15 . . #10: 1, 2, 3, 31, 32, 33 #11: 1, 2, 3, 34, 35, 36 #12: 4, 5, 6, 7, 8, 9 #13: 4, 5, 6, 10, 11, 12 . . #20: 4, 5, 6, 31, 32, 33 #21: 4, 5, 6, 34, 35, 36 #22: 7, 8, 9, 10, 11, 12 #23: 7, 8, 9, 13, 14, 15 . . #64: 28, 29, 30, 31, 32, 33 #65: 28, 29, 30, 34, 35, 36 #66: 31, 32, 33, 34, 35, 36 The number of tickets here is 11+10+9+8+7+6+5+4+3+2+1 = 66. I suspect that the prize for getting just two matching numbers is less than 66 dollars. --- Steve Villee (ihnp4!terak!anasazi!steve) International Anasazi, Inc. 7500 North Dreamy Draw Drive, Suite 120 Phoenix, Arizona 85020 (602) 870-3330
ron@brl-sem.ARPA (Ron Natalie <ron>) (11/27/85)
> > Here is one way of doing it in ten tickets: 1,2,3,4,5,6 7,8,9,10,11,12 13,14,15,16,17,18 19,20,21,22,23,24 25,26,27,28,29,30 31,32,33,34,35,36 1,2,3,7,8,9 4,5,6,10,11,12 1,2,3,10,11,12 4,5,6,7,8,9 (He says ten tickets but he lables them 1,2,3,4,5,6,7,8,11, and 12. How strange).
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (11/27/85)
> (He says ten tickets but he lables them 1,2,3,4,5,6,7,8,11, and 12. > How strange). No stranger than most stuff in netnews. Hey, I thought we were filtering out net.puzzle?
gupta@asgb.UUCP (Yogesh K Gupta) (11/27/85)
Q. What is the minimum number of tickets that one needs to buy, such
that there are at least two matching numbers.
Assumption ASS0: The numbers on a ticket are distinct.
Assumption ASS1: The numbers on the tickets are not ordered (in ascending
or descending order).
Assumption ASS2: The number of matches does not depend on the position of
a number on the list. e.g. for the winning set {A1, A2, A3,
A4, A5, A6} the ticket: B1 B2 A1 B4 A5 B6 has TWO matches.
^^ ^^
Soln:
a. First, the number of tickets that have no match:
30*29*28*27*26*25 = 427518000 (na)
b. The number of tickets that have EXACTLY one match:
(30*29*28*27*26) * (6*6) = 615625920 (nb)
the expression in the first parenthesis is the ways in which
five numbers can be chosen that are not in the winning set,
and the second expression is the number of ways in which a
correct number can be chosen and where it is on the ticket.
.
. . number of tickets you may have to buy before you are sure
of getting at least two correct numbers:
na + nb + 1 = 1043143921
If ASS2 is dropped (but ASS0 and ASS1 hold), then the solution
posted by a previous poster (sorry, I do not remember your name)
is correct (41*35**5).
If only ASS1 is dropped, the problem becomes quite interesting as
certain numbers can not occur in the certain positions. e.g., if
the numbers on a ticket are in ascending order, 32 can never occur
in the first position. Also, if 31 was in the first position, the
rest of the numbers would be determined as well.
--
Yogesh Gupta Advanced Systems Group,
{sdcrdcf, sdcsvax}!bmcg!asgb!gupta Burroughs Corp., Boulder, CO.
--------------------------------------------------------------------
All opinions contained in this message are my own and do not
reflect those of my employer or the plant on my desk.kscott@ucsfcgl.UUCP (Kevin Scott%Kuntz) (11/28/85)
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. 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? I suspect that this question may have arisen due to the once yearly mailing of coupons for free megabucks tickets (don't ask how to get them, they find you) I once got some and was lucky enough to win with them. Now some advice: Buy 4 tickets at a quarter each ( or whatever is the minimum bet), even if you pick the same numbers on each card. The tax people look for large winnings, if you win 500 dollars with a dollar bet they instantly become your friends and hit you up, but if you win 125 dollars four times with your quarter bet they don't take notice of you. Being in California now, I am witnessing a mass hysteria caused by the creation of the California state lottery. I would encourage everyone not to play the lottery, being familiar with computers I imagine we all have enough math to see that it is a bad bet. Still, the math is fun to talk about. Anyone out there know how to 'count' at blackjack? I met a mathematician who gets thrown out of casinos if they recognize him. I've never been there to see him removed from a blackjack table, but I have heard that it is possible to beat blackjack tables where they only use two decks. -- two to the power of five thousand against and falling ...
ldenenbe@bbncc5.UUCP (Larry Denenberg) (12/05/85)
Va negvpyr <25@ooapp5.HHPC> yneel@ooapp5.HHPC (Yneel Qraraoret) jevgrf: >Gur Znffnpuhfrggf Fgngr Zrtnohpxf Ybggrel jbexf yvxr guvf: N gvpxrg pbfgf >$1 naq pbafvfgf bs fvk qvfgvapg ahzoref bs lbhe pubbfvat orgjrra 1 naq 36 >vapyhfvir. Lbh znl ohl nf znal gvpxrgf nf lbh yvxr. Ba Ybggrel Qnl >gur Nhgubevgvrf pubbfr fvk ahzoref. Vs gubfr fvk ner gur fnzr nf lbhe >fvk, lbh jva! >... >Jung vf gur zvavzhz ahzore bs gvpxrgf gung lbh zhfg ohl gb rafher gung >ng yrnfg bar bs lbhe gvpxrgf zngpurf gjb be zber bs gur jvaavat ahzoref? Frireny chmmyvfgf unir fbyirq guvf ceboyrz jvgu gra gvpxrgf, naq bar unf fubja gung ng yrnfg rvtug gvpxrgf ner erdhverq. Va snpg, gur ceboyrz pna or fbyirq jvgu avar gvpxrgf (yrnivat bayl gur dhrfgvba bs rvtug gvpxrgf bcra). V jba'g cbfg zl fbyhgvba lrg, ohg V'yy fraq vg ol znvy gb nalbar jub erdhrfgf vg. Frireny boivbhf trarenyvmngvbaf fhttrfg gurzfryirf. Nal gnxref sbe gur bar va juvpu jr ercynpr "gjb" ol "guerr"? Bar fbyire, jub pnzr hc jvgu fvkgl-fvk gvpxrgf, cbvagf bhg gung gur cevmr sbe zngpuvat gjb ahzoref zhfg gurersber or yrff guna fvkgl-fvk qbyynef. Gur cevmr sbe zngpuvat gjb ahzoref vf mreb. Gur cevmr sbe zngpuvat guerr ahzoref vf nyzbfg mreb (gurl tvir lbh n serr gvpxrg, fb gur gehr cevmr vf gur rkcrpgrq inyhr bs n gvpxrg). Gur cevmr sbe zngpuvat sbhe ahzoref vf sbegl ybhfl ohpxf, naq sbe svir ahzoref lbh trg sbhe uhaqerq ohpxf. Qba'g ubyq lbhe oerngu. Gur chmmyr bjrf vgf bevtva gb n orybirq pbhfva bs zvar jub fcraqf n evqvphybhf senpgvba bs ure vapbzr ba ybggrel gvpxrgf. Fur unf arire jba n cevmr, ohg engure bsgra zngpurf gjb ahzoref. ("Frr, Yneel! V pnzr erny pybfr guvf gvzr!")
greg@harvard.UUCP (Greg) (12/05/85)
Mr. Denenberg has shown me the error of my ways...I thought that ten was the minimum number of tickets, but he says thta the answer is nine tickets. With the knowledge that the answer is nine, an example of a winning strategy is clear. The nine tickets are: #1: 1 2 3 4 5 6 #2: 7 8 9 10 11 12 #3: 13 14 15 16 17 18 #4: 19 20 21 22 23 24 #5: 19 20 21 25 26 27 #6: 22 23 24 25 26 27 #7: 28 29 30 31 32 33 #8: 28 29 30 34 35 36 #9: 31 32 33 34 35 36 Why does this work? Suppose the winning ticket does not have two numbers in common with any of the nine. It can have at most one number between 1 and 6, at most one between 7 and 12, and at most one between 13 and 18. That leaves at least three numbers between 19 and 36. There are two possibilities: At least two numbers are between 19 and 27, or at least two numbers on the winning ticket are between 28 and 36. If the former is true, then there are the following possibilities: The smaller # is between: The larger # is between: They are both in ticket: 19 and 24 19 and 24 #4 19 and 21 25 and 27 #5 22 and 24 25 and 27 #6 25 and 27 25 and 27 #6 If, on the other hand, there are two numbers between 28 and 36, then essentially the same thing happens, except with tickets #7-9 instead of #4-6. Not only that, eight tickets is definitely not enough, but the proof is long and tedious, and at the moment I don't have the stamina to type it up. -- gregregreg