Friday, December 25, 2009

Being a Dissertation on Pirates, Closed-Societal Rank, and the Ideals of Democratic Progression

The other day, I got a call from a friend on a strange-looking logic problem that she had encountered on one of her exams. That this happened to be a corporate exam surprised me; I ran into a variant of this one some years ago, and it struck me as the kind of thing that takes a great leap of logic in order to solve.

I'll paraphrase it below, just for the telling. There are plenty of versions of this puzzle running around, so don't take this one as canon:

Five pirates have gathered on a deserted island to divide their booty: 1,000 gold coins in total. These 5 pirates are ranked by seniority (so there's a #1 pirate, a #2 pirate, and so forth, all the way down to a #5 pirate), and it's the job of the most senior pirate to decide how the loot should be divided among themselves.

There is, however, a catch: Whenever the most senior pirate gives a proposal on how to divide the loot, a vote is taken among all of the pirates. If the majority of the pirates agree with the proposal (or if the vote is tied), the coins are divided as stated. If the majority of the pirates disagree with the proposal, however, the most senior pirate is killed and the next most senior pirate must now come up with a proposal.

As mentioned, there are currently five pirates, and it is now the job of the pirate captain (pirate #1) to decide on how to divide the 1,000 coins. Each of the pirates is completely logical in nature, will never abstain from voting, and would like to keep as many of the coins as possible for him or herself. What division should the pirate captain propose so that he gets as much of the coins as possible, without risk of getting killed in the process?

The obvious concern here is that you can name virtually any division proposal, and the problem will simply throw it right back in your face. The pirate captain can, for example, suggest that the coins be divided equally among all five pirates (i.e. each of them gets 200 coins)... but then, how do you stop the other four pirates from thinking that they could just as easily get 201 coins each?

No, the real puzzle here involves coming up with a convincing argument: the solution involves devising a sound logical structure — sound enough, at least, to get the majority preference among the pirates. That happens to be the key to the problem, mind you — we can assume that each of the pirates is a completely logical, which means that we can presumably predict how they will think.

The worst-case scenario involves all of the first four pirates losing the vote on their respective proposals, in which case it will be Pirate #5's turn to make a proposal. In this case, the situation goes as follows:

Pirate #5: "Since I'm the only pirate remaining, I can simply propose that I get all 1,000 coins. When the vote comes, I'll be the only one voting, which means that I can just vote for myself and let the proposal pass! Whoo-hoo!"

Easy, right? This situation will obviously be the result if it comes down to Pirate #5 making the porposal... and Pirate #4 knows this. So what should Pirate #4's proposal be, assuming that only #4 and #5 are remaining?

Pirate #4: "Only me and Pirate #5 remain, but I just need to tie the vote in order for my proposal to pass. If that's the case, then what's stopping me from proposing that I get all 1,000 gold coins and Pirate #5 gets nothing? Pirate #5 will definitely vote against me, but he can't do anything about the tied vote, and I'll get the coins as proposed."

So the basic fact is that, if the first three pirates are killed and the proposal goes to Pirate #4, when Pirate #4 will certainly get all the coins. Pirate #3 must know this, and must therefore plan accordingly:

Pirate #3: "Pirate #5 knows that if I'm killed, then the proposal passes to Pirate #4, and #5 gets no coins at all. Therefore, I'll propose that Pirate #5 get one coin — because that's more than he'll ever get out of this deal, and he'll have to vote for my proposal — and I get the other 999 coins. Pirate #4 gets nothing at all, but I don't need his vote anyway."

And now, since Pirate #2 knows that he needs to get at least two votes for his proposal — his own vote, plus one of the other pirates' votes... the most economical solution is to offer Pirate #4 an incentive.

Pirate #2: "I'll propose that Pirate #4 get one coin — because he gets nothing at all if Pirate #3 is allowed to make a proposal — and that I get the other 999 coins. Pirate #3 and Pirate #5 will definitely vote against me, but they won't be enough for a majority."

As a result, the pirate captain (Pirate #1) must take all of the above into account. Noting that he only needs three votes — his own vote and at least two other pirates' — for his own proposal to pass, he must offer the minimum needed to two other pirates in order to "buy" their votes. This is this correct, and final answer:

Pirate #1: "If it falls to Pirate #2 to make a proposal, Pirate #3 and Pirate #5 both get nothing at all. So in order to get their votes, I'll offer that Pirate #3 get one coin, and that Pirate #5 gets two coins (so that he's not tempted to wait for Pirate #3's proposal). In the meantime, I get the other 997 coins via majority vote... and Pirate #2 and Pirate #4 both get nothing."

Questions like these are logical models: They assume that all involved entities follow a logical pattern, and then challenge you to follow that logical pattern to a correct resolution. Usually the best approach for each of these is to boil them down to a simpler scenario (usually a snapshot of the same situation in a future iteration) and then work your way back to the original complex scenario.

The earliest (and simplest) example of such a puzzle that I remember goes as follows. I'll use the "pirates" background again, because we might as well go all Jack-Sparrow today:

Three stowaways have been caught on the deck of a pirate ship. Now, normally, they'd be executed, but the pirate captain is feeling a little generous today, and decides to play a little game with them.

The stowaways are shown a total of five shirts: Three of the shirts have a black mark on the back, and two of the shirts have a red mark on the back. Then each of the three is blindfolded, and each made to wear a shirt with a black mark (although they don't know what color mark they're wearing). The two shirts with red marks are then hidden from sight, and the blindfolds removed.

The pirate captain then announces to the three: "Each of you is wearing one of the five shirts we showed you earlier — either a shirt with a black mark, or a shirt with a red mark. Each of you can see what colors the other two are wearing, but not your own. The first one among you who can tell us the color of the mark he is wearing will be freed, while the other two will be executed."

The stowaways are all completely logical, and none of them dares turn his own shirt around for fear of angering the pirates. After a few minutes of silence, however, one of the stowaways announces, "I'm wearing a shirt that has a black mark." How did he know this?

Assuming that the three stowaways are named #1, #2, and #3 — with Stowaway #1 being the lucky man who speaks first — we can boil down #1's thought process as follows:

Stowaway #1: "Let's simplify the situation first: Let's suppose that I'm wearing a red mark.

"If I'm wearing a red mark, then when Stowaway #2 looks at me, he sees that I'm wearing a red mark. And he must be thinking: If I'm wearing a red mark myself, then Stowaway #3 sees two red marks and should therefore immediately conclude that he's wearing a black mark.

"But Stowaway #3 doesn't say anything... and in that case, Stowaway #2 can only conclude that he's not wearing a shirt with a red mark. So Stowaway #2 should have concluded that he's wearing a black mark.

"But Stowaway #2 doesn't say anything, either. And if he doesn't say anything, then that can only mean that my original assumption is wrong. Stowaway #2 doesn't see a red mark on my shirt because I'm not wearing a red mark. I must therefore be wearing a shirt with a black mark."

I've seen quite a few other variants of these situations as well — I've seen grand viziers separated by walls, I've heard of leather-jacket-wearing scientists being locked up in rooms, and I've even read of costume-wearing kids sharing Halloween candy. Each of them happens to be a variant of the puzzles above, or of some unlikely logic-inducing scenario that's closely related to them. The method of solution happens to follow the same pattern, and that involves trying to simplify the situation to a point where the larger problem is solvable.

The strange part lies in the fact that, in order for the object of the puzzle (the "protagonist", if you will) to get out of his or her situation, they'll literally need to think in terms of the other characters' thoughts. It's like having some pseudo-logical encouragement to put yourself in somebody else's shoes.

That said, puzzles like this are actually somewhat rare — when all the variants are compressed into their original versions, you don't have much to go around. I suspect that the more popular logical models belong to a subset of puzzles — the liar- and truthteller-versions — if only because these can go through an infinite number of combinations and get a proportional amount of study.

Finding this puzzle in an exam for a corporate application, though... well, that's just odd. It's not the sort of thing that you can answer in a few sentences, after all. I'm actually more interested to find out if 1) said corporation offers any similar brainteasers in its application process, and 2) said corporation actually expects people to solve these things in one breath.

An even more pressing question, of course, lies in why a company would ask such things of their applicants. Let me see... darkened rooms, strange procedures, and threats of execution... perhaps these things are closer to the corporate scenario than I imagine.

No comments: