Problem simplification

If the original problem is so complex that you cannot come up with an immediate solution, try to identify a simplified version of the problem and start with it. Usually, you can start with the simplest problem and gradually increase the complexity. You do not need to have a defined plan at the beginning. Just try to solve the simplest cases and analyze your reasoning. More often than not, you will find a pattern that will guide you through the whole problem.

Besides starting with a simplified version of the problem, we can also split the problem into two or more mutually exclusive cases and solve each individual case independently. This approach is called casework (as we have seen in the Counting chapter).

Screwy pirates: Five pirates looted a chest full of 100 gold coins. Being a bunch of democratic pirates, they agree on the following method to divide the loot:

The most senior pirate will propose a distribution of the coins. All pirates, including the most senior pirate, will then vote. If at least 50% of the pirates (3 pirates in this case) accept the proposal, the gold is divided as proposed. If not, the most senior pirate will be fed to a shark, and the process starts over with the next most senior pirate… The process is repeated until a plan is approved. You can assume that all pirates are perfectly rational; they want to stay alive first and to get as much gold as possible, second. Finally, being blood-thirsty pirates, they want to have fewer pirates on the boat if given a choice between otherwise equal outcomes.

How will the gold coins be divided in the end?

Solution: Chances are that you have not studied game theory, and this strategy problem may appear to be daunting. If the problem with 5 pirates seems complex, we can always start with a simplified version of the problem by reducing the number of pirates. Since the solution to 1‑pirate case is trivial, let’s start with 2 pirates. The senior pirate (labeled as 2) can claim all the gold since he will always get 50% of the votes from himself, and pirate 1 is left with nothing.

Let’s add a more senior pirate, 3. He knows that if his plan is voted down, pirate 1 will get nothing. But if he offers pirate 1 nothing, pirate 1 will be happy to kill him. Therefore, pirate 3 will offer pirate 1 one coin and keep the remaining 99 coins, so the plan will have 2 votes from pirates 1 and 3.

If pirate 4 is added, he knows that if his plan is voted down, pirate 2 will get nothing. Thus, pirate 2 will settle for one coin if pirate 4 offers one. Therefore, pirate 4 should offer pirate 2 one coin and keep the remaining 99 coins, and his plan will be approved with 50% of the votes from pirate 2 and 4.

Now we finally come to the 5-pirate case. He knows that if his plan is voted down, both pirate 3 and pirate 1 will get nothing. Therefore, he only needs to offer pirate 1 and pirate 3 one coin each to get their votes and keep the remaining 98 coins. If he divides the coins this way, he will have three out of the five votes: from pirates 1 and 3 as well as himself.

Once we start with a simplified version and add complexity to it, the answer becomes obvious. After the case of , a clear pattern has emerged, and we do not need to stop at 5 pirates. For any pirate case (n should be less than 99 though), the most senior pirate will offer pirates and each one coin and keep the rest for himself.

One hundred tigers and one sheep are put on a magic island that only has grass. Tigers can eat grass, but they would rather eat sheep. Assume A. Each time, only one tiger can eat one sheep, and that tiger itself will become a sheep after it eats the sheep. B. All tigers are smart and perfectly rational, and they want to survive. Will the sheep be eaten?

Solution: 100 is a large number, so again let’s start with a simplified version of the problem. If there is only 1 tiger (), surely it will eat the sheep since it does not need to worry about being eaten. How about 2 tigers? Since both tigers are perfectly rational, either tiger will do some thinking as to what will happen if it eats the sheep. Either tiger is probably thinking: if I eat the sheep, I will become a sheep. Then I will be eaten by the other tiger. To guarantee the highest likelihood of survival, neither tiger will eat the sheep.

If there are 3 tigers, the sheep will be eaten since each tiger will realize that once it changes to a sheep, there will be 2 tigers left, and it will not be eaten. Thus, the first tiger that thinks this through will eat the sheep. If there are 4 tigers, each tiger will understand that if it eats the sheep, it will turn to a sheep. Since there are 3 other tigers, it will be eaten. To guarantee the highest likelihood of survival, no tiger will eat the sheep.

Following the same logic, we can naturally show that if the number of tigers is even, the sheep will not be eaten. If the number is odd, the sheep will be eaten. For the case , the sheep will not be eaten.

Part A. One hundred prisoners are given a chance to be set free tomorrow. They are all told that each will be given a red or blue hat to wear. Each prisoner can see everyone else’s hat but not his own. The hat colors are assigned randomly, and once the hats are placed on top of the prisoners’ heads, they cannot communicate with one another in any form. The prisoners will be called out in random order, and the prisoner called out will guess the color of his hat. Each prisoner declares the color of his hat so that everyone else can hear it. If a prisoner guesses the color of his hat correctly, he is set free immediately; otherwise, he serves the remaining of his sentence.

They are given the night to come up with a strategy among themselves to save as many prisoners as possible. What is the best strategy they can adopt, and how many prisoners can they guarantee to free?[24]

Part B. What if there are 3 possible hat colors: red, blue, and white? What is the best strategy they can adopt, and how many prisoners can they guarantee to free?[25]

Solution: For part A, at least 99 prisoners can be freed. The key lies in the first prisoner, who can see everyone else’s hat. He declares his hat to be red if the number of red hats he sees is odd. Otherwise, he declares his hat to be blue. He will have a 1/2 chance of having guessed the color of his hat correctly. Everyone else can deduce his own hat color combining the knowledge whether the number of red hats is odd among 99 prisoners (excluding the first) and the color of the other 98 prisoners (excluding the first and himself). For example, if the number of red hats is odd among the other 99 prisoners, a prisoner wearing a red hat will see an even number of red hats in the other 98 prisoners (excluding the first and himself) and deduce that he is wearing a red hat.

The two-color case is easy, isn’t it? Now let’s consider the 3-color case. Despite the additional complexity, the answer is still that at least 99 prisoners will be freed. The difference is that the first prisoner now only has a 1/3 chance of freedom. Let’s use the following scoring system: red=0, green=1, and blue=2. The first prisoner counts the total score (s) for the rest of 99 prisoners and calculates . If the remainder is 0, he announces red; if the remainder is 1, green; 2, blue. He has 1/3 chance of being freed, but all the rest of the prisoners can determine their own scores (colors) from the remainder. Let’s consider a prisoner i among 99 prisoners (excluding the first prisoner). He can calculate the total score (x) of all the other 98 prisoners. Since and are all different, from the remainder that the first prisoner gives (for the 99 prisoners including i), he can determine his own score (color). For example, if prisoner i sees that there are 32 red, 29 green, and 37 blue in those 98 prisoners (excluding the first and himself). The total score of those 98 prisoners is 103. If the first prisoner announces that the remainder is 2 (green), then prisoner i knows his own color is green (1) since only among 103, 104, and 105.

Theoretically, we can apply a similar strategy to any number of hat colors. Surely, that requires all prisoners to have exceptional memory and calculation capability.