I had no idea how to achieve optimality, so I consulted two references about this problem:
Both references mentions that:
When the number of people is more than or equal to 4, the problem can be broken down into
- move slowest 2 people to the other side,
- repeat this until the number of people is less than 4.
Technically speaking, this "break down problem" is a crucial step to prove the optimality of the algorithm by induction, which is not obvious for me to understand intuitively.
So, I tried to formalize and prove a statement, but I failed. Here is some of notes about this.
Locally best strategy
Compositionality of best strategies
Rests are my crappy notes: