Perfectly Logical Pirates and Sheep

 

 

            Here are the complete answers to the pirate and sheep problems from the midterm:

 

 

            Sheep:

            The key to this problem is making full use of the fact that the judge would stop whenever he could convict or acquit anyone, and that he convicted someone after three questions.

            First, we note that the answers to the second question could not have been “No.”  Because if the answer to the second question were “No,” then the first two sheep must either both be speaking the truth or both be lying.  In either case, one of them is the spy.  [Since if the first two sheep were not the spy, one would have to lie and other would have to speak the truth.]  Since the judge did not acquit after the second question, there must have been a possibility that the third person was guilty.  Hence, the second answer must have been “yes.”

            Next we note that the first and last sheep must answer the same, as “NYY” and “YYN,” both allow for multiple people to be te spy.  In the first case the sheep could be “Truther, Liar, Spy,” or “Spy, Truther, Liar.”  In the second case the sheep could be “Liar, Truther, Spy,” or “Spy, Liar, Truther.”  Hence the answers would be inconclusive.

            Thus, the only possibilities are “YYY” and “NYN.”  In the first case, neither the first or last sheep can be the truther (as the truth teller would never say he is the spy), hence the middle person is telling the truth, the first lying, and the third is the spy.  In the second case, neither the first or last sheep can be the liar (who would say he is the spy).  Thus the middle sheep is the liar, the first is speaking the truth and the third is a spy.

           In both cases, the third sheep is convicted as the spy.

 

 

            Pirates:

            As was pointed out on the handout, if there were only two pirates, the captain could claim all the gold for himself and win the 1-1 tie vote that would occur.  Thus, if there were three pirates, the first mate would never side with the captain, as he knows he will get all the gold if he can thwart the captain.  However, the second mate knows that, if the captain is thrown overboard, he would receive no gold whatsoever.  Thus, the captain only needs to give one gold coin to the second mate to secure his vote, as the second mate will get more gold this way than if he throws the Captain overboard.

            Thus, with three pirates, the captain proposes the plan of him getting 99 coins and the second mate getting 1.  This plan passes 2-1.

 

            We can build upwards to the case of 4 pirates.  Since in the case of three pirates, the first pirate gets 99 coins and the second mate gets 1, we see that the captain would have to give all 100 coins to the first mate if he wants his vote (otherwise the first mate, upon becoming captain, would get 99).  However, the captain doesn’t need the first mate’s vote, he only needs 1 other vote.  Since the third mate will become the second mate (and get 1 coin) if the Captain is thrown over, the captain would have to give the third mate 2 coins to buy his vote.  However, if the captain gets thrown over, the second mate would become the first mate and get nothing (since the first mate never gets anything).  Thus the captain only needs to give the second mate 1 coin to get his vote.  This is the cheapest possibility, so the Captain allocates 99 for himself and 1 to the second mate.  This plan passes 2-2.

 

            If there were 5 pirates, a similar analysis holds: the second mate and the fourth mate would receive nothing if the captain is thrown overboard as they would become the first and third mates in the 4 pirate version, and hence receive nothing.  Thus, it only requires a single gold coin to get their votes.  So the Captain allocates 98 coins to himself and gives 1 coin to the second mate and 1 to the fourth mate.  This plan passes 3-2.

 

            This continues up until the 30 pirate version, each time the even numbered mates know they will receive nothing if the current captain is thrown over, so the captain gives each of them one coin to vote for him.  So, in the case of 30 captains the plan for allocating the booty is 86 for the Captain and 1 for the 2nd,4th,6th,…,28th mate.  This plan passes 15-15.

 

            However, evenutally we run out of coins and the problem takes on another facet.  It is not as simply as “the pirates kill each other off until there are only 202 pirates left.”  Let’s take a closer look:

 

            When there are 202 pirates left, the captain can save his hide by giving every other mate a gold coin.  When his own vote is added, the plan passes 101-101.  Thus, when there are 202 pirates or fewer there is no danger of anyone being thrown over.  This is the first cornerstone of the solution.  This means that it will always take at least 1 coin to buy the votes of the pirates if there are 203 or fewer pirates, since the pirates know they can at least get the joy of throwing someone overboard if they don’t get at least one gold coin.  Since there are only 100 coins and a captain of 203 pirates would need 101 votes (not counting his own), there is no way the captain lives.

            Since anytime there are 203 pirates left,the Captain always gets thrown overboard, the pirates know they can expect as much money as in the case with 202 pirates, since it will reduce to that scenario when the captain is off’ed.  Thus, the 1st mate (who will become captain) knows he will receive no gold, but can keep his life.  The 2nd mate (who would become 1st mate) knows he will receive no gold but keep his life.  The 3rd mate, 5th mate, 7th mate, etc. all know they will receive 1 gold coin and all the other mates know they will receive nothing, but all keep their lives.

            Now, consider what occurs with 204 pirates.  Since the 1st mate would become captain (and afterward fish food) if the plan fails, the 1st mate will vote for the captain’s plan no matter what!  Thus, the Captain in the 204 pirate version gets a free vote.  He can pay 1 gold coin to 100 of the pirates who would otherwise receive nothing if he is thrown overboard, and this gives him enough votes (counting his own) to keep his life.  Thus, we see the plan for 204 pirates would be:

0-0-0-1-0-1-0-1-0-1-0-1-…-0-1.

And the vote would be 102-102 (he would receive his own vote, the 1st mate (who otherwise is doomed when he becomes captain) would vote for him along with the 100 pirates who received the gold coins.

 

            However, this means that the Captain of a crew of 205 will be in big trouble, since the pirates now know that 204 is a “safe” number…a number in which no one dies.  Thus, the pirates will once again need to be paid at least 1 gold coin for their votes and there are not enough gold coins to go around.

            In the case of 206 pirates, the same thing occurs, except the first mate is the “free vote,” he will vote for the Captain no matter what.  However, that still is not enough to save the captain’s hide, since he could only muster 102 votes (His own, the free vote from the 1st mate and the 100 he could buy from the other pirates).  Thus, with 206 pirates the captain is also thrown overboard.

            Similarly for 207, except now the captain gets 2 “free votes,” since now the first mate and the second mate know they will die if the plan does not go through.  However, these two free votes only give the captain 103 (1 for himself, 2 free ones, and 100 to be bought with gold coins).  He needs 104 votes to live, so he dies also.

            Finally, with 208 pirates the captain gets 3 free votes, since the first three mates know they will all die if the captain’s plan does not work…thus the captain can must 104 votes: 1 from himself, 3 free ones from the first three mates, and 100 from the gold coins.

            Thus we have that 208 is another “safe number,” and the progression begins again, with the captains dying until they get enough ‘free votes” to overcome the sanguinity of the pirates who know they are safe [the first 208 of them].

           If we examine the pattern of “safe numbers:” 202, 204, 208, we see that they are all “200 plus a power of 2,” so 216, 232, and 264 will all be safe numbers.  However, there are no safe numbers from 264 to 300.

            So, in the case of 300 pirates, the first 36 pirates die and when there are 264 pirates left, the captain proposes a plan where the first 32 pirates [including himself] get nothring, but vote for the Captain anyway to preserve themselves, and the mates numbered 66,68,70,…264 each get 1 and vote for the captain so that the plan passes 132-132.  Note, there is one extra subtlety, at each “safe number” the even or oddness of which of the mates you buy with the gold changes, but that is a minor point.

 

            Note, if anyone had given a super-complete answer to the pirate problem, he would have received 13 out of 10 points…A completely complete answer for the first 2 steps garnered 8 points.

 

-Rudel