My Interview Brain Teasers Part 3

This is Part 3 of my series on [[How to Handle An Interview|how I conduct an interview]].  This brainteaser is sometimes called the Survival of the People brain teaser.  As I've said before, just regurgitating the brain teaser to an interviewee is really lame.  Instead, I modify the brain teaser to fit the situation.  I like to ask this teaser if the candidate tells me how easily he can adjust to scope creep.  This works best in a team interview where everyone is sitting around a table.  I start by saying: 

Your boss has $100 to give each member of the team.  He sticks a Post It on everyone's head with a 1 or 0 on it.  Everyone can see everyone else's Post-It but their own.  Whomever can guess their number gets their bonus.  We start with the new guy who announces his guess and proceed to each subsequent co-worker around the table, clockwise.  You can work as a team and assume everyone will execute the plan perfectly.  How can we ensure our boss disperses the most money?  You cannot say anything but "0" or "1" and you cannot give any non-verbal hints.  If your boss thinks he are not following the spirit of the contest he will award no money.  Lastly, your boss gets to hear your plan and adjust requirements at will!  

In every case I've tried this one the candidate starts by having all co-workers simply guess.  The probability (assuming an even, random distribution) is 50%.  Not great.  The boss hears your plan and ensures they are not evenly distributed.  The candidate will usually then say that every other person should simply say the color of the next person around the table.  This ensures at least 50% success, assuming a random distribution the probability is 75%.  

It is at this point where I tell them the perfect plan will guarantee that everyone, except one, can get their bonus.  That's a big hint.  I like to see if the candidate now focuses attention on this fact.  The logical conclusion is that of course the "new guy" will have to guess, giving him a 50% chance, but also implies that he can give valuable information to the next guy.  The next guy in turn should be able to both announce his answer correctly and also give helpful information to the next guy, etc.  

At this point the candidate will likely say, "I would alter my voice to indicate that the next person in line is either a 0 or 1.  So if I say ZERO that means I'm a zero and the next person is too, but if I say zero that means I'm a zero but the next person is a 1."  This is a really good answer in my opinion because we are answering for ourself and giving the next person the answer.  But now the boss changes the requirement so that the next person to answer is chosen at random so now that information cannot be conveyed.  

This makes things much more difficult.  I usually allow the candidate some uninterrupted time to think through it, then I give a little hint, "notice that every candidate must guess either a 1 or 0, a basic bit.  Could that basic bit also represent something else that is binary?   Let's assume ZERO ALSO EQUALS EVEN and ONE ALSO EQUALS ODD. "  Again, I've always gotten stumped looks.  Fine, let's do an example.  Assume 10 co-workers are sitting around the table with this distribution of 1's and 0's: