Re: Help in solving this puzzle


<matt271829-news@xxxxxxxxxxx> wrote in message
news:1143852272.571724.173260@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Michael Harrington wrote:
<matt271829-news@xxxxxxxxxxx> wrote in message
news:1143811743.700626.31370@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

john@x wrote:
There is a lottery drawn on 1 through 20 numbers and six distinct
balls

are randomly picked by the lottery every day. To play you need to buy
a

ticket and select six numbers of your choice. An example ticket might
be [1,20,6,19,5,12] You can buy any number of tickets. If any three of
the numbers in one of your tickets are among the six winning numbers
picked by the lottery, in any order then you win.
What is the minimum number of tickets you have to buy to be certain of
winning with atlease one?
Thanks
John

I think you can do it with 14 tickets, though I do not know if this is
the minimum. This is an example 14-ticket solution (I hope!):

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
1 2 7 13 19 20
3 4 8 14 19 20
5 6 9 10 15 16
5 6 11 12 17 18
1 3 9 10 17 18
2 4 11 12 15 16
5 6 7 8 13 14
1 2 8 14 19 20
3 4 7 13 19 20
1 2 3 4 7 13
1 2 9 10 19 20

I now have 12 tickets which comply with exhaustive testing>>>
1 2 3 4 5 6
1 2 3 4 7 8
1 2 5 6 7 8
3 4 5 6 7 8
9 10 11 12 13 14
9 10 11 12 15 16
9 10 13 14 15 16
11 12 13 14 15 16
17 18 19 20 1 2
17 18 19 20 3 4
17 18 19 20 5 6
17 18 19 20 7 8

Very good! It's interesting to see how your answer has so many
repetitions - for example, four tickets all with the numbers 17, 18,
19, 20. Intuitively you would think (or I would, anyway) that the best
solutions would mix up the numbers as much as possible. Do you think
that 12 is the best that can be achieved?


Logic:
Divide 20 numbers into 3 blocks ( 2 blocks of 8 numbers & 1 block of 4
numbers)
Defining the blocks as eg (1 to 8 ) & (9 to 16) & (17 to 20)
With 6 numbers drawn, one of these blocks must contain at least 3 of the
drawn numbers or else each block contains exactly 2 drawn numbers.
Every combination of three from eight numbers can be covered with 4
tickets.>>
1 2 3 4 5 6
1 2 3 4 7 8
1 2 5 6 7 8
3 4 5 6 7 8
And
9 10 11 12 13 14
9 10 11 12 15 16
9 10 13 14 15 16
11 12 13 14 15 16
And
17 18 19 20 ( plus any other two numbers) covers every combination of
three
from the block of four numbers.
The alternative to one of these blocks containing at least 3 numbers is
that
each
block has exactly 2 numbers. This means that the block of four (17 18 19
20)
must
contain two numbers. If we combine this block of four with every number
from
one to the blocks of eight this must give at least three numbers in one
of
the
resulting tickets.

PS I previously interpreted the puzzle as requiring every combination of
3
to be covered. With six numbers drawn giving 20 combos of 3 numbers the
earlier
solution I posted of 120 tickets( which did contain every combo of 3)
therefore
also contained 20 combos of 3 from any draw.
Regards Richard Spelman.


Don't know if 12 is the best that can be achieved. Could you please
explain the reasoning behind your 14 solution as it may help in
understanding.
Would like any fresh insights into approaching the problem.
Am also curious as to whether or not there is a definitive mathematical
solution.

Regards Richard Spelman.


.

Relevant Pages

  • Re: 150 lines for 28 numbers( aiming to 5 hit)
    ... WON'T BE DRAWN. ... Get that right every time for 50 draws and I'll ... Dare you say anyone posted 100 tickets in less than 3 times and made ... How much money did you win? ...
    (rec.gambling.lottery)
  • Re: U19 RWC semi line-up
    ... lottery occasionally. ... tickets than the others, thus reducing the odds for that player. ... He mentioned the probability of a ticket being drawn, ...
    (rec.sport.rugby.union)
  • Re: U19 RWC semi line-up
    ... lottery occasionally. ... tickets than the others, thus reducing the odds for that player. ... drawn than the one million and oneth ticket. ... Whereas you wasted your time trying to prove that 1,000,000/1,000,001> 1/1,000,0001, which is not what Rick was saying. ...
    (rec.sport.rugby.union)
  • Re: Countif
    ... "Mike" wrote in message ... > numbers on lottery tickets. ... > contain 5 numbers and at the bottom the actual numbers that were drawn. ...
    (microsoft.public.excel)
  • Re: Countif
    ... > Using Windows XP & Excel XP. ... > numbers on lottery tickets. ... > contain 5 numbers and at the bottom the actual numbers that were drawn. ...
    (microsoft.public.excel)