2.4 Application of Symmetry

Coin piles

Suppose that you are blind-folded in a room and are told that there are 1000 coins on the floor. 980 of the coins have tails up and the other 20 coins have heads up. Can you separate the coins into two piles so to guarantee both piles have equal number of heads? Assume that you cannot tell a coin’s side by touching it, but you are allowed to turn over any number of coins.

Solution: Let’s say that we separate the 1000 coins into two piles with $n$ coins in one pile and $1000-n$ coins in the other. If there are $m$ coins in the first pile with heads up, there 16 must be $20-m$ coins in the second pile with heads up. We also know that there are $n-m$ coins in the first pile with tails up. We clearly cannot guarantee that $m=10$ by simply adjusting $n$.

What other options do we have? We can turn over coins if we want to. Since we have no way of knowing what a coin’s side is, it won’t guarantee anything if we selectively flip coins. However, if we flip all the coins in the first pile, all heads become tails and all tails become heads. As a result, it will have $n-m$ heads and $m$ tails (symmetry). So, to start, we need to make the number of tails in the original first pile equal to the number of heads in the second pile; in other words, to make $n-m=20-m$. $n=20$ makes the equation hold. If we take 20 coins at random and turn them all over, the number of heads among these turned-over 20 coins should be the same as the number of heads among the other 980 coins.

Mislabeled bags

You are given three bags of fruits. One has apples in it; one has oranges in it; and one has a mix of apples and oranges in it. Each bag has a label on it (apple, orange or mix). Unfortunately, your manager tells you that ALL bags are mislabeled. Develop a strategy to identify the bags by taking out minimum number of fruits? You can take any number of fruits from any bags.⁸

Solution: The key here is to use the fact that ALL bags are mislabeled. For example, a bag labeled with apple must contain either oranges only or a mix of oranges and apples. Let’s look at the labels: orange, apple, mix (orange + apple). Have you realized that the orange label and the apple label are symmetric? If not, let me explain it in detail: If you pick a fruit from the bag with the orange label and it’s an apple (orange $\to$ apple), then the bag is either all apples or a mix. If you pick a fruit from the bag with the apple label and it’s an orange (apple $\to$ orange), then the bag is either an orange bag or a mix. Symmetric labels are not exciting and are unlikely to be the correct approach. So let’s try the bag with the mix label and get one fruit from it. If the fruit we get is an orange, then we know that bag is actually orange (It cannot be a mix of oranges and apples since we know the bag’s label is wrong). Since the bag with the apple label cannot be apple only, it must be the mix bag. And the bag with the orange label must be the apple bag. Similarly, for the case that apples are in the bag with the mix label, we can figure out all the bags using one single pick.

Wise men

A sultan has captured 50 wise men. He has a glass currently standing bottom down. Every minute he calls one of the wise men who can choose either to turn it over (set it upside down or bottom down) or to do nothing. The wise men will be called randomly, possibly for an infinite number of times. When someone called to the sultan correctly states that all wise men have already been called to the sultan at least once, everyone goes free. But if his statement is wrong, the sultan puts everyone to death. The wise men are allowed to communicate only once before they get imprisoned into separate rooms (one per room). Design a strategy that lets the wise men go free.

Solution: For the strategy to work, one wise man, let’s call him the spokesman, will state that every one has been called. What does that tell us? 1. All the other 49 wise men are equivalent (symmetric). 2. The spokesman is different from the other 49 men. So naturally those 49 equivalent wise men should act in the same way and the spokesman should act differently.

Here is one of such strategies: Every one of the 49 (equivalent) wise men should flip the glass upside down the first time that he sees the glass bottom down. He does nothing if the glass is already upside down or he has flipped the glass once. The spokesman should flip the glass bottom down each time he sees the glass upside down and he should do nothing if the glass is already bottom down. After he does the 49th flip, which means all the other 49 wise men have been called, he can declare that all the wise men have been called.