Math Challenge of the Week

Presented by Cold Stone Creamery^(R)

The Department of Mathematics Challenge of the Week

Solution to Challenge 7, Part 1, Fall '04

Let a pirate be ``safe'' if he will survive, even if the pirate whose turn it is walks the plank, and ``scared'' otherwise. A scared pirate will always vote to spare the pirate whose turn it is, and a safe one will always vote for him to go overboard.

Pirate 1 is safe. Therefore, he will send Pirate 2 overboard if it's 2's turn, so 2 is scared if it's 3's turn. Pirate 3 can count on 2's vote, and 3 will survive his turn.

Because of this, if it's a higher-numbered pirate's turn, 1, 2, and 3 are safe, so they will vote for him to go overboard. The next pirate who can survive his turn is 7, who can count on the votes of scared pirates 4, 5, and 6, which, together with his own vote, will outnumber 1, 2, and 3's votes. By induction, a pirate can only survive his turn if his number is one shy of a power of two. The pirates numbered 1 through the next smaller number that is one shy of a power of two will be safe, so he can get a majority if and only if his own number is also one shy of a power of two.

Previous Challenges, Fall '04

If you would like to receive a weekly email reminder about the Challenge Problem, send an email to solution@math.colostate.edu

The Department of Mathematics Challenge Problem is sponsored by the Cold Stone Creamery, which is providing all the prizes.

If more than one correct solution is submitted, one prize winner will be chosen from among the correct solutions. Submissions from CSU faculty and people not affiliated with CSU are encouraged, but they are ineligible for the prizes unless they are unclaimed by students.

For questions, comments or suggestions for future challenge problems: please e-mail Ross McConnell, rmm@cs.colostate.edu.