A criminal is planning an escape across a well-guarded bridge, which has a series of 9 guards, who each require a bribe of one coin in order to pass by them in either direction.
The criminal can keep a stash of coins in the area before the guards and between each guard. However, he can only carry 4 coins when approaching or passing any guard, in order to remain stealthy and not alert the other guards.
For example, if he starts with 6 coins, he can bring 4 with him to bribe the first guard, and end up with 3 coins in between the first and second guards.
How many coins does the criminal need to bring to the bridge in order to successfully pass by all 9 guards?
Solution
87 gold coins
On the last trip past any guard, it costs him 1 coin to bring up to 3 coins. On any resupply trip prior to that, he needs to pass the guard and then come back, so it costs him 2 coins to bring 2 coins.
So let’s say the stash of coins needed after a guard is x. The stash of coins needed before that guard would be x + 1 + (x – 3 rounded up to the next multiple of 2).
Number of coins he needs to stash before each guard:
- Last: 1
- 2nd last: 2
- 3rd: 3
- 4th: 4
- 5th: 7
- 6th: 12
- 7th: 23
- 8th: 44
- 9th: 87