If an expression has two variables, it is symmetric if the expression stays the same when we swap the two variables. If an expression has three variables, it is symmetric if the expression stays the same when we swap any of the two variables. Symmetry is an extremely powerful tool in solving a variety of counting, probability, algebra, and geometry problems.
Problem 4‑16
«« Suppose that you are blindfolded 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 to guarantee both piles have an 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 
coins in the other. If
there are m coins in the first pile with heads up, there must be 
coins in the second
pile with heads up. We also know that there are 
coins in the first pile
with tails up. We clearly cannot guarantee that 
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 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 
. 
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.
Problem 4‑17
Mislabeled bags: You are given three bags of fruits. One has apples in it; one has oranges in it; one has a mix of apples and oranges in it. Each bag has a label on it (apple, orange, or mix). Unfortunately, your teacher tells you that ALL bags are mislabeled. Develop a strategy to identify the bags by taking out a minimum number of fruits. You can take any number of fruits from any bag.[19]
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’s
explain it in detail: If you pick a fruit from the bag with the orange label
and it’s an apple (orange 
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 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. 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 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.
Problem 4‑18
Solution: For the strategy to work, one wise man—let’s call him the spokesman—will state that everyone 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. 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 already 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.
Problem 4‑19
«« Poisonous wine: You’ve got 1000 bottles of wines for a birthday party. Eleven hours before the party, the winery sent you an urgent message that one bottle of wine was poisoned. You happen to have 10 lab mice that can be used to test whether a bottle of wine is poisonous. The poison is so strong that any amount will kill a mouse in exactly an hour. But before the death in an hour, there are no other symptoms. How do you identify the poisoned bottle?
Solution: If there is no time limit, we can feed a mouse a sip from a bottle, wait for an hour to see what happens. If the mouse dies from the poison, the bottle is identified. Otherwise, we move to the next bottle. In computer science, this approach is called a sequential search or a linear search. The reason why it is called a linear search is that each time it eliminates one element in the list until the match is found. The max time required to find a match grows linearly with the number of elements in the list. In this case, a linear search requires up to 1000 hours, and we have only eleven hours. Therefore, the approach does not work.
A different approach is a binary
search, in which case we group the elements in the list to two groups and
eliminate half of the elements in each test. The max time require to find a
match in 
elements is 
. For our problem, we
can start by splitting the 1000 bottles to two groups of 500 bottles (A and B).
We take a tiny amount from each bottle in group A, combine them, and feed the
wine to a mouse. If the mouse dies in an hour, we know that the poisoned bottle
is in group A; if the mouse lives in an hour, we know that the poisoned bottle
is in group B. Similarly, we can then split the subgroup identified in the
first step to two groups and repeat the process. For each test (hour), we can
eliminate half of the bottles in the subgroup, which allows us to identify the
poisoned bottle for up to 
bottles using 10 tests
in 10 hours.
Problem 4‑20
««« Poisonous wine 2: You’ve got 1000 bottles of wines for a birthday party. Two hours before the party, the winery sent you an urgent message that one bottle of wine was poisoned. You happen to have 10 lab mice that can be used to test whether a bottle of wine is poisonous. The poison is so strong that any amount will kill a mouse in exactly an hour. But before the death in an hour, there are no other symptoms. How do you identify the poisoned bottle?
Solution: This is a
more difficult version of the previous problem. Because we only have two hours,
we cannot run the binary search sequentially. In order to identify the poisoned
wine in two hours, we have to run all 10 binary tests simultaneously.
Nevertheless, the binary search idea still applies. Since we have 10 mice, it
is possible to run 10 binary tests simultaneously. All integers between 1 and
1000 can be expressed in 10-bit binary format. For example, bottle 1000 can be
labeled as 1111101000 since 
.
Now let mouse 1 take a sip
from every bottle that has a 1 in the first bit (the lowest bit on the right);
let mouse 2 take a sip from every bottle with a 1 in the second bit; …; and,
finally, let mouse 10 take a sip from every bottle with a 1 in the 10th bit
(the highest bit). One hour later, if we line up the mice from the highest to
the lowest bit and treat a live mouse as 0 and a dead mouse as 1, we can
backtrack the label of the poisonous bottle. For example, if the 6th, 7th, and
9th mice are dead and all others are alive, the line-up gives the sequence
0101100000, and the label for the poisonous bottle is 
[19] The problem struck me as a word game when I first saw it. But it does test a candidate’s attention to details, besides his/her logic reasoning skills.