Paul’s Puzzler: Pirates and Gold Bars
I sometimes get asked at parties why dropped calls occur as often as they do. “Why not just ‘connect’ to the ‘tower that has the strongest signal?’ a layman’s approach to handover. If you run into that question, you may wish to challenge the questioner to a brain teaser that highlights the perils of trusting our intuition when it comes to “greedy algorithms” — the strongest signal being a form of greed in this context. If you’re a non-technical reader, just ignore the bit about handover and enjoy the following as a puzzle.
The brain teaser goes like this: Ten pirates come across 100 bars of gold. The pirates have a pecking order, with #10 and #1 indicating the top and bottom-ranked pirates, respectively. Each pirate wants to maximize his share of the gold bars. There are no coalitions or collusions between them. They are all very analytical—they can think things through!
Their process for splitting the loot is somewhat democratic. It begins with the top-ranked pirate making a proposal on how to divvy up the loot. (Note that the gold bars can not be broken up, glued together, or otherwise changed; there are 100 bars of gold, period.) Each man gets one vote, up or down on the entire proposal. Remember, each man votes his own pocket and there are no side agreements of any sort. If the proposal gets 50% or more votes, it wins! If it fails to muster majority, the pirate who made the proposal is thrown overboard, and the process continues with the next pirate down the hierarchy.
The question is quite simple: What is the maximum number of bars that the most powerful pirate can get and what allocation to each pirate will ensure him the 50% vote that he needs?
Look for the answer next week. It may surprise you!
Editor: Paul is scheduled to teach the 2-day UMTS seminar scheduled for Nov 5-6, 2007 (Washington, DC).