The Entertainment Blockbuster of Summer 2009!

That is: http://tr.im/uFEL

We said during the most recent podcast that we’d offer the answer to the ending puzzle on the website.

Twitter user @snoble posted a hint on #mathfactor that points to the right answer.

First, I’ll review the problem.  You and nine other prisoners will be lined up in the morning front to back.  Each of you will have either a blue or red hat placed upon your head.  Each person can see all the hats on the heads of people in front of him, but not the color of his own or of any of the people behind.

The guards will then proceed to the rear of the line and ask that person the color of the hat on his own head.  He must guess and if he guesses wrong, sadly, he’ll be shot.  Either way, the guard then proceeds to the number nine position and repeats through all of the other prisoners.

Knowing that this will happen and with a night to plan, what strategy can the prisoners develop to maximize their expected survival rate?

[spoiler]During the show, I suggested a 75% solution and claimed that you can do much better.  In fact, 95% of the prisoners should survive.  Here’s how it is done.

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.)

[/spoiler]

Man, what is it with puzzlers and prisoners? Jeff Yoak lines ’em up and the stakes are high in this week’s puzzle. 

Also, we are now twittering at MathFactor; each of the authors has an account of his own; mine is CGoodmanStrauss. You can tag solutions and comments with #mathfactor. See you there!

Standard Podcast Play Now | Play in Popup | Download

How can three people, each required to guess the color of hat on their head, strategize and maximize the chances they’ll all be right?

Standard Podcast Play Now | Play in Popup | Download

Jeff Yoak discusses the mathematical – and non-mathematical – nature of poker. Sitting at the table led him to wonder: Which numbers, precisely, are the sum of consecutive integers, and in how many ways?

Standard Podcast Play Now | Play in Popup | Download

The Math Factor podcast catches up with Jeff Yoak, an author on the Math Factor website, to discuss his fantastic Find-the-Gold-Coin puzzle.

Standard Podcast Play Now | Play in Popup | Download

In working out the proof for World of Britain I came across a paradox.  Maybe smarter Math Factorites can help me out?  My sanity could depend on it.

In the puzzle you have five different tasks.  On each day one of these tasks is given at random.  How long do you expect it to take to get all five tasks?

First consider a simple case.  Suppose some event has a probability, p, of happening on any one day.  Let’s say that E(p) is the expected number of days we have to wait for the event to happen.  For example if p=1 then the event is guaranteed to happen every day and so E(p)=1.

How can we calculate E(p)? 

Read the rest of this entry »

Here’s a classic from Martin Gardner:

Suppose that you have a 3″ on a side wooden cube and a buzz saw.  You wish to cut the cube into 27 smaller cubes, each 1 cubic inch. It is easy to see that you can do this with six cuts.  You simply hold the cube in its original position while making two cuts that trisect each face.

Can it be done if fewer cuts?  If so, tell us how.  If not, prove that it can’t be done.

“It was a bright, cold day in April, and the clocks were striking thirteen.”

opens George Orwell’s novel ‘Nineteen Eighty-Four’.

1.  By an amazing coincidence thirteen squared is 169 which is the number of times my clock read the right time recently in a single calander day.  Normally it only reads correctly 164 times in a calander day.  This is even more surprising as my clock has been stopped for several years.  How can this be?

My solution combines a number of different techniques.  If you can think of any way a stopped clock can read correctly more than twice a day please post in the comments.  If you can think of something I’ve missed then we may be able to get a bigger answer!

2. I have a second clock which runs slightly fast and I have no way of adjusting it.  How can I make my clock read the right time?

3.  I noticed recently that my third clock was two minutes fast.  It runs at one minute per minute.  It tells me the right time four times a day.  Why?

For inspiration you may want to listen to Peter Sellers (Bluebottle) and Spike Milligan (Eccles) discussing the stopped-clock problem way back in 1957. 

Thanks to New Scientist’s Feedback Column and it’s readers for some of the idea’s here.

What can you say about a sequence if you know that each term is a weighted average of the terms to either side? 

For example, in the sequence 1, 2, 4, 8, 16, … each term is exactly 2/3rds of the previous term, plus 1/3rd of the following term. What other sequences have exactly that property?

For a given value p, what sequences s₁, s₂, s₃, … s_n have the property that each s_k = p s_(k-1) + (1-p) s_(k+1) ? Does knowing s₁ also fix the remaining terms? 

Amusingly, this actually will help with last weeks puzzle!

Standard Podcast [ 2:34 ] Play Now | Play in Popup | Download