Presented by Cold Stone Creamery(R)
The Department of Mathematics Challenge of
the Week
Solution to Challenge 7, Part 2, Fall '04
Let n be the number of pirates and m be the number of coins.
It's easy to show by induction on n that, up through n = 2m+1,
if n is even is even, pirates {1,2,4,6,8, ..., n-2} can be bribed with one
coin each to form a majority coalition,
and if n is odd, pirates {3,5,7, ..., n-2} can be bribed with one
coin each, leaving a remaining pirate from {1,2,4, ..., n-3} to be bribed
with two coins. (The solutions for four and five pirates are special
cases of this.)
Therefore, the first pirate who doesn't have enough
money to pay the necessary bribes is Pirate 2m+2. The situation from here
on out is now the same as it is for Part 1, except that 2m has been added
to the pirate numbers.
That is, Pirate 2m+j can survive his turn if and only if
j is a one shy of a power of two.
Previous Challenges, Fall '04
Challenge 1
Challenge 2
Challenge 3
Challenge 4
Challenge 5
Challenge 6
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.
