Bribing a Series of Guards

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

Leave a Reply

Your email address will not be published. Required fields are marked *