In the Robot Swimming Trials, 3N identical robots compete for N equivalent spots in the finals by swimming N races. Each robot precommits to spending a certain amount of its fuel in each race. After all the races are run, the spots in the finals are given to the winners of the races, moving from the fastest winner to the slowest. (Once a robot wins a race, it is ineligible to win another race.) A robot’s speed is strictly increasing in the amount of fuel it spends, and ties are broken by randomly choosing the winner among the robots that have spent the same amount of fuel. Each robot's sole objective is to maximise its own probability of making the finals (that is, of winning some race).
Mathematically speaking, the 3N robots each submit a strategy, which is an N-tuple of nonnegative real number “bids” summing to 1, representing the fuel burned in each of the N races. The winners are then determined as follows:
- Winners are found by starting at the highest bid across all races and all robots and working down.
- Whenever the current highest bid belongs to a robot that has not yet won, placed in a race that has no winner yet, that robot wins that race.
- Ties: when several remaining bids share the same value (whether in the same race or in different races), they are considered one at a time in a uniformly random order, independent of everything else.
- Once a robot wins a race, its other bids are deleted. Once a race has a winner, all other bids in that race are ignored.
- Every bid counts as an entry in its race, including a bid of 0. In particular, a bid of 0 can win a race if no still-eligible robot has a higher bid there. Every race ends up with a winner, so we are guaranteed to get exactly N distinct qualifiers for the finals.
For example, suppose N=3 and the 3N=9 robots submit their strategies as
| Robot | Race 1 | Race 2 | Race 3 |
|---|---|---|---|
| Automatonya | 0.6 | 0.1 | 0.3 |
| Botty | 0.6 | 0.3 | 0.1 |
| Chroma | 0 | 1 | 0 |
| Data | 0.3 | 0.5 | 0.2 |
| Electro | 0.2 | 0.8 | 0 |
| Fernandroid | 0.4 | 0.5 | 0.1 |
| Gregulator | 0.5 | 0.5 | 0 |
| Hannanobot | 0 | 0.9 | 0.1 |
| IO | 0.2 | 0.7 | 0.1 |
The second race gets resolved first because Chroma’s bid of 1 is the highest overall, and Chroma is declared the winner of that time trial. Next, the first race is resolved because 0.6 is the highest remaining bid (we ignore the 0.9, 0.8, and 0.7 in the second race because it already has a winner). We flip a fair coin to determine who is the winner between Automatonya and Botty; say that Automatonya gets lucky and is declared the winner. Then the third race is decided, and Data is declared the winner, because 0.2 is the highest bid among robots that have not yet won (Automatonya’s 0.3 is ignored).
Over the storied history of the Robot Swimming Trials, the metagame settled into what was widely believed to be the Nash equilibrium: each robot picks one of the N races uniformly at random, independently of the others, and puts all of its fuel (a bid of 1) on it, bidding 0 on every other race. Let’s call this the discrete strategy. However, rumors are circulating that this conventional wisdom is not entirely accurate: for a large enough N, the discrete strategy is not the Nash equilibrium. Here "the discrete strategy is a Nash equilibrium" means: when all the other 3N-1 robots play the discrete strategy, no single robot can achieve a strictly higher probability of making the finals by switching to any other strategy (pure or randomised). It fails to be a Nash equilibrium exactly when some such strictly profitable deviation exists. You’ve been tasked to find two pieces of information:
What is the smallest N for which the trial does not have the discrete strategy as the Nash equilibrium?
For this N, if the other 3N-1 robots naively play the discrete strategy and your robot plays optimally (exploiting this knowledge of your opponents’ strategies), with what probability p will you make the finals? Give p rounded to 7 significant figures.
Submit two numbers, in this order: N, p.