Conference rusure::math

    You need to purchase 8 different cards to be assured of getting
    at least two matches on one of the cards.
    
    You need to purchase 87 different cards to be assured of getting
    at least three matches on one of the cards.
    
    You need to purchase 1402410240 different cards to be assured of
    winning :-)
    
    The next question is how many cards are needed to get four and five
    matches? (can we beat the system? unfortunately i don't think so.)

    re .1
    
    The number of 6 number combinations from 36 is approx. 1.96 * 10^6
    Since each lottery card holds 5 picks the number of cardrds needed
    is approx .4 * 10 ^ 6.
    
    Perhaps I mis-understood what you were saying about a guaranteed
    win.
    

    re 746.1 & .2
    
    I neglected to divide by the number of permutations of six distinct
    things:  n choose m = n!/(m!(n-m)!)
    
    I had  n!/(n-m)!
    
    The other two numbers (8 & 87) didn't involve that calculation.

re .1
    Could you give examples (or a program) for the 8 and 87 assertions?

I'm not sure I understand the problem, but here's a try with 12 cards:

 1  2  3  4  5  6	 1  2  3  7  8  9	 4  5  6  7  8  9
10 11 12 13 14 15	10 11 12 16 17 18	13 14 15 16 17 18
19 20 21 22 23 24	19 20 21 25 26 27	22 23 24 25 26 27
28 29 30 31 32 33	28 29 30 34 35 36	31 32 33 34 35 36

The idea is that if there are 6 state numbers, and four quarters (1-9, 10-18,
19-27, 28-36), then one quarter must have two or more state numbers.  Use
brute force on each quarter.

Peter, am I attacking the right problem?  Re .1 & .3:  how do you get there
with 8?  There seems to be some slop in my 12 -- maybe one could use fifths
instead of quarters, and/or something cleverer than brute force.

John

Well, .5 can be improved using five parts instead of four.  Just one
more refinement to get to 8.

 1  2  3  4  5  6	 1  2  3  7  8  9	 4  5  6  7  8  9
10 11 12 13 14 15	10 11 12 16 17 18	13 14 15 16 17 18
19 20 21 22 23 24	25 26 27 28 29 30	31 32 33 34 35 36

John    

Let's try enumeration: let 1(2..6)(7..10) mean the cards whose lowest 
number is 1 and includes the range in the parentheses. By doing some judicious
shuffling of 'slack' numbers, I get:

1(2..6)(7..11)(12..16)(17..21)(22..26)(27..31)(32..36)

2(8..12)(13..17)(18..22)(23..27)(28..32)(33..36,7)
3(9..13)(14..18)(19..23)(24..28)(29..33)(34..36,7..8)
4(10..14)(15..19)(20..24)(25..29)(30..34)(35..36,7..9)
5(11..15)(16..20)(21..25)(26..30)(31..35)(36,7..10)
6(7..11)(12..16)(17..21)(22..26)(27..31)(32..36)

7(12..16)(17..21)(22..26)(27..31)(32..35,11)
8(13..17)(18..22)(23..27)(28..32)(33..35,11..12)
9(14..18)(19..23)(24..28)(29..33)(34,..35,11..13)
10(15..19)(20..24)(25..29)(30..34)(35,11..14)
11(16..20)(21..25)(26..30)(31..35)(36,15)

12(18..22)(23..27)(28..32)
13(19..23)(24..28)(29..33)
14(20..24)(25..29)(30..34)
15(21..25)(26..30)(31..35)
16(22..26)(27..31)(32..36)

17(23..27)(28..32)(33..36,31)
18(24..28)(29..33)(34..36,29..30)
19(25..29)(30..34)(35..36,26..28)
20(26..30)(31..35)(36,22..25)
21(27..31)(32..36)

22(28..32)(27,32..35)
23(28..32)
24(29..33)
25(30..34)
26(31..35)

So I get 97 cards as the minimum for two matches.

Maybe there's a more efficient arrangement, but I can't find it yet. I
suspect there's a 96-card arrangement.

Lynn Yarbrough 

    Aha!  Now I see how I mistakenly thought the lower bound was 42.

    There are 36*35/2 possible pairs, and 6*5/2 pairs are 'covered'
    by each card.  Thus, we need at least (36*35/2)/(6*5/2) = 42 cards.

    But this is not quite right (as replies .5 and .6 prove) -- it assumes
    that EVERY pair in the state's card must be present in one of the player's
    cards.  What's wanted is that at least ONE pair be present in one of the
    player's cards.

    Does this drop the theoretical lower bound to 42/6 = 7?

    Also, where's that group of 87 cards?

Someone - probably me - is confused about the statement of the problem. As I 
understand it, you want a set of cards for which it is guaranteed that,
whatever the State's set of six numbers, two of them will turn up on at
least one of your cards. Is that what is meant by

>Now suppose the player wants to ensure that at least *two* of the state's
>numbers will match on at least one of his playing cards.  How many playing
>cards are needed?  

By my calculation, it takes 7 cards to match *if you know that one of the 
numbers is 1*, as in reply .-2. If you don't know what the first number is,
it takes in the neighborhood of 96 cards.

re .9
	Yes, that's what is meant by the problem.

	Your point about seven cards (when one of the state's numbers is 1)
	makes it difficult to believe that seven cards might suffice without
	that guarantee.
	
	I still don't understand the 96-card claim -- see J.Munzer's replies.

In neither of Munzer's replies does {4,10} appear on the same card, for example.
You have to systematically demonstrate for every {a,b} that there exists a card
in your set with both a and b on it.

    Lynn:
    
    What I tried to demonstrate was that for every {a,b,c,d,e,f} there
    exists a card with {a,b} or {a,c} or ... or {e,f} on the card. 

    John

36*35/6*5 = 42 is the minimum number of cards that are needed. It's not
difficult to prove that at least twice that number are involved. 

Start with the seven cards exhausting the pairs that include 1:
1(2..6)(7..11)(12..16)(17..21)(22..26)(27..31)(32..36)
Now take any set of cards that exhaust the possibilities for N <> 1; there must
be at least 7 more cards with 5 numbers <> N per card, so there must be a
duplicate including N between the two sets. But N is arbitrary; thus *every*
pair must be duplicated, thus at least 84 cards are required. 

    Problem A (.0):  9 shown, 8 claimed.
    
    Problem B (cover every pair):  66 is enough. Split 1-36 into twelve
    groups -- 1-3, 4-6, 7-9, ..., 34-36.  Make a card from every pair of
    groups; e.g. one card would be 7,8,9,19,20,21.
    
    Lynn, I can't follow your reasoning well enough to try to find a
    hole in it.  But I think there is one.

    John

    Lynn, if there is even a grain of truth in what you are claiming
    (which I have not devoted enough time to), would you take a look
    at .14 and (a) explain if you are trying to address Problem A or
    Problem B, and (b) exhibit a 6-number "drawing" that is not covered
    by John M's two purported solutions (A in .6, B in .14)?
    
    There being only a finite number of combinations, I believe it is
    perfectly fair to ask you to demonstrate a counterexample.  Even
    a first grader can check out a counterexample, and it may help me
    understand what's wrong with John's solutions.
    
      John

Suppose we want to ensure that THREE numbers match.  The following shows that
this can be done with 120 cards.

We apply the pigeon-hole principle (many times).

Divide the ranges into three groups, 1-12, 13-24, and 25-36.  
Now the state's card will either have at least 3 numbers in one of these groups,
or 2 numbers in each of these groups.


We use the following 15 cards, which ensure that if the state has three numbers
in the 1-12 group, then we will have three matches (the 15 may not be minimal).

	1,2,3,4,5,6	1,2,7,8,9,10	3,4,7,8,11,12	5,6,9,10,11,12
	3,5,6,7,8,9	1,4,5,7,10,11	2,4,6,8,10,12	1,2,3,9,11,12
	2,4,6,7,9,11	2,3,5,8,10,11	1,4,5,8,9,12	1,3,6,7,10,12
	1,3,6,8,9,11	2,3,5,7,9,12	1,2,3,4,9,10

We include 2 more sets of 15 cards, to cover the 13-24 group, and the
25-36 group.  Thus, these 45 cards ensure that if the state's card has
at least 3 numbers in any of these groups, we will have three matches.


Suppose that the state's card has two numbers in each of these three groups.
We choose cards having two numbers in the 13-24 group and four numbers in the
1-12 group, such that we are ensured one match in the 13-24 group, and two
matches in the 1-12 group.

We need 6 'cards' in the 13-24 group to ensure one match, and the following
13 'cards' ensure two matches in the 1-12 group:

	1,2,3,4		3,7,11,12	4,5,6,10	1,9,10,11 
	2,8,10,12	4,7,8,9		1,5,9,12	3,6,8,9
	1,2,6,7		2,5,8,11	3,5,7,10	4,6,11,12
	1,2,8,9

We choose all 6 * 13 combinations of these 'cards'.  By a 'card' (in quotes),
I really mean a partial card.


This covers all possibilities, and requires only 3 * 15 + 6 * 13 = 123 cards.


That being understood, realize that the 13 'cards' above may make some of the
15 cards that were being used for the 1-12 group unnecessary.  Indeed, we find
that the following 12 cards (in combination with the 13 'cards' above) can
replace the 15 cards for the 1-12 group.  This is a net savings of 3 cards,
which leaves 120 cards.

	1,3,4,5,8,11	1,6,7,8,10,12	2,4,7,9,10,11	2,3,5,6,9,12
	1,3,4,6,7,9	5,8,9,10,11,12	2,3,6,9,10,11	2,4,5,7,9,12
	1,5,6,7,8,11	1,3,4,8,10,12	1,2,5,10,11,12	2,3,4,6,7,8

I think this might be improved a little bit more (down to 111), since each of
the 13 'cards' is duplicated 6 times.  Instead of duplicating them, it may be
possible to use different sets of 13 'cards', making the 15 cards for the 1-12
group (almost) totally unnecessary.


What is the theoretically minimal number of cards necessary?  Can anyone
improve on the above set of 120 cards?  Is there an easier way?

					- Gilbert

You're right, there was a hole in my argument. Sorry. I'm still confused, 
though.

>    Problem A (.0):  9 shown, 8 claimed.

I don't know what this statement means. We haven't discussed "A" or "B" 
previously in this note, nor do I know what the 9 and 8 refer to.
>    
>    Problem B (cover every pair):  66 is enough. Split 1-36 into twelve
>    groups -- 1-3, 4-6, 7-9, ..., 34-36.  Make a card from every pair of
>    groups; e.g. one card would be 7,8,9,19,20,21.
>    

I'll buy this: it's a nice, lucid solution. Good thinking, John.

Lynn Yarbrough 

>>    Problem A (.0):  9 shown, 8 claimed.
    
    Sorry, too cryptic.  What I meant was that we were talking about
    two different problems in this note.  Problem A was posed in .0,
    answered (8) in .1, answered (9) and demonstrated in .6.
    
    Problem B is the other problem being discussed here, answered in
    .7 and .14.  The difference between A and B is explained in .11 
    and .12.
    
    John
    

    It looks like the technique in .16 can be improved upon by using
    three groups that are NOT the same size.  For example, 8, 13, and 15.

    The following function seems useful:

	f(n, s, p, e) = the minimum (or near-minimal) number of cards needed.
			n = # of numbers (for example, 36)
			s = # of numbers the state chooses (ex: 6)
			p = # of numbers the player chooses per card (ex: 6)
			e = # of matches to be guaranteed (ex: 3)

    I've been able to calculate this analytically for a VERY FEW special cases.
    For others, I've gone through a nasty trial-and-error process.  Does someone
    have ideas on how to calculate this, or get near-minimal numbers, possibly
    with some recursion?

    Note that note .16 essentially uses the relation:

	f(36, 6, 6, 3) <= 3 * f(12, 3, 6, 3) + f(12, 2, 2, 1) * f(12, 2, 4, 2)

			<= 3 * 15 + 6 * 13 = 123

    I've gotten f(36,6,6,3) <= 94.

    Divide the 36 numbers into three groups of sizes 6, 15, and 15.
    Then we have:

	f(36,6,6,3) <= f(6,3,6,3) + f(15,3,6,3) + f(15,3,6,3)
			+ f(6,2,4,2) * f(15,2,2,1)

    But the following results are straight-forward:

	f(6,3,6,3) = 1
	f(6,2,4,2) = 3
	f(15,2,2,1) = 7

    And I found a 36 card example for f(15,3,6,3) (which is on a shard
    of paper somewhere -- I'll post it later).  Thus,

	f(36,6,6,3) <= 1 + 2*f(15,3,6,3) + 3*7 <= 1 + 2*36 + 3*7 <= 94

    I asked these questions in the LOTTERIES conference, but I think
    most of the math whizzes are here, so I'll ask my questions here.

    1.  As I understand it, to figure the odds of having a lottery
    ticket with all 6 winning numbers on it can be computed by the
    formula:

        (36*35*34*33*32*31) / (6*5*4*3*2*1)

    where the first sequence of numbers simply starts with the highest
    possible number in the lottery number range; in this example, the
    Mass 6/36 game.  Is there a similar formula for figuring out what
    the odds are for having a ticket with *5* of the winning numbers
    on it?  Or 4?  What about the 'special case' as with the Mass
    Millions game where there is a 'bonus number' drawn (ie, the 7th
    ball drawn), where in that case, the ONLY place the bonus number
    is any good is if your 6 chosen numbers match the bonus number plus
    any 5 of the 6 regular numbers?

    2.  Given a range of number that starts at 1 and the highest number
    is "R", where "R" would equal the highest possible number; ie, 36,
    40, etc.  Given "B" is the number of balls drawn to determine the
    winner, typically 6.  Given "G" as the number of drawings that you
    are examining.  What would be the formula to determine the PERCENTAGE
    of times that each number in the range "R" should (in a statistically
    ideal world) have been drawn?

    3.  Further on question #2: given the variables listed above, but
    then also given "H" which is the number of times that the number "N"
    actually was drawn over the course of those "G" drawings, what would
    be the formula to determine the PERCENTAGE of times that this number
    was drawn?

    Thanks
    Jon

	Answer to question 1.

	The formula for the number of ways to draw B balls, without
	replacement, from a collection of R balls labelled 1, ..., R is

						  R!
		if the order matters:		------
						(R-B)!

						   R!
		if the order does not matter:	--------
						B!(R-B)!

	You get this from:  there are R ways to draw the first ball,
	R-1 ways to draw one of the remaining balls, R-2 ways to draw
	one of th balls remaining after that, etc.  This multiplies
	out to R * R-1 * ... R-B+1 = R! / (R-B)!  This counts the number
	of ways when order matters.  Of the B balls chosen, the set
	may have been drawn in B! [plug B in for R in the formula just
	given, to get B! / 0! = B! (since 0! = 1)] different ways, so
	divide by B! to get the number of drawings where order doesn't
	matter.

	Now change the problem a bit.  We have R balls numbered 1,...,R.
	R1 of the balls, for example, the eighteen of some wheeling system,
	are marked as winners, and the rest of the balls R2=R-R1 are losers.
	(You can use the letter B to stand for B1+B2, the total number of
	balls drawn.)  Now, how many ways, with order not mattering, can one
	draw B1 winners (B1 <= R1) and B2 losers (B2 <= R2)?  Well, really
	this is just two drawings, one of B1 from R1 and one of B2 from R2.
	The number of ways of doing the first if R1!/(B1!(R1-B1)!) and the
	number of ways of doing the second is R2!/(B2!(R2-B2)!).  Each complete
	drawing combines one of each, and so there are

		    R1!           R2!
		----------- * -----------
		B1!(R1-B1)!   B2!(R2-B2)!

	combinations (when order doesn't matter).

	Example 1:  Plug in B1=R1 and B2=0 and you find one way to pick all
	winners and no losers.  :-)

	Example 2:  Let R=36 and B=6 as before, with R1=6 winners and
	R2=36-6=30 losers.  Draw B=6 balls: how many ways are there to
	draw B1 winners and B2 losers?  (W and L stand for winners and
	losers)

		 B1    B2
		----  ----
		W: 0, L: 6	6!/(0!6!) 30!/(6!24!) = 1 * 593775 = 593775
		W: 1, L: 5	6!/(1!5!) 30!/(5!25!) = 6 * 142506 = 855036
		W: 2, L: 4	6!/(2!4!) 30!/(4!26!) = 15 * 27405 = 411075
		W: 3, L: 3	6!/(3!3!) 30!/(3!27!) = 20 * 4060 =   81200
		W: 4, L: 2	6!/(4!2!) 30!/(2!28!) = 15 * 435 =     6525
		W: 5, L: 1	6!/(5!1!) 30!/(1!29!) = 6 * 30 =        180
		W: 6, L: 0	6!/(6!0!) 30!/(0!30!) = 1 * 1 =           1

	[read that as, say, the number of ways of picking 2 winners and 4
	losers is the number of ways of picking 2 of 6 winners times the
	number of ways of picking 4 of 30 losers, or 15 * 27405 = 411075]

	And, of course, 593775 + 855036 + 411075 + 81200 + 6525 + 180 + 1 =
	= 1947792 = 36! / (6!30!) = the total number of ways of choosing
	6 from 36.
	
	Example 3:  How many ways are there to pick 6 of 36 and have four
	of them be even?  Use R=36 balls, R1=18 "winners" (even balls) , R2=18
	losers (odd balls), and pick B1=4 winners and B2=2 losers:
	18!/(4!14!) * 18!/(2!16!) = 468180.  Preparing a table like in
	example 2 gives:

		6 even: 18!/(6!12!) * 18!/(0!12!) = 18564 * 1 =   18564
		5 even: 18!/(5!13!) * 18!/(1!13!) = 8568 * 18 =  154224
		4 even: 18!/(4!14!) * 18!/(2!14!) = 3060 * 153 = 468180
		3 even: 18!/(3!15!) * 18!/(3!15!) = 816 * 816 =  665856
		2 even: 18!/(2!16!) * 18!/(4!16!) = 153 * 3060 = 468180
		1 even: 18!/(1!17!) * 18!/(5!17!) = 18 * 8568 =  154224
		0 even: 18!/(0!18!) * 18!/(6!18!) = 1 * 18564 =   18564

	and the total, once again, is 1947792.  So if you have 18 favorite
	numbers of the 36, you know that there is, say, a (18564 + 154224
	+ 468180) / 1947792 = 640968/1947792 = 1571/4774 = slightly over
	32.9% probability that four or more of the drawing will be your
	favorites.

	To answer the second part of question 1, just generalize from
	two categories to three categories.  For the Massachusetts game
	in question you have R=46 balls, made up of R1=6 winners, R2=1
	bonus, and R3=39 losers.  The number of ways to pick B=B1+B2+B3
	balls of which B1 are winners, B2 are bonus, and B3 are losers
	(of course, with B1 <= R1, B2 <= R2, B3 <= R3) are

		    R1!           R2!           R3!
		----------- * ----------- * -----------
		B1!(R1-B1)!   B2!(R2-B2)!   B3!(R3-B3)!

	In the particular case you asked for B1=5 winners, B2=1 bonus
	and B3=0 losers: there are 6 * 1 * 1 = 6 ways to do that.

	Dan

    re .22
    
    I'm not sure I understand, so let me ask the same questions with real
    numbers.  Say the lottery is a 40 number game, such as the Tri-State.
    Over the course of say, 50 games, you could state that 300 numbers have
    been drawn.  (50 games * 6 numbers drawn per game).
    
    Now pick a number, say 15.  Two questions now:
    
    1.  What is the statistically ideal number of times that the number 15
    should have been drawn?
    
    2.  What statistically ideal percentage of the time should the number
    15 have been drawn?  (I expect that this percentage will not differ
    regardless of how many games are being examined?)
    
    Now for a third question, somewhat related but using the same example.
    Say that over these 50 games, you know that the number 15 has been
    drawn 12 times.  My calculations should that to be 4% of the time -- is
    that accurate?
    
    Thanks
    Jon

    	re .23
    
        I didn't deal with that question in .22, just with
        question 1 of note 21.
        
        Dan

    Re .23:
    
    > 1.  What is the statistically ideal number of times that the number 15
    > should have been drawn?

    I have not seen the term "statistically ideal" before.  There is an
    "expected number" of times that the number 15 will be drawn.  This is
    not actually the number of times it is expected to be drawn; rather,
    each possible number of times that 15 will be drawn in 50 games has a
    certain probability, and the "expected number" of times that 15 will be
    drawn is the average of those numbers weighted with their probability.
     
    The expected number is a central tendency indicator; it tells you about
    where the "middle" of the distribution is located, in some sense.

    The expected number of times that 15 will be drawn in 50 games of
    picking 6 numbers from a set of 40 numbers is 300/40 = 7.5.  This is
    true because all 40 numbers are identical as far as selection in the
    lottery goes, so they must all have equal expected numbers of
    occurrences, and those expected numbers of occurrences for all of them
    must add up to the total occurrences, which is 300 since 300 numbers
    are picked.  (The expected number can also be found by computing the
    probability that 15 appears in a single game and multiplying by the
    number of games.)
    
    > 2.  What statistically ideal percentage of the time should the number
    > 15 have been drawn?  (I expect that this percentage will not differ
    > regardless of how many games are being examined?)

    In a single game, 15 is one of the six numbers chosen 6/40 of the time,
    or 15%.
    
    > Now for a third question, somewhat related but using the same example.
    > Say that over these 50 games, you know that the number 15 has been
    > drawn 12 times.  My calculations should that to be 4% of the time -- is
    > that accurate?

    In 50 games, 15 is chosen exactly 12 times only 3.275% of the time.  15
    is chosen 12 or more times 6.251% of the time.
    
    Since in one game, 15 is chosen 6 times in 40, the probability of 12
    15's being chosen in 50 games is:
    
    	C(50 12) * (6/40)^12 * (34/40)^(50-12) ~= .03275

    C(m n) denotes the number of ways to chose n objects from m objects,
    ignoring order.  C(m n) = m! / (n! * (m-n)!).
    
    
				-- edp

>    The expected number of times that 15 will be drawn in 50 games of
>    picking 6 numbers from a set of 40 numbers is 300/40 = 7.5.  This is
    
>    In a single game, 15 is one of the six numbers chosen 6/40 of the time,
>    or 15%.
    
    Does this take into account the fact that the MAXIMUM number of times
    that 15 could be drawn in 50 games is *50*, not *300*, since the number
    15 (or any other number) can only appear once in each set of 6?
    
    Jon

    Re .26:

    Yes, it does.  Although the format of the game (50 instances of 6
    selections without replacement) changes the distribution of the
    probabilities of the numbers of occurrences, it does not change the
    average.  (The distribution is brought in more toward the center;
    numbers close to the average have higher probability than they would in
    a distribution made from 300 instances of 1 selection.)

    The average must stay the same because the reasoning about all numbers
    being identical still holds -- there's no reason for any one number to
    be any different from any other, so they must all have the same
    expected number of occurrences, and those numbers must add up to the
    total number of draws, 300.

    The expected number can also be computed more directly.  In 1
    selection, 15 has a 1/40 chance of showing up once and a 39/40 chance
    of showing up zero times.  In 300 repetitions of that, the expected
    number of occurrences of 15 is 300 * (1 * 1/40 + 0 * 39/40) = 300/40.
    
    In 6 selections, 15 has a 1/40 chance of showing up on the first
    selection.  If it does not show up then (chance 39/40), it has a 1/39
    chance of showing up on the next selection.  Continued through 6
    selections, the chance of 15 showing up on any of the six selections
    is:
    
    	1  39*1  39*38*1  39*38*37*1  39*38*37*36*1  39*38*37*36*35*1
    	--+-----+--------+-----------+--------------+----------------
        40 40*39 40*39*38 40*39*38*37 40*39*38*37*36 40*39*38*37*36*35
    
    Reduced, that's 6/40 -- there's a 6/40 chance that 15 will show up once
    in 6 selections and 34/40 chance that it will show up zero times. 
    Repeated 50 times, that is:
    
    	50 * (1 * 6/40 + 0 * 34/40) = 300/40.
    
    The average is the same.
    
    
    				-- edp