I agree with aquaepulse - it's easy to misread the question and think it's a special case.

Though this simplified problem is a good starting point, I think.

Good question. No, the other prisoners don't need to know whether each prisoner answered correctly.

Hey Victor, thanks for the comment. If you take a closer look at the solution, you'll see that it works for any number of white and black hats. Try it for the extreme case 0 black hats followed and 100 white hats.

They key thing to remember is the third part in the solution: ^spoiler Based on the previous responses, keeping track of whether they should expect an odd or even number of white hats in front of them, every prisoner can determine whether they are wearing a black or white hat.

Hey Anand, that scheme won't work. Consider this scenario starting from the back: BWBB...

According to what you've described, the first prisoner (wearing a black hat), will say "white" and be killed. The second prisoner (wearing a white hat) has to say "black" because the two prisoners in front of him are wearing black. Since he is wearing white, he is killed as well. As such, more than just 1 prisoner is at risk in this design.

That's a good point, but I think the idea is to avoid conditionals altogether. Your compiler turns the ternary ( ? : ) operator into the same code that it turns an if statement into (i.e. a conditional branch with two blocks).

Haha that's kind of clever :)

Love the second explanation, very clever.

Solid puzzle. It should be mentioned that, at the London racetrack, you don't actually time each horse. Each time you race 5 horses, you get their relative ranking (who came 1st, 2nd, 3rd, 4th, and 5th) and no other information.

These balloon questions always get me.

Exactly, I find this arises so often with statistics/probability questions...intuition isn't worth a whole lot. After figuring it out or understanding the solution, you start to wonder how many other things you haven't thought about correctly.

So interesting...I'll check wikipedia out for some proofs.

Took me longer than I'd like to admit...very nice though.

So much more manageable...this one is tricky and takes some time.

Very good answer - this seems impossible at first...

Interesting approach. Combinatorics also works nicely.

That sounds right to me.

Whoa - thanks for sharing!

I think Squeamish meant that the first and last numbers in each row have the same number of letters. The rest of it is as Squeamish described.

Ahh, got it! I think the question is clear, but like this one helps a lot. Thanks, cool question!

Could you explain why, in your illustration, the answer is 3? Doesn't the question say that all the subsets have to be mutually exclusive (i.e. disjoint)?

Then, with r=4 and k=2, you have only the sets {1,2} and {3,4}. Introducing any of the other sets you mentioned will violate the "disjointness among subsets" requirement. Am I misunderstanding the question?

Ravi, this is not a puzzle.

The solution seems a little vague - care to explain?

I'm pretty sure #ProblemsMakeYouHungry is going to take off as a hashtag.

I think this still assumes that you know whether the odd ball is heavier or lighter in advance. The question doesn't appear to give you that assumption.

Agreed, unless both a and b are zero...

You're right - I've updated the puzzle :)

No worries - solid explanation!

Agreed, I just posted a clearer one here if you're interested: http://www.mindcipher.com/puzzles/151

Here's a clearer version: http://www.mindcipher.com/puzzles/151

Whoa, the triangular number sounds surprising..could you explain it with another example? If we have 2 and 3: 2^3 = 8, 3^3 = 27.

In this case, what's our "triangular number ending in k"?

All of the white king's moves are illegal since they put white in check.