Ponder This

August 2021 - Challenge

<< July August

Let's say that the Olympics just introduced a new sport - "Coin Toss Battle Royale". In this sport, a group of n players takes turns tossing coins (first player 1, then 2, etc., up to player n, and then starting over from 1). Each time "heads" comes up, the player selects one of the other players and removes him from the game. The winner is the last player remaining.

To make things interesting (but not fair), the coins are biased. The input for each game is a vector C = (p_1, p_2, \ldots, p_n), giving each player the probability for "heads" to come up for his or her coin. Assume all probabilities are different.

Assume also that all players are perfectly rational - they always choose which player to remove in a way that maximizes their chance to win. If two players or more can be chosen according to this criterion, the player chooses the one whose next turn is closer.

For example, if C = (0.25, 0.5, 1), then the chances for success for the respective players are approximately W = (0.29375, 0.425, 0.28125). Here we see that Player 2 has a better chance to win than Player 3, although Player 3 has the better coin.

When ordering players according to the probability of their coin, we obtain a permutation \sigma_C. When ordering them according to their probability of success, we obtain a permutation \sigma_W. We call an input C fair if \sigma_C = \sigma_W.

In the above example, \sigma_C = (1,2,3) and \sigma_W=(2,3,1), so C is not fair.

Another example: for C = (0.5, 0.2, 0.05, 0.85, 0.1), we obtain success probabilities of approximately W=(0.205, 0.196, 0.178, 0.238, 0.183), so C is fair since \sigma_C=\sigma_W=(4,3,1,5,2)

Your goal: Find a fair C for n=6.

A bonus "*" will be given for finding a fair C for n=8.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com