Byzantium is famous for the incessant intrigues and plotting that supposedly took place among the courtiers of the palace. Apparently, the Byzantine court in no way deserved this reputation. Modern historical research suggests that Byzantium achieved a remarkable stability and harmony by the standards of the first millennium. Reputations die hard, however, and this puzzle concerns a game show inspired by the imagined intrigues of Byzantium. We call it Byzantine Bettors.
Each bet works as follows. There are some number of "advisors" and you. One advisor will write either 1 or 0 on a piece of paper, show it to the other advisors but not to you, and put that paper face down in front of you. Each advisor will tell you what the value is. They are all very good actors, so no obvious tick or facial expression will reveal to you who is telling the truth. The amount you can wager on each bet is anything from 0 to the total amount you have.
Suppose there are four advisors and two always tell the truth, although you don't know which ones. You get three even-money bets (that is, if you win, your winnings are equal to your wager). You start with $100. With the right strategy, how much can you be sure of winning?
Solution to Warm-Up:
If all four or three out of four advisors agree on the first bet, then bet all the money you have. At least one truth teller must be in that group. If the advisors are two and two, then bet nothing. After the first bet, you will know who the truth tellers are and will be able to bet the maximum each time. Thus at least two times you will be able to bet all you have and be sure to win. This will give you a total of $400 at the end.
1. Now suppose there are only three advisors and only one of them always tells the truth. Again, you can make three even-money bets. You start with $100. How much can you guarantee to win?
The game has just become a little longer but also a lot more nasty. You have four bets but there is no longer a truth teller, merely a "partial truth teller." That advisor is not guaranteed to tell the truth all the time, but must do so at least three out of four times. Further, the advisors can actually substitute what's on the paper for a worse result for you once they hear your bet. However, they cannot change the result if so doing would eliminate the possibility that at least one of them is a partial truth-telling advisor.
2. What are you sure of winning in four bets, with four advisors, of whom three can lie at will and one must tell the truth at least three out of four times?
3. Under the same reliability conditions as question 2 (one partial truth teller who tells the truth four out of five times and three liars at will), but assuming you have five bets, can you guarantee to end with at least $150?
Hint: The last two questions may require some quiet contemplation.