31
$\begingroup$

Across the Deadly River, among the Black Mountains, is a mystical cave. Anyone who enters the cave finds within it a single gold coin, which may be freely taken. Once you leave the cave, you can never reenter it. However, a group of people may enter the cave together, even if every member has entered it before, so long as that exact group has never entered. A group of people will still find only a single gold coin. The cave seems to have an infinite supply of gold coins, but stingily doles out only one per visit.

It costs 1 gold coin to pay the ferryman to take you and any number of people across the Deadly River and back. So if you and a friend travel together, you will get 3 coins in total (one from you entering, one from your friend entering, and one from the two entering together). Less 1 coin for the ferryman, that's 2 coins of profit, or 1 for each of you. If instead three people were to make the journey, you'd collect 3 coins by entering individually, 3 coins for each pair, and 1 coin for all of you entering together, for 7 coins. Minus 1 for the ferryman, that leaves 6 coins, or 2 each.

You want to put together a party to travel to this cave. There are a couple of wrinkles though. The first is that a party will only agree to travel if the profit can be divided evenly. As described above, this would work fine for a party of 2 or 3, but it can be shown that a party of 4 would not work, since the profit is 14 coins and 14 is not a multiple of 4.

The second wrinkle is that you want to form a secret conspiracy within your party, consisting of yourself and at least one other person (but not the whole party). After you are back across the River with the divvied-up gold, the members of the conspiracy will turn on the rest, murder them, and steal their shares of the profit. However, people will only agree to a conspiracy if the victims can be divided evenly, so that each conspirator kills the same number of people and therefore pockets the same amount of gold as well. So here we see that a party size of 2 won't work (too small to form a conspiracy within it), and a party size of 3 won't work, because while you could form a conspiracy of two, there would be only one victim, which doesn't divide evenly between the two murderers. A party size of 4 would work, 2 murderers and 2 victims for 1 victim apiece, but this fails the first criterion.

What is the smallest party size for which your plan will work?

Improve this question
$\endgroup$
2
  • $\begingroup$ Yes, well done, I was expecting this one to last more than 15 minutes. Maybe I should have added a layer of game theory on top or something. $\endgroup$
    – histocrat
    Jun 11, 2015 at 19:26
  • 2
    $\begingroup$ Nah, you were just unlucky that I happened to be browsing the site at that time. $\endgroup$
    – user88
    Jun 11, 2015 at 19:27

1 Answer 1

Reset to default
34
$\begingroup$

The first wrinkle is easy enough — you get one coin for each (nonempty) subset of $n$ travellers ($2^n - 1$ total), minus one coin for the ferry, for a total of $2^n - 2$. If that's divisible by $n$, you go.

By Fermat's Little Theorem, any prime number of partygoers will work. But the second wrinkle means that you need to be able to divide your party into multiple equal groups (of 1 conspirator and $m$ victims each), which is impossible if the number is prime.

So you need to find the smallest composite number, known as a Fermat pseudoprime, that satisfies this criterion. In the article I just linked, the answer is stated to be 341.

Therefore, you go with 340 other people, and you and your conspiracy of 10 kill 30 people each.

Improve this answer
$\endgroup$
11
  • 20
    $\begingroup$ Well done, enjoy your 407226316759600765555898596466989868749390090406299915436361654720689431123665626432886816958474021050 gold coins. $\endgroup$
    – histocrat
    Jun 11, 2015 at 19:35
  • 11
    $\begingroup$ I must say, I'm impressed with this ferry's carrying capacity. $\endgroup$
    – user1618143
    Jun 11, 2015 at 20:46
  • 5
    $\begingroup$ @user1618143 I must say, I'm impressed with the group's combination of patience and avarice. $\endgroup$
    – aebabis
    Jun 11, 2015 at 20:55
  • 8
    $\begingroup$ @acbabis: Secret ending: Everyone dies of old age before they get to the murder part. The ferryman (who is clearly some sort of supernatural entity) pockets the gold. $\endgroup$
    – user1618143
    Jun 11, 2015 at 21:25
  • 1
    $\begingroup$ @user1618143 I was expecting something like this... the one coin obviously comes from the ferryman who interferes to make sure your party can only enter the cave once per trip. $\endgroup$
    – Michael
    Jun 11, 2015 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.