Skip to content
Get started

Nobody moves more than two places

HardCombinatorics9 min

Eight runners finish a race in positions 11 to 88. In a rerun, each runner's new position differs from their old position by at most 22, i.e. the new order is a permutation π\pi of {1,…,8}\{1, \dots, 8\} with ∣π(i)−i∣≤2|\pi(i) - i| \le 2 for all ii. How many such permutations are there?

Show hints (3)+
  1. After filling positions 1..i1..i, which values must already be used?
  2. The state is which two of {i−1,i,i+1,i+2}\{i-1, i, i+1, i+2\} are used: 6 states.
  3. Band 1 gives Fibonacci; band 2 needs the 6-state transfer.

Answer

Reveal answer →

400

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions