Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a
transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the
current reference desk pages.
June 22 Information
Random number game
One hundred contestants pay to enter a game. In Round 1, they are asked to select on their keyboard a number between 1 and 100. No contestant knows what any other contestant has chosen. Once a number is chosen, that person cannot choose it in a future round. If two or more people choose the same number in the same round, they are eliminated. Then the process repeats with the reduced group, and so on until there are only one or two people left. The remaining person or people win or share the prize pool. If everyone is eliminated before that point (three or more remaining players all happen to pick the same number, for example), the prize pool jackpots for the next game.
Does "everyone is eliminated" count as a "result"? Also, it is possible that contestants run out of numbers in 100 rounds without reaching the stage of only one or two left. (The problem can be generalized to N contestants who pick numbers from 0 to N−1. Think
clock arithmetic, where N is the same as 0. One scenario is that each contestant cycles through the numbers in increments of 1, all starting at a different value, like in round r contestant i enters i+r.) How should this be accounted for? When N = 100, the likelihood of this happening is negligible, though. If we count "everyone is eliminated" as a result,
Monte Carlo simulation indicates that the average number of rounds in a single game is close to 45. If the players cannot know what others have chosen in past rounds, they cannot influence their chances one way or another. --
Lambiam09:45, 22 June 2021 (UTC)reply
Once you get down to three players, it would take on average 33 rounds to get a match. If you ended up with four players then it would be about 17 rounds, but then the chances are that you'd have a tie; neither can win if there are two players left. --
RDBury (
talk)
13:07, 22 June 2021 (UTC)reply
As I said, the remaining person or people win or share the prize pool. Clearly, the game continues until there are less than three players left. If two, they share the pool. If one, he/she wins the entire pool. If zero, it jackpots to the next round game. --
Jack of Oz[pleasantries]01:07, 23 June 2021 (UTC)reply
If no contestant knows what any other contestant has chosen holds after each round (i.e. if you are still in the game, the previous choices of others are not revealed to you), then you cannot do any better than pick randomly, unless you know something that breaks the symmetry.
For the purposes of computing the probability of deaths in a given round, I am almost certain that we can assume everyone picks randomly between 1 and 100, regardless of the previous round's number picks, by a symmetry argument. Assuming that holds, the probability of a win when there are k persons at the start and N numbers to pick from (N=100 here) could be computed by a relatively simple
dynamic programming task:
By the rules, (if at any moment, there are 1 or 2 persons left, they win, if there is nobody left, everyone loses).
If we assume that a given moment there are n persons standing, the probability of a win is given by the standard Markov-chain rule where is the probability that k people survive a round of n persons (again: I think it is safe to assume this depends only on the total number of possible picks N, and not how many have been picked so far of what they were).
You would think that the formula for is somewhere in our page about the
birthday problem but I did not find it (it only gives P(n→n) and the average number of collisions i.e. the first moment of the P(n→k)). A quick online search turns up many related problems (
example) but not exactly this one. Even if there is not a closed formula with binomial coefficients, there is probably a way to compute it. I searched something along the following lines: split the N initial persons between k that will not collide (P(k→k)) and N-k that will (number of possible ways to sort N-k people into b buckets with at least two in each bucket = ?), sum over the number of possible collision buckets b and ensure the colliding and non-colliding groups stay in the N-b and b buckets each.
TigraanClick here for my talk page ("private" contact)09:24, 23 June 2021 (UTC)reply
Did you account for this clause: "Once a number is chosen, that person cannot choose it in a future round."? It seems to me that the state space is far too large, also after reduction by using its symmetries, for a dynamic programming approach to be feasible. --
Lambiam22:09, 24 June 2021 (UTC)reply
I "accounted" for it by assuming it away, by the following argument: people who are alive do not know what other people who are alive have picked in previous rounds, so from one person's point of view the others are just picking randomly without restrictions, and then their own restrictions do not matter either (by symmetry). There is a good chance that this is an approximation and it is wrong, but is it wrong enough to change the result significantly? My physicist's warm fuzzy feeling says "eh, probably not", at least with large N and a large number of rounds.
TigraanClick here for my talk page ("private" contact)11:43, 25 June 2021 (UTC)reply
Experimentally I see indeed no significant differences, also not for small values of N (= both number of participants & numbers to choose from). The expected values are not exactly the same, though; for N = 3 I find 1.27778 (with clause) vs. 1.27160 (without, with a cutoff of N). --
Lambiam14:56, 25 June 2021 (UTC)reply
RDBury, the fluid dram is 1/4 of the tablespoon, and it's back to the power of 2 rule. Was there once a unit equal to 1/2 a tablespoon or 2 fluid drams??
Georgia guy (
talk)
16:45, 22 June 2021 (UTC)reply
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a
transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the
current reference desk pages.
June 22 Information
Random number game
One hundred contestants pay to enter a game. In Round 1, they are asked to select on their keyboard a number between 1 and 100. No contestant knows what any other contestant has chosen. Once a number is chosen, that person cannot choose it in a future round. If two or more people choose the same number in the same round, they are eliminated. Then the process repeats with the reduced group, and so on until there are only one or two people left. The remaining person or people win or share the prize pool. If everyone is eliminated before that point (three or more remaining players all happen to pick the same number, for example), the prize pool jackpots for the next game.
Does "everyone is eliminated" count as a "result"? Also, it is possible that contestants run out of numbers in 100 rounds without reaching the stage of only one or two left. (The problem can be generalized to N contestants who pick numbers from 0 to N−1. Think
clock arithmetic, where N is the same as 0. One scenario is that each contestant cycles through the numbers in increments of 1, all starting at a different value, like in round r contestant i enters i+r.) How should this be accounted for? When N = 100, the likelihood of this happening is negligible, though. If we count "everyone is eliminated" as a result,
Monte Carlo simulation indicates that the average number of rounds in a single game is close to 45. If the players cannot know what others have chosen in past rounds, they cannot influence their chances one way or another. --
Lambiam09:45, 22 June 2021 (UTC)reply
Once you get down to three players, it would take on average 33 rounds to get a match. If you ended up with four players then it would be about 17 rounds, but then the chances are that you'd have a tie; neither can win if there are two players left. --
RDBury (
talk)
13:07, 22 June 2021 (UTC)reply
As I said, the remaining person or people win or share the prize pool. Clearly, the game continues until there are less than three players left. If two, they share the pool. If one, he/she wins the entire pool. If zero, it jackpots to the next round game. --
Jack of Oz[pleasantries]01:07, 23 June 2021 (UTC)reply
If no contestant knows what any other contestant has chosen holds after each round (i.e. if you are still in the game, the previous choices of others are not revealed to you), then you cannot do any better than pick randomly, unless you know something that breaks the symmetry.
For the purposes of computing the probability of deaths in a given round, I am almost certain that we can assume everyone picks randomly between 1 and 100, regardless of the previous round's number picks, by a symmetry argument. Assuming that holds, the probability of a win when there are k persons at the start and N numbers to pick from (N=100 here) could be computed by a relatively simple
dynamic programming task:
By the rules, (if at any moment, there are 1 or 2 persons left, they win, if there is nobody left, everyone loses).
If we assume that a given moment there are n persons standing, the probability of a win is given by the standard Markov-chain rule where is the probability that k people survive a round of n persons (again: I think it is safe to assume this depends only on the total number of possible picks N, and not how many have been picked so far of what they were).
You would think that the formula for is somewhere in our page about the
birthday problem but I did not find it (it only gives P(n→n) and the average number of collisions i.e. the first moment of the P(n→k)). A quick online search turns up many related problems (
example) but not exactly this one. Even if there is not a closed formula with binomial coefficients, there is probably a way to compute it. I searched something along the following lines: split the N initial persons between k that will not collide (P(k→k)) and N-k that will (number of possible ways to sort N-k people into b buckets with at least two in each bucket = ?), sum over the number of possible collision buckets b and ensure the colliding and non-colliding groups stay in the N-b and b buckets each.
TigraanClick here for my talk page ("private" contact)09:24, 23 June 2021 (UTC)reply
Did you account for this clause: "Once a number is chosen, that person cannot choose it in a future round."? It seems to me that the state space is far too large, also after reduction by using its symmetries, for a dynamic programming approach to be feasible. --
Lambiam22:09, 24 June 2021 (UTC)reply
I "accounted" for it by assuming it away, by the following argument: people who are alive do not know what other people who are alive have picked in previous rounds, so from one person's point of view the others are just picking randomly without restrictions, and then their own restrictions do not matter either (by symmetry). There is a good chance that this is an approximation and it is wrong, but is it wrong enough to change the result significantly? My physicist's warm fuzzy feeling says "eh, probably not", at least with large N and a large number of rounds.
TigraanClick here for my talk page ("private" contact)11:43, 25 June 2021 (UTC)reply
Experimentally I see indeed no significant differences, also not for small values of N (= both number of participants & numbers to choose from). The expected values are not exactly the same, though; for N = 3 I find 1.27778 (with clause) vs. 1.27160 (without, with a cutoff of N). --
Lambiam14:56, 25 June 2021 (UTC)reply
RDBury, the fluid dram is 1/4 of the tablespoon, and it's back to the power of 2 rule. Was there once a unit equal to 1/2 a tablespoon or 2 fluid drams??
Georgia guy (
talk)
16:45, 22 June 2021 (UTC)reply