Information compression is a technique used in logic puzzles which require one to compress information to communicate effectively. Typical examples of this type of problems include finding oddly weighted coins using a balance and a minimal number of weighings, and people being lined up with their hats on their heads, where some or all of them have to guess their hat color correctly in order to survive.
When solving logic puzzles, it is often useful to think combinatorially: consider the size of the space of possible outcomes, and then to consider how those outcomes can be distinguished given the tools of the problem. This kind of analysis will generally give some bounds on possible solutions, but will often point the way toward a successful solution as well.
There are eight identical-looking coins; one of these coins is odd and is known to be heavier than the other coins. What is the minimum number of weighing needed to identify the fake coin with a two-pan balance scale without weights?
Select from the given coins two groups of three coins each and put them on the opposite cups of the scale. If they weigh the same, the fake is among the remaining two coins, and weighing these two coins will identify the heavier fake. If the first weighing does not yield a balance, the heavier fake is among the three heavier coins. Take any two of them and put them on the opposite cups of the scale. If they weigh the same, it is the third coin in the heavier group that is fake; if they do not weigh the same, the heavier one is the fake. Thus the answer is at most . But is the minimum number as well: weighing only gives meaningful information if the number of coins on each side is balanced, and it's easy to check that one weighing of two groups of one, two, three, or four coins against each other will not always find the heavier coin.
Note that the first weighing splits the eight possible outcomes into three groups: if they weigh the same, there are two possibilities, and if one is heavier, there are three possibilities on either side.
1. Count total outcomes.
2. Consider how the steps in a process divide the outcomes into groups.
3. Bound the number of steps.
4. Construct a process that comes as close to the bound as possible.
The following more difficult problem is an example of these ideas in practice.
There are twelve identical-looking coins; one of these coins is odd and is known to be either heavier or lighter than the other coins. What is the minimum number of weighings, with a two-pan balance scale without weights, needed to identify the coin and whether it is heavier or lighter?
Instead of diving into multiple cases, first consider the process. At each step we choose some coins and weigh them. There are three cases: the left side is heavier, the right side is heavier, or they balance. How many distinct outcomes are there at the beginning of the problem? The solution space has distinct outcomes: any one of the twelve coins can be the odd coin, and it can be heavier or lighter. (This is step 1.)
These outcomes are split into three groups based on the three cases. The goal of the problem is to split the outcomes into groups based on the results of weighings, until the groups contain only one outcome each. The number of different groups is at most , where is the number of weighings, so , so . This shows that it will take at least three weighings to identify the coin. (This is steps 2 and 3.)
This analysis also gives a clue as to the optimal procedure (step 4). At each stage, try to arrange the weighings so that the three cases split the possible outcomes into groups of roughly equal size.
For simplicity, label the coins through . Now weigh group against group The three cases split the outcomes into three groups of eight each. If is heavier, then the eight outcomes are the four where one of is heavy, and the four where one of is light. The eight outcomes in the case where is lighter are similar but reversed, and the eight outcomes in the case when they balance are that one of the four coins is either heavy or light.
If the coins in the first weighing balance, the second weighing should be vs. . If they balance, then is the odd coin, and weighing it against determines whether it's heavy or light. If is heavier, then either or is heavy or is light. To determine which of these three is true, weigh vs. . The same thing applies with "heavy" and "light" reversed if is lighter.
Notice that the second weighing split the outcomes into groups of and , which is the optimal division.
If (without loss of generality) is heavier, weigh against next. If they balance, then either is light or is light, and the third weighing of vs. will determine which. If is heavier, then either is heavy, is heavy, or is light, and we can weigh vs. to determine which. A similar idea applies if is heavier. Again, the weighing splits the eight outcomes into groups of and .
The procedure described here will solve the problem with three weighings, which has been shown to be the minimum possible; so the answer is
You have a unique three-pan balance with which to measure the weight of coins. This balance has three pans, as its name implies. Each pan can be loaded with any number of coins after which you may press a button to turn the balance on. If all three pans have different weights, the scale will indicate to you the pan that has the 2 heaviest weight (so the pan that is not the heaviest nor lightest). However, if any two pans have the same weight, then the scale will read "ERROR" (because there is no unique 2 heaviest weight). After that, the balance switches off, and you can unload and reload the pans again for the next use.
In a pile of 64 coins, all but one of them have the same weight; the odd one is heavier. You want to identify this heavier coin in as few button presses (uses of the balance) as possible. With the best strategy, how many button presses do you need in the worst case?
One way to summarize the problem-solving ideas in the previous section is that giving a lower bound for the "difficulty" of the solution made the best solution clearer. Here is a similar example in a different context.
Three people enter a room and have a red or blue hat placed on their head. They cannot see their own hat, but can see the other hats. The color of each hat is purely random. All hats could be red, or blue, or 1 blue and 2 red, or 2 blue and 1 red. They need to guess their own hat color by writing it on a piece of paper, or they can write "pass." They cannot communicate with each other in any way once the game starts. But they can have a strategy meeting before the game. If at least one of them guesses correctly they win $50,000 each, but if anyone guesses incorrectly they all get nothing. Using optimal strategy, what is the maximal percentage chance of winning that can be achieved? E.g., if you think the answer is 50 % chance of winning, type in your answer as 50.
Hint: Note that if the game is repeated many times, and we tabulate the total number of right guesses and wrong guesses, these numbers will tend to be roughly equal, because the chance of any one particular guess being correct is . So for the players to win more than of the time, their strategy must involve them all guessing wrong when they are wrong, and only one guessing right when they are right. This way, the wrong guesses are clustered together and the right guesses are spread out.
1. Think combinatorially; count outcomes.
2. Consider the effect of multiple trials with every outcome represented equally often. Note that individual guess probabilities are strategy-independent.
3. Use the individual probabilities to decide how the guesses would be distributed between the various trials "in an ideal world."
4. Construct a strategy that distributes those guesses accordingly.
Here is an example of these ideas in action.
This is a slightly modified version of this discussion.
Suppose there are prisoners. The warden has many hats of different colors in his closet. The warden tells the prisoners that he will pick a hat at random from his closet for each of the prisoners (he tells them the possible colors that the hats can have). Note that the hats he chooses might all be of the same color, or all different colors. Each prisoner can see everyone else's hat but not his or her own. Once the hats are put on, the prisoners are to guess their own hat color (by writing it on a piece of paper). The prisoners go free if at least one of them guesses correctly. There is no penalty for incorrect guessing.
The prisoners are given a short break to plan strategy. Once they are in the room, no communication or movement of any kind is allowed. What is the probability that they go free, if they play optimally?
As in the earlier hat problem, consider the total number of incorrect and correct guesses, if the trials are repeated over all of the different outcomes (counting them is step 1). Each prisoner has a chance of guessing correctly, and there are prisoners, so on average there will be one correct guess (step 2). Here the priority is the opposite of the above problem; the goal is to spread out the correct guesses evenly so exactly one prisoner guesses correctly in each of the different situations. If this can be done, the prisoners can guarantee that they go free in every case. (This is step 3.)
Looking at sums was useful in other problems, and the fact that there are colors suggests looking mod somehow. Suppose we relabel the colors . Then prisoner can guess that the sum of the hats (including his) is mod . That will translate to a unique hat color guess; if the sum of the hats that the prisoner sees is , then the prisoner guesses that his hat color is mod . And exactly one prisoner will be right about the sum mod , so exactly one prisoner will guess the right hat color. So the probability that they go free is .
As in the coin problems, the point is that a global consideration of bounds and sizes gives a blueprint for constructing the best strategy.
In many other logic puzzles, the difficulty is in successfully transmitting information given severe restrictions on the communication between participants. Sometimes the information is transmitted via pauses, where inferences can be drawn based on another participant's inaction. Other times, not every participant is perfectly rational; if every participant was perfectly rational, this would be known as K-level thinking.
Sometimes the severity of the restrictions on the transmittable amount of information helps to indicate the correct solution, in a similar way to the problems in the previous section. That is, the choice of strategies is so limited by the conditions of the problem that it can be used to give an upper bound on the success rate of any strategy.
1. Decide how much information can be transmitted between the participants.
2. Give an upper bound for the success rate of any strategy based on step 1.
3. Find a solution that is as close as possible to the bounds in the first two steps.
A stark raving mad king tells wise prisoners that he is about to line them up and place either a red or blue hat on each head. Once lined up, they must not communicate amongst themselves, nor attempt to look behind them, and nor remove their own hat. They will be able to see all the hats in front of them but not their own hat nor the hats behind them, although they will be able to hear the answers from all those behind them.
The king will start with the last prisoner in the back and ask, "What color is your hat?" The prisoner will only be allowed to answer "red" or "blue," nothing more. If the answer is incorrect then the prisoner will be executed. If the answer is correct then the prisoner may live but must remain absolutely silent. The king will then move on to the second last prisoner and repeat the question, and so on.
Before they are lined up, the king makes it clear that if anyone breaks the rules then all of them will die. While the prisoners consult each other for a few minutes before they line up, the king listens in to make sure they don't devise a plan to communicate anything more than their guess of red or blue.
What is the maximum expected number of men that can be guaranteed to be saved?
The very best possible expected survival rate has to be out of prisoners; the first prisoner has no information about his hat and will survive of the time, but the successive prisoners will each get at least one bit of information from the first prisoner's choice. Note that the prisoners can't simultaneously guarantee their survival and transmit any information about anything but their own hat color; if they know their hat color, their choice is forced. But hearing the hat color of each of the prisoners behind them will still help the prisoners in front. So each prisoner can transmit at most one bit of information.
The presence of one bit suggests that we look at hat colors mod . Suppose the prisoner at the very back (call him #, the prisoner in front of him # and so on) agrees that if he sees an odd number of red hats he calls out red, and if he sees an even number of red hats he calls out blue.
So for example, if # says red, implying he sees an odd number of red hats in front of him, then # counts the number of red hats in front of him. If he counts an even number of red hats he will know that he is wearing a red hat. On the contrary, if he counts an odd number of red hats in front of him, he will know he is wearing a blue hat. The same strategy goes for # except he will have to take into account what # and # said.
Unfortunately, this means # has a % chance of survival but it guarantees everyone else's survival. So all of them are guaranteed to survive, which gives the overall expected survival rate of % that we previously identified as the best possible.
You are asked to guess an integer between and inclusive.
Each time you make a guess, you are told either
(a) you are too high,
(b) you are too low, or
(c) you got it!
You are allowed to guess too high twice and too low twice, but if you have a guess that is too high or a guess that is too low, you are out.
What is the maximum for which you are guaranteed to accomplish this?
Clarification: For example, if you were allowed to guess too high once and too low once, you could guarantee to guess the right answer if , but not for . So, in this case, the answer would be .