The person in the rear of the line announces the “red” if he sees an even number of red hats in front of him and “blue” if the number is odd.  He’ll be right about his own hat 50% of the time.  There’s no help for that as he has no information at all.  But from this, all future prisoners know with certainty the color of their own hat!  Here’s how:

If the person in the rear says “red,” number nine knows that he saw an even number of red hats.  If he also sees an even number of red hats, he knows that his own hat must be blue.  Likewise, if he sees an odd number of hats, the only way for ten to have seen an even number of red hats is if his own hat is read.

By keeping track of each answer and the change between even / odd indicated by the answers, each person can correctly guess the color of his own hat for a total of 95% success.

Interestingly, this works even if the guards know what the prisoners are up to.  Unlike the hat problem in GB where the hat placers can make failure 100% likely knowing the strategy by cheating and placing hats of all the same colors on the heads of the players, in this setup, the strategy works not only on random placement but also on malicious placement.

The hint offered on twitter was to think about “parity.”  When hiring computer programmers I would sometimes offer this as an interview questions and often the people who got it would answer me with this one word and we’d move on.  It refers to parity bits in some communication protocols on computers.  When you send information over the wire, the signal may occasionally be distorted.  Parity bits are an approach to self-correction.  Suppose you send through a block of 1024 bits, 1’s and 0’s.  Suppose that you use 1023 for data and in the last bit, called a parity bit, you send 1 of the there are an even number of 1’s in the other bits, and 0 otherwise.  The receiving party can then check to make sure that this works out.  If a bit got flipped, you can request re-transmission of that block.  Of course, two errors might give you a false positive here, but if you know about how often errors occur, you can choose the size of the block you send such that errors occur as rarely as you like (with an increased cost of transmission because of parity bits.)

Though czarrandy and others provided the distance between the cities, I’d like to show a way that you can work the problem.

We want to work out an equation that explains the amount of time traveled each  downhill, level and uphill in terms of the distances involved.

How long does it take to travel a particular distance at a particular rate?  Take the uphill portion as an example.  At 56 mph, you travel 1 hour / 56 miles or n hours / x miles for any given distance x.  So:

1/56 = n / x

Solve for n (hours) and you get:

x/56 hours traveled for distance x.

Do something similar for the level distance (call that y) and the downhill distance (call that z) and you get this equation for the time traveled in terms of the three distances traveling from A to B in 4 hours:

x/56 + y/63 + z/72 = 4

For the trip back, where uphill becomes downhill and vice versa, we get:

z/56 + y/63 + x/72 = 4 2/3 or 14/3

If we could solve for x, y and z, we would get our answer, but generally there will not be a unique solution for two equations with three unknowns.  But in this case, what we need is the value of x+y+z , which we can attempt to extract that from the equations.

First, add the two equations together and get:

x/56 + x/72 + y/63 + y/63 + z/56 + z/72 = 26/3

To collect the terms, multiply both sides by the least common multiple of the denominators, which is 504, and we get:

9x + 7x + 8y + 8y + 9z + 7z = 4368
16x + 16y + 16z = 4368
16(x+y+z) = 4368
x+y+z = 273

for 273 miles each way.  Notice that what we did was to add the equations up to get a value for the round trip, which might have been a first intuitive step if you happened to think of it.

Now… it was very lucky that we were able to nicely factor out that 16 in order to solve for x+y+z.  This won’t always be the case!  The three speeds were chosen carefully so that this would work out.  Consider if we used some other randomly chosen values:

Uphill: 50 mph
Level: 60 mph
Downhill: 70 mph

Leave the times the same, so:

x/50 + y/60 + z/70 = 4
x/70 + y/60 + z/50 = 14/3

or x/50 + x/70 + y/60 + y/60 + z/70 + z/50 = 26/3

Multiply by the least common multiple of the denominators, 2100, and get:

42x + 30x + 35y + 35y + 30z + 42z = 18200
72x + 70y + 72z = 18200

As you can see, there isn’t going to be any way to factor out x+y+z to get a unique total distance.  You could experiment to demonstrate that you can pick values for x, y and z that satisfy the equation and for which x+y+z will differ.

The final question that interested me is how to identify the cases where there does turn out to be a solution.  From the process we just followed, you can see that you want the final coefficient of the x and z terms, or the uphill and downhill time traveled, which will always be equal to each other, to also be equal to the coefficient of the y term or the time traveled level.

Since we’ve added the two equations from the round trip, the meaning of these terms is the time taken to travel round-trip over a slanted piece of road.  So in English, in order to have a unique solution to the problem, the speeds must be specially selected such that the time it takes to travel round-trip over a slanted piece of road must be the same as the time it takes to travel over a level piece of road.

I got this problem originally from Nick’s Mathematical Puzzles. There are a lot of neat puzzles on the site to enjoy.