Legend has it that in a police station in the old west a group of six bandits tried to bribe the Sheriff in charge of the place with six gold coins to free them, the Sheriff was a very honest person so to prevent them from continuing to insist With the idea of bribery, he sat the bandits around a table and proposed the following:
- "Initially the leader will have the six gold coins, in each turn one of you can pass coins to the adjacent companions, but each time you do so you must pass the same amount of coins to each of your neighbors. If at any time they all manage to have the same amount of coins so I will let them go free. "
The bandits accepted and began to play.
Show that regardless of what moves the bandits make, they cannot win.
Problem 1554
Official solution
1. Initial Setup and Coloring:
- We start by coloring the bandits alternately in black and white around the table. Let's denote the bandits as , where stands for black and stands for white.
- Initially, the leader (let's assume ) has all 6 coins.
2. Observation of Coin Distribution:
- The key observation here is to track the parity (odd or even nature) of the number of coins held by the black and white bandits.
- Initially, the black bandits have 6 coins (since has all 6 coins), and the white bandits have 0 coins.
3. Coin Passing Rule:
- When a bandit passes coins to their adjacent neighbors, they must pass the same number of coins to each neighbor.
- This means if a bandit passes coins, they pass coins to the left neighbor and coins to the right neighbor.
4. Effect on Parity:
- Consider the effect of a single move on the parity of the number of coins held by black and white bandits.
- If a black bandit passes coins, they pass an even number of coins in total (since they pass the same number to two neighbors). This does not change the parity of the total number of coins held by black bandits.
- Similarly, if a white bandit passes coins, they also pass an even number of coins in total, which does not change the parity of the total number of coins held by white bandits.
5. Invariant Property:
- The total number of coins held by black bandits remains even throughout the game because it starts even (6 coins) and each move preserves the parity.
- For the bandits to win, each bandit must have exactly 1 coin, which means each black bandit must have 1 coin and each white bandit must have 1 coin.
- However, if each black bandit has 1 coin, the total number of coins held by black bandits would be 3, which is odd.
6. Conclusion:
- Since the total number of coins held by black bandits must always be even, it is impossible for each black bandit to end up with exactly 1 coin.
- Therefore, it is impossible for all bandits to have the same number of coins at any point in the game.