I've been trying to "solve" a problem and I've run into a pretty solid wall and need some ideas. Here's the problem put as simply as I can. Note this is a problem in combinatrics, not a lottery problem.
Imagine a 6 from 49 lottery where 6 balls are drawn at random from a set of 49 without replacement. Order is unimportant. How many tickets/lines of numbers would I need to buy to guarantee at least 2 matches on one line?
The current best is 19 lines. http://lottery.merseyworld.com/Wheel/
So, how far have I got?
Each line is 0<n1<n2<n3<n4<n5<n6<50 which gives 13983816 possible lines from 1,2,3,4,5,6 to 44,45,46,47,48,49.
Option 1 - Brute Force
Working on proving if there's an 18 line option for 2 matches, this gives 6.5300550628388e+112 possible variations to test. Assuming 0.1 seconds per test on each combination, a brute force attempt would take 2.07e+104 years. Even spread across all 10 CPUs here and allowing a bit for Moore's Law would maybe cut it down to 2e+100 years.
Patently not an option in my lifetime.
Option 2 - Monte Carlo
Monte Carlo is a means of solving a problem whereby a random starting point is continually modified. Modifications that result in an improved outcome are retained. Modifications that result in a worsened outcome are rejected. By changing one or more numbers at a time, I have managed to achieve 99.9549% coverage by using the first 18 lines of the 19 lines as a start point. Monte Carlo methods haven't actually improved on that start point however one limitation of Monte Carlo methods is they're prone to get stuck in local minima solutions. Running with a random start point generally gets to 99.2% and seemingly gets stuck.
Option 3 - Ask for help and suggestions
That'll be where I am now.
Can anyone suggest ways of working out what the minimum number of lines is and/or working out what those lines are?
BTW, I asked this on a maths forum and they didn't seem to think it could be done in 19 lines which was a little worrying.
Imagine a 6 from 49 lottery where 6 balls are drawn at random from a set of 49 without replacement. Order is unimportant. How many tickets/lines of numbers would I need to buy to guarantee at least 2 matches on one line?
The current best is 19 lines. http://lottery.merseyworld.com/Wheel/
So, how far have I got?
Each line is 0<n1<n2<n3<n4<n5<n6<50 which gives 13983816 possible lines from 1,2,3,4,5,6 to 44,45,46,47,48,49.
Option 1 - Brute Force
Working on proving if there's an 18 line option for 2 matches, this gives 6.5300550628388e+112 possible variations to test. Assuming 0.1 seconds per test on each combination, a brute force attempt would take 2.07e+104 years. Even spread across all 10 CPUs here and allowing a bit for Moore's Law would maybe cut it down to 2e+100 years.

Option 2 - Monte Carlo
Monte Carlo is a means of solving a problem whereby a random starting point is continually modified. Modifications that result in an improved outcome are retained. Modifications that result in a worsened outcome are rejected. By changing one or more numbers at a time, I have managed to achieve 99.9549% coverage by using the first 18 lines of the 19 lines as a start point. Monte Carlo methods haven't actually improved on that start point however one limitation of Monte Carlo methods is they're prone to get stuck in local minima solutions. Running with a random start point generally gets to 99.2% and seemingly gets stuck.
Option 3 - Ask for help and suggestions
That'll be where I am now.

BTW, I asked this on a maths forum and they didn't seem to think it could be done in 19 lines which was a little worrying.

Comment