We are given that our opponents are all playing the discrete strategy, which means they will all be independently choosing a race uniformly randomly and devoting all of their fuel to it. Since we are searching for the smallest N so that the discrete strategy is not optimal, we will be playing something other than this strategy. This means we won’t be assigning all of our fuel to any one race, but since all of our opponents are “bidding” 1 or 0 on every race, the best non-discrete strategies will involve bidding a nonzero amount on every race, which will beat all of the 0 bids (but lose to all of the 1 bids). So without loss of generality we can assume the strategy of bidding 1/N on every race, we can call this the uniform strategy.

Now we need to compute the smallest N for which this beats out the discrete strategy. The uniform strategy wins a race exactly when none of the 3N-1 other discrete-strategy-playing robots select that race for their fuel. It’s straightforward to compute this probability for a single race, (1-1/N)^(3N-1). But the assignment of discrete strategies is not independent across the N races! Assuming they were would give an incorrect answer of N=9 and p=0.350245…

Also, these events of winning a race with the uniform strategy are not disjoint across the N races! Assuming they were would give an incorrect answer of N=8 and p=0.370916…

Instead, a nice recursion could be found to count up the number of arrangements of the 3N-1 other players that left at least one race undefended. For example, let P(R,m,n) equal the probability that, if we need to assign R robots to (m+n) total races, m of which already have a robot assigned and n of which don’t, we will eventually assign at least one robot to all (m+n) races. Then assigning the next robot to a race uniformly randomly implies the recursion:

P(R,m,n) = (m * P(R-1,m,n) + n * P(R-1,m+1,n-1))/(m+n).

Along with the boundary values

P(R,m,0) = 1 (all races have been assigned at least one robot)

and for n>0,

P(0,m,n) = 0 (we’ve run out of robots and we still have an unassigned race),

we can compute values of P efficiently by induction. We want to find the smallest N such that

1 - P(3N-1,0,N) > 1/3,

which occurs at N=8 and p=0.334578….

Congrats to this month’s solvers who computed the correct size and probability of winning the swimming trials!