Algorithm for a lucky game [on hold]
- by Ronnie
Assume we have the following Keno(lottery type) game:
From 80 numbers(from 1 to 80), 20 are being drawn.
The players choose 1 or 2 or 3..... or 12 numbers to play(12 categories).
If they choose for example 4 then they win if they predict correctly a certain amount of numbers(2,3 or 4) from the 4 they have played and lose if the predict only 1 or 0 numbers. They win X times their money accordingly to some predefined factor depending on how many numbers they predict from each category.
The same with the other categories. And e.g 11 out of 11 gives 250000 times your money and 12 out of 12 gives 1000000 your money. So the company would want to avoid winnings so high.
Every draw by the company is being made every 5 minutes and in each draw around 120000 (let's say) different predictions(Keno tickets) are being played.
Let's assume 12000 are being played in category 10 and 12000 in category 11 and also 12000 in category 12.
I'm wondering if there is an algorithm to allow the company that provides the game in the 5 minutes between the drawings, to find a 20 number set, in order to avoid any "12 out of 12" and "11 out of 11" and "11 out of 12" and "10 out of 11" and "10 out of 10" winning ticket.
That means is there any algorithm, where in a time of less than 1 minute approximately(in todays hardware), to be able to find a 20 number set so that none of the 12000 12 and 11 and 10 number sets that the players played(in categories 10,11 and 12) contains any winning of "12 out of 12" and "11 out of 11" and "11 out of 12" and "10 out of 11" and "10 out of 10"?
Or even better the generalization of the problem:
What is the best algorithm(from a perspective of minimal time), to be able to find a Y number set from numbers 1 to Z(e.g Y=20, Z=80) so that none of the X sets of K-numbers that are being played(in category K) contains more than K-m numbers from the Y-set?
(Note that for Y=K and m=1 there is a practical algorithm.)
