Let me give the problem with 1 concrete example:
Suppose you have a lottery called "Keno" that draws 20 numbers out of 80(from 1 to 80).
Players can choose from 1 to 12 numbers, category-1, category-2 etc. If they choose 1 number for example they win if they get this number to be in those 20 that are drawn. If they choose 7, they win if 7 or 6 or 5 or 4 are inside to those 20 numbers that had been drawn. And of course if they get 7 out of 7 they will get something like 15000 times of the money the have bet.
If they get 12 out of 12 they will get 1 000 000 times the money the have bet, etc.
Now suppose Keno is played every day from 09:00 to 21:00(it doesn't matter anyway) with every draw of the lucky balls to occur every 5 minutes. That is the first draw occurs at 09:00, then at 09:05, .....etc.
Now suppose that in every draw all the players play about 290 000 tickets(a ticket is just a N-set of numbers (N=1 to 12 depending of what category the player have chosen to play)). Note that this happens obviously inside these 5 minutes.
So a draw is being made and then in the next 5 minutes all the players would play around 290 000 tickets for the next draw, and after 5 minutes the next draw will be made.
► My question is if there is any efficient algorithm(s) for the company that offers the Keno game to apply, in order to create a draw with 20 numbers, to assure that no player will get a 12 out of 12 a 11 out of 11 and generally to give big winnings to the players, within these 5 minutes?
►Or if there isn't one what is the time the company needs to calculate the draw of 20 number that will assure no player gets a 12 out of 12 and an 11 out of 11? Is it a billion years, 10 years or much less and how much?
Efficient means to process these 290 000 tickets(we can assume them different) with N-set(N=1, 2, 3,...,12) of numbers(the numbers are from 1 to 80) within 5 minutes and create a set of 20 numbers(the numbers are from 1 to 80) in order to don't give any big win.
For simplicity's sake let's assume all the 290000 tickets are played on the 12-category(that is players played 12 numbers) and that company wants to assure that no one gets 12 out of 12 and 11 out of 12.
►Is this question in NP?
► Is there any algorithm that can make this processing? And what is the most efficient algorithm for that, even if it needs thousands of years to do that.
►If there are positive answers to the above, are there are any generalizations for the general Lotto game with K time(instead of 5 minutes)?
---------------------------
---------------------------
Let me give a small example:
Suppose there is a game that draws 6 numbers(and not 20 as in Keno of my post) out of 10(1 to 10 and not 80 as in Keno of my post) and players play 4 numbers.
And the 6 players played:
-P1: {1,2,8,10}
-P2: {3,5,6,8}
-P3: {2,3,5,9}
-P4: {1,4,8,9}
-P5: {4,5,8,10}
-P6: {2,4,7,10}
And we want a draw of 6 numbers {a1,a2,a3,a4,a5,a6} that will make no player to have a 4 out of 4 match.
This is easy to create for the current example, even with no computer program to check the results.
But when you have thousands of players(tickets that players played) and not just 10 number to choose form but 80, and 20 numbers to be drawn in the lot, then things get complicated.
So is there any efficient algorithm to find the appropriate draw?
And what is the most efficient algorithm of today to do that and in what time it does it? Exponentially? What is its big O?
Thanks in advance.
In case you find the questions a bit difficult or off topic, can you provide me with a programming forum link that i can ask there my questions?