UVA 10037: Bridge

Created at 2016-05-07T03:16:20.000Z
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: