Wikipedia:Reference desk/Archives/Mathematics/2021 June 22

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

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.

How many rounds should we expect this to take before a result? Is there a good strategy for maximising one's chances of winning? -- Jack of Oz ^{[pleasantries]} 08:35, 22 June 2021 (UTC)

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.  --Lambiam 09:45, 22 June 2021 (UTC)

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)

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)

But would it really be 33 rounds at that stage, given that they've already used up possibly 50 of the available numbers? -- Jack of Oz ^{[pleasantries]} 01:25, 23 June 2021 (UTC)

• 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) $P_{w}(k,N)$could be computed by a relatively simple dynamic programming task:

1. By the rules, $P_{w}(0,N)=0,P_{w}(1,N)=P_{w}(2,N)=1$ (if at any moment, there are 1 or 2 persons left, they win, if there is nobody left, everyone loses).
2. 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 $P_{w}(n,N)=\sum _{k}P_{w}(k,N)P(n\rightarrow k,N)$ where $P(n\rightarrow k,N)$ 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 $P(n\rightarrow k,N)$ 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. Tigraan^{Click here for my talk page ("private" contact)} 09:24, 23 June 2021 (UTC)

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.  --Lambiam 22:09, 24 June 2021 (UTC)

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. Tigraan^{Click here for my talk page ("private" contact)} 11:43, 25 June 2021 (UTC)

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).  --Lambiam 14:56, 25 June 2021 (UTC)

Tablespoons, teaspoons, and fluid drams

Why is a teaspoon 1/3 and not 1/2 of a tablespoon?? The teaspoon is the only unit that's out of the power of 2 rule. (Check out a discussion at Talk:Gill (unit).) Georgia guy (talk) 13:56, 22 June 2021 (UTC)

It has nothing to do with the power of 2s, it is used to measure out 5 mL. Heart ^(talk) 14:06, 22 June 2021 (UTC)

as for being "the only unit that's out of the power of 2 rule", what about the yard?. ---Sluzzelin talk 14:07, 22 June 2021 (UTC)

Sluzzelin, I've never heard of the word yard under the definition "a unit a capacity". I've only heard of it meaning "a unit of length". Georgia guy (talk) 14:11, 22 June 2021 (UTC)

See Yard of ale. HiLo48 (talk) 07:43, 23 June 2021 (UTC)

I didn't know you were only talking about units of volume/capacity. ---Sluzzelin talk 14:41, 22 June 2021 (UTC)

But now you do, so can anyone answer my question?? Georgia guy (talk) 15:04, 22 June 2021 (UTC)

This is a matter of history and tradition, not mathematics. According to Teaspoon#Apothecaries' measure, it was once 4 teaspoons to the tablespoon, then the price of tea went down. --RDBury (talk) 16:37, 22 June 2021 (UTC)

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)

There is some "What does that have to do with the price of tea in China?" joke here, but I could not find it. Tigraan^{Click here for my talk page ("private" contact)} 08:28, 23 June 2021 (UTC)