Byzantine Bettors

Last year I had an idea to work my way through Dennis Shasha's book: Puzzles for Programmers and Pros.  Well, it's been a busy year and I didn't quite get around to it.  But, since we had a holiday this week, I had some time to play around and managed to finish another one.  As promised, I'll write about it here.

In this problem, you have some advisors, some who always tell the truth and some who may or may not lie.  The idea is you can make a bet, from $0 to $100, on whether a number on a piece of paper (face down) is 0 or 1.  The goal is to figure out how much you are guaranteed to win.

In the first case, you have two advisors out of four who always tell the truth.  You start with $100.  I figured out that the amount you are guaranteed to win is $400.  Here is how I worked it out:

The second part is a bit trickier: how much are you guaranteed to win if you start with $100 but there are only three advisors, and only one of them always tells the truth.  The answer I got is $266.69 - which I got by working out the different cases you would encounter and working through the possibilities.  I used a flow chart to do that:

I'm enjoying the book and hopefully will get around to posting a few more problems soon!