a puzzle that uses Gray code (photo by James Houghton)
1000 Freshmen
1000 freshman are lined up on Mass. Ave., all facing the river, each with either a red or green hat on. Starting with the freshman at the end farthest from the river--the only one who can see every hat but her own--and continuing up the line, how can they conspire to guess the color of their own hat making at most one mistake in the 1000 guesses?
The solution involves the use of a parity check.
Parity checking refers to the use of parity bits to check that data has been transmitted accurately. The parity bit is added to every data unit (typically seven or eight bits ) that are transmitted. The parity bit for each unit is set so that all bytes have either an odd number or an even number of set bits.
Assume, for example, that two devices are communicating with even parity (the most common form of parity checking). As the transmitting device sends data, it counts the number of set bits in each group of seven bits. If the number of set bits is even, it sets the parity bit to 0; if the number of set bits is odd, it sets the parity bit to 1. In this way, every byte has an even number of set bits. On the receiving side, the device checks each byte to make sure that it has an even number of set bits. If it finds an odd number of set bits, the receiver knows there was an error during transmission.
The sender and receiver must both agree to use parity checking and to agree on whether parity is to be odd or even. If the two sides are not configured with the same parity sense, communication will be impossible. (http://www.webopedia.com/)
In this case the parity can be calculated based upon the number of red hats by the first freshman in line, who shouts out red for even or green for odd. She may or may not get her own hat color correct (50% chance), but everyone else in line can calculate their hat color by summing the total number of times they hear "red" and how many red hats they see. If the sum is even, they shout green. If it is odd, they shout red.
Ant Trail
What is the minimum binary pattern a ant can leave to disambiguate direction along its trail?
The key here is to generate a binary code that repeats, but from which a direction can be determined no matter where you enter the sequence. 010011 is such a code, i.e., ...010011010011010011010011... How do we prove it is minimal?
Colombo's Gold
Janet asked, "If Colombo is in a room with bags of gold nuggets, where one bag contains fake gold, how can he tell, with a single weighing, which bag contains the fake gold? He knows how much a real gold nugget weighs and also how much a fake gold nugget weighs."
We know the following:
(a) The weight of gold, g; and
(b) The weight of the other metal, x.
First, let's assume n bags. For each bag numbered as i (i
goes from [1, n]) take i coins for the bag i. Thus, for bag
number 1 take one coin, for bag number 2 take two coins, ...., for bag number
n take n coins. If all of them were golden coins and we weight them
then the total weight w would be:
w=(n(n+1)/2)*g
but we know that i coins are not made of gold, then the total weight of
the coins is:
w+a= (n(n+1)/2)*g + i*(x-g)
Therefore:
i= a/(x-g).
The answer is then, bag i is the one with coins that are not made of
gold. (This assumes that there are more coins per bag than bags in the room.)
Prison Switcharoo
This is a classic puzzler that is modified from one on the CarTalk puzzle site ( http://cartalk.cars.com/Radio/Puzzler)
A warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'On' or the 'Off' position. [The switches both start in the 'Off' position.] The switches are not connected to anything.
"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none, either. Then he'll be led back to his cell.
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.'
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."
Here's the question: What is the strategy the prisoners devise?
The key to the solution is to designate one prisoner and one switch to be the "counters." If the counter switch is off and you've never turned it on, do so. Otherwise, toggle the other switch. Only the counter prisoner can switch the counter switch off. Eventually, everyone will have turned it on exactly once and the counter will have turned it off (n-1) times.
12 Coins
If you have twelve coins, one of which is false and either lighter or heavier than the others, how do you find it (and know its relative weight) after just three weightings?
The solution lies in a partitioning of the search space so that each weighing
tells us as much as possible and we don't waste time on things we already know.
Let's label the coins as: 1234, 5678, and 9ABC.
In the first weighing, we compare 1234 vs 5678.
If 1234 == 5768 then we know that the bad coin is one of 9ABC, so in the second
weighing, we compare 123 vs 9AB.
If 123 == 9AB then in the third weighing, we compare 1 vs C
If 1 < C then C is false and lighter.
If 1 > C then C is false and heavier.
if 123 < 9AB and 9 == A then B is false and heavier etc.
If 1234 > 5678, then in the second weighing we want to compare 125 vs 34A
If 125 == 34A, then we are left with 6 vs 7 for the third weighing.
If 125 > 34A then we need to compare 1 vs 2. Else 3 vs 4. etc.
Gray Code
Is there a way of counting binary numbers such that only one bit is flipped between successive numbers?
0, 1, 11, 10, 110, 111, 101, 100, 1100, 1101, ...
(See
http://mathworld.wolfram.com/GrayCode.html for a detailed discussion.)
a puzzle that uses Gray code
(photo by James Houghton)
White mates in two
Note that advancing the pawn from c6 to c7 does not lead to a solution because Black can move b5 to b4. If White's next move is to a8 x a7, the Black king can then capture the White rook (a6 x a7). If White moves to c8, the Black king captures the White pawn (a6 x a5).
Eight Queens
Place eight queens on a chessboard such that they don't attach each other.