August 2021 - Challenge
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
Challenge:
01/08/2021 @ 12:00 PM EST
Solution:
04/09/2021 @ 12:00 PM EST
List Updated:
31/08/2021 @ 12:00 PM EST
People who answered correctly:
*Bertram Felgenhauer (3/8/2021 12:32 AM IDT)
*Keith Schneider (3/8/2021 2:00 AM IDT)
Daniel Chong Jyh Tar (3/8/2021 6:25 AM IDT)
*Liubing Yu (3/8/2021 11:43 AM IDT)
*Dan Dima (3/8/2021 12:07 PM IDT)
*Alper Halbutogullari (3/8/2021 1:59 PM IDT)
Guillaume Escamocher (3/8/2021 6:29 PM IDT)
*Uoti Urpala (4/8/2021 10:50 PM IDT)
JJ Rabeyrin (5/8/2021 10:10 PM IDT)
Giorgos Kalogeropoulos (6/8/2021 9:34 AM IDT)
Marco Bellocchi (6/8/2021 7:16 PM IDT)
*Walter Schmidt (7/8/2021 1:44 PM IDT)
*Bert Dobbelaere (7/8/2021 4:16 PM IDT)
*Tomer Vromen (7/8/2021 6:01 PM IDT)
Clive Tong (8/8/2021 12:00 PM IDT)
*James Dow Allen (7/8/2021 2:50 AM IDT)
*Dominik Reichl (8/8/2021 9:23 PM IDT)
Daniel Bitin (8/8/2021 10:55 PM IDT)
*David Greer (9/8/2021 1:55 PM IDT)
*Phil Proudman (10/8/2021 7:11 PM IDT)
Moning Zhang (11/8/2021 12:34 AM IDT)
Horváth Markó (11/8/2021 10:17 AM IDT)
Graham Hemsley (11/8/2021 10:31 AM IDT)
Marco Bellocchi (11/8/2021 4:05 PM IDT)
Latchezar Christov (11/8/2021 5:50 PM IDT)
Benjamin Lui (11/8/2021 6:15 PM IDT)
*Andreas Knüpfer (12/8/2021 12:04 AM IDT)
Ryan Rose (12/8/2021 2:17 AM IDT)
Radu-Alexandru Todor (16/8/2021 5:43 AM IDT)
*Gil Citro (16/8/2021 2:43 PM IDT)
*Harald Bögeholz (16/8/2021 3:30 PM IDT)
Todd Will (16/8/2021 5:27 PM IDT)
Joaquim Carrapa (17/8/2021 9:30 PM IDT)
Karl D’Souza (17/8/2021 10:29 PM IDT)
*Andreas Stiller (18/8/2021 1:59 AM IDT)
*Paul Revenant (18/8/2021 10:51 PM IDT)
*Tim Walters (20/8/2021 6:59 PM IDT)
Nir Paz (21/8/2021 7:16 PM IDT)
*Alfred Reich (23/8/2021 9:56 AM IDT)
*Vladimir Volevich (23/8/2021 5:37 PM IDT)
*Joaquim Carrapa (25/8/2021 3:56 AM IDT)
*Sean Egan (26/8/2021 8:23 AM IDT)
*Karl Mahlburg (28/8/2021 10:14 PM IDT)
*Yuping Luo (29/8/2021 11:46 AM IDT)
*Motty Porat (30/8/2021 2:43 AM IDT)
Wang Longbu (30/8/2021 5:02 AM IDT)
*Li Li (31/8/2021 7:37 AM IDT)
Shirish Chinchalkar (31/8/2021 2:56 PM IDT)
*Kang Jin Cho (31/8/2021 9:07 PM IDT)
*Reiner Martin (31/8/2021 10:14 PM IDT)