Information Compression

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 \(2\). But \( 2 \) 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. \(_\square\)

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.

Problem-solving ideas:
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 \( 24 \) 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 \( 24 \) 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 \( 3^n \), where \( n \) is the number of weighings, so \( 3^n \ge 24\), so \( n \ge 3 \). 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 \(A\) through \( L \). Now weigh group \(ABCD\) against group \(EFGH.\) The three cases split the outcomes into three groups of eight each. If \( ABCD \) is heavier, then the eight outcomes are the four where one of \( A,B,C,D \) is heavy, and the four where one of \( E,F,G,H \) is light. The eight outcomes in the case where \( ABCD \) is lighter are similar but reversed, and the eight outcomes in the case when they balance are that one of the four coins \( I,J,K,L \) is either heavy or light.

If the coins in the first weighing balance, the second weighing should be \( IJ \) vs. \( AK \). If they balance, then \( L \) is the odd coin, and weighing it against \( A \) determines whether it's heavy or light. If \( IJ \) is heavier, then either \( I \) or \( J \) is heavy or \( K \) is light. To determine which of these three is true, weigh \( AI \) vs. \( BJ \). The same thing applies with "heavy" and "light" reversed if \( IJ \) is lighter.

Notice that the second weighing split the \( 8 \) outcomes into groups of \( 3,3,\) and \( 2 \), which is the optimal division.

If (without loss of generality) \( ABCD \) is heavier, weigh \( ABE \) against \( CDF \) next. If they balance, then either \( G \) is light or \( H\) is light, and the third weighing of \( G \) vs. \( H \) will determine which. If \( ABE \) is heavier, then either \( A \) is heavy, \( B \) is heavy, or \( F \) is light, and we can weigh \( AI \) vs. \( BJ \) to determine which. A similar idea applies if \( CDF \) is heavier. Again, the weighing splits the eight outcomes into groups of \( 3,3,\) and \( 2 \).

The procedure described here will solve the problem with three weighings, which has been shown to be the minimum possible; so the answer is \( 3 .\) \(_\square\)

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.

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 \( 50\% \). So for the players to win more than \( 50\% \) 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.

Problem-solving ideas:
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 \( n \) prisoners. The warden has many hats of \( n \) 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 \( n \) 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 \( n^n \) of the different outcomes (counting them is step 1). Each prisoner has a \( 1/n \) chance of guessing correctly, and there are \(n\) 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 \( n^n \) 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 \( n \) colors suggests looking mod \( n\) somehow. Suppose we relabel the colors \( 0,1,2,\ldots, n-1\). Then prisoner \( i\) can guess that the sum of the hats (including his) is \( i \) mod \( n\). That will translate to a unique hat color guess; if the sum of the hats that the prisoner sees is \( j \), then the prisoner guesses that his hat color is \( j-i \) mod \( n \). And exactly one prisoner will be right about the sum mod \( n\), so exactly one prisoner will guess the right hat color. So the probability that they go free is \(1\).

As in the coin problems, the point is that a global consideration of bounds and sizes gives a blueprint for constructing the best strategy. \( _\square \)

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.

Problem-solving strategies:
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 \(100\) 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 \( 99.5 \) out of \( 100 \) prisoners; the first prisoner has no information about his hat and will survive \( 50\% \) 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 \( 2 \). Suppose the prisoner at the very back (call him #\(1\), the prisoner in front of him #\(2,\) 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 #\(1\) says red, implying he sees an odd number of red hats in front of him, then #\(2\) 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 #\(3,\) except he will have to take into account what #\(1\) and #\(2\) said.

Unfortunately, this means #\(1\) has a \(50\)% chance of survival but it guarantees everyone else's survival. So all \(99\) of them are guaranteed to survive, which gives the overall expected survival rate of \(99.5\)% that we previously identified as the best possible. \(_\square\)