My Math Forum (http://mymathforum.com/math-forums.php)
-   Computer Science (http://mymathforum.com/computer-science/)
-   -   Computability/Complexity problem related to Lotto/Keno. (http://mymathforum.com/computer-science/10931-computability-complexity-problem-related-lotto-keno.html)

 ChessTal January 27th, 2010 04:46 AM

Computability/Complexity problem related to Lotto/Keno.

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?

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? :? :cry:

 CRGreathouse January 27th, 2010 05:19 AM

Re: Computability/Complexity problem related to Lotto/Keno.

Let me see if I understand your assumptions. Of course ideally I'd find a way to replace your parameters with variables, but I'll try the problem with numbers first.
• There will be 145 draws (every 5 minutes between 09:00 to 21:00, including 09:00 and 21:00)[/*:m:3b2vkkam]
• There are 290 000 tickets with 12 numbers each[/*:m:3b2vkkam]
• Each draw consists of 20 numbers from a pool of 80[/*:m:3b2vkkam]
• Can the draws avoid matching 12/12 numbers on any ticket? Can they avoid matching 11/12 numbers on any ticket?[/*:m:3b2vkkam]

The number of draws isn't very important here. Generally, if you can find one way you can find many, and you haven't said that I can't repeat results anyway. :twisted:

So the first question is: computation aside, is such a choice always possible?

Call matching at least 11/12 numbers in a single draw "winning". Each ticket has
P(win) = ((# ways to choose 11 out of 20) * 12 - (# ways to choose 12 out of 20) * 11)/(# ways to choose 20 out of 80)
= (binomial(20,11)*12-binomial(20,12)*11)/binomial(80,20)
= 4845/27194739555478264

So if all the players cooperate, they can (at best) force 4845/27194739555478264 * 290 000 of the possible draws to win. This is about 0.000000052, which is much smaller than 1. In particular, this suggests that an efficient algorithm would be:
• Draw 20 numbers at random[/*:m:3b2vkkam]
• Test the 290 000 tickets to see if any would win[/*:m:3b2vkkam]
• If so, start over; otherwise, return that result[/*:m:3b2vkkam]

 ChessTal January 27th, 2010 05:50 AM

Re: Computability/Complexity problem related to Lotto/Keno.

Quote:
 Originally Posted by CRGreathouse Let me see if I understand your assumptions. Of course ideally I'd find a way to replace your parameters with variables, but I'll try the problem with numbers first. There will be 145 draws (every 5 minutes between 09:00 to 21:00, including 09:00 and 21:00)[/*:m:2nw5bvc5] There are 290 000 tickets with 12 numbers each[/*:m:2nw5bvc5] Each draw consists of 20 numbers from a pool of 80[/*:m:2nw5bvc5] Can the draws avoid matching 12/12 numbers on any ticket? Can they avoid matching 11/12 numbers on any ticket?[/*:m:2nw5bvc5]
All correct. And nothing more is required to know.
And as you note below the first assumption is irrelevant to my question and it doesn't need to be mentioned.

So to sum up:
•There are 290 000 tickets with 12 random but different(in every 12-set) numbers each(from 1 to 80). (Note that there can be 2 or more 12-sets that are identical).
•Each draw consists of 20 numbers from a pool of 80(1 to 80).
•Can the draws avoid matching 12/12 numbers and 11/12 numbers on any ticket?
•Is in NP the above question?
•What is the time the most efficient algorithm known, can do that matching?

Quote:
 The number of draws [color=#0000BF]isn't very important here[/color]. Generally, if you can find one way you can find many, and you haven't said that I can't repeat results anyway. :twisted:
Correct. Actually it's not important at all. :)

Quote:
 So the first question is: computation aside, is such a choice always possible? Call matching at least 11/12 numbers in a single draw "winning". Each ticket has P(win) = ((# ways to choose 11 out of 20) * 12 - (# ways to choose 12 out of 20) * 11)/(# ways to choose 20 out of 80) = (binomial(20,11)*12-binomial(20,12)*11)/binomial(80,20) = 4845/27194739555478264 So if all the players cooperate, they can (at best) force 4845/27194739555478264 * 290 000 of the possible draws to win. This is about 0.000000052, which is much smaller than 1.
So if i get this correctly, you say that a draw of 20 numbers can always exist that can succeed in NOT matching all the 290000 tickets of 12-numbers of the players. Right?

Quote:
 So if all the players cooperate, they can (at best) force 4845/27194739555478264 * 290 000 of the possible draws to win. This is about 0.000000052, which is much smaller than 1. In particular, this suggests that an efficient algorithm would be: Draw 20 numbers at random[/*:m:2nw5bvc5] Test the 290 000 tickets to see if any would win[/*:m:2nw5bvc5] If so, start over; otherwise, return that result[/*:m:2nw5bvc5]
Yes of course but this algorithm is more or less simple brute force and computable very costly. I guess its complexity is huge(n!) and can't be practically applied, since you have to search (Draw 20 numbers at random-.....-If so, start over;) A=80!/(20!60!) > 3·10^18 times and make A·290000 comparisons.

 CRGreathouse January 27th, 2010 07:23 AM

Re: Computability/Complexity problem related to Lotto/Keno.

Quote:

Originally Posted by ChessTal
Quote:
 So if all the players cooperate, they can (at best) force 4845/27194739555478264 * 290 000 of the possible draws to win. This is about 0.000000052, which is much smaller than 1. In particular, this suggests that an efficient algorithm would be: Draw 20 numbers at random[/*:m:1oz5615w] Test the 290 000 tickets to see if any would win[/*:m:1oz5615w] If so, start over; otherwise, return that result[/*:m:1oz5615w]
Yes of course but this algorithm is more or less simple brute force and computable very costly. I guess its complexity is huge(n!) and can't be practically applied, since you have to search (Draw 20 numbers at random-.....-If so, start over;) A=80!/(20!60!) > 3·10^18 times and make A·290000 comparisons.

No.

Let p = 4845/27194739555478264 * 290 000. The expected number of trials is at most 1/(1-p), which is about A = 1.0000000517. The expected work is at most A draws and 290 000(A - (A-1)/2) checks for winners.

The chance that more than two trials are needed is less than 0.003 in a trillion. The chance that only one trial is needed is greater than 99.999994%.

And remember, this is all for the worst case where the players collude against you. If they instead pick their numbers randomly, it gets better for you; if they choose some numbers with higher probability than others, better yet.

 anadya December 23rd, 2018 12:15 PM

hello i need some help with massachusetts keno. i want to know how to get one number correct. a one spot wager of \$20 will win you \$50. i know you have to play when busy and i know its an rng with a seed an algorithm

i have also read the best seed is time. i have read you have to watch the keno board but what am i looking for when i watch the board?

i have much info on the usa lottery so if you want to swap info please send me your email

 Maschke December 23rd, 2018 01:33 PM

Quote:
 Originally Posted by anadya (Post 603621) hello i need some help with massachusetts keno. i want to know how to get one number correct. a one spot wager of \$20 will win you \$50. i know you have to play when busy and i know its an rng with a seed an algorithm i have also read the best seed is time. i have read you have to watch the keno board but what am i looking for when i watch the board? i have much info on the usa lottery so if you want to swap info please send me your email
I like Lucky Louie in the fifth at Del Mar. I heard it from the horse's mouth.

You know Keno played at casinos has terrible odds. The payoffs are way less than the actual odds. Keno is about the worst game you can play.

 Denis December 23rd, 2018 02:35 PM

You've reactivated an 8 years old thread; what do you really want?
And what d'hell does this mean:
"i know you have to play when busy and i know its an rng with a seed an algorithm"?

 anadya December 25th, 2018 10:17 AM

keno in massachusetts

denis playing when its busy means that frid sat sund holidays more people are playing keno and those are called high payout nights as the computer is due to pay out some of the money it has taken in

rng stands for random number generator it runs on seed and algorithm

with that said i still cant get only one number correct. i could use your help here. thanks ana

 All times are GMT -8. The time now is 02:25 PM.