PROJECT EULER · #0597
Torpids
-
A division consists of
boats (typically 13), placed in order based on past performance. - All boats within a division start at 40 metre intervals along the river, in order with the highest-placed boat starting furthest upstream.
- The boats all start rowing simultaneously, upstream, trying to catch the boat in front while avoiding being caught by boats behind.
- Each boat continues rowing until either it reaches the finish line or it catches up with ("bumps") a boat in front.
-
The finish line is a distance
metres (the course length, in reality about 1800 metres) upstream from the starting position of the lowest-placed boat. (Because of the staggered starting positions, higher-placed boats row a slightly shorter course than lower-placed boats.) - When a "bump" occurs, the "bumping" boat takes no further part in the race. The "bumped" boat must continue, however, and may even be "bumped" again by boats that started two or more places behind it.
-
After the race, boats are assigned new places within the division, based on the bumps that occurred. Specifically, for any boat
that started in a lower place than , then will be placed higher than in the new order if and only if one of the following occurred:-
bumped directly -
bumped another boat that went on to bump -
bumped another boat, that bumped yet another boat, that bumped - etc
-
Suppose that, in a particular race, each boat
Let
For example, with
| Bumps occurring | New order | Permutation | Probability |
|---|---|---|---|
| none | |
even | |
| |
|
odd | |
| |
|
odd | |
| |
|
even | |
| |
|
odd | |
Therefore,
You are also given that
Find
Write-up coming later
The complete problem is available here. An approach, code, and answer will be added later.