33

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?

histocrat
  • 2,336
  • 14
  • 18
  • 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. – histocrat Jun 11 '15 at 19:26
  • 2
    Nah, you were just unlucky that I happened to be browsing the site at that time. –  Jun 11 '15 at 19:27

1 Answers1

35

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.

  • 20
    Well done, enjoy your 407226316759600765555898596466989868749390090406299915436361654720689431123665626432886816958474021050 gold coins. – histocrat Jun 11 '15 at 19:35
  • 11
    I must say, I'm impressed with this ferry's carrying capacity. – user1618143 Jun 11 '15 at 20:46
  • 5
    @user1618143 I must say, I'm impressed with the group's combination of patience and avarice. – aebabis Jun 11 '15 at 20:55
  • 8
    @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. – user1618143 Jun 11 '15 at 21:25
  • 1
    @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. – Michael Jun 11 '15 at 23:26
  • 1
    JSFiddle for a more brute-force attempt: http://jsfiddle.net/4w9eh98o/ – Sphinxxx Jun 12 '15 at 14:00
  • if it takes you 1 femtosecond to form a group, get in the cave, get the coin, get out, you need about 10^79 years. That's ~10^69 times the age of the universe. good luck with that. – njzk2 Jun 12 '15 at 16:35
  • 1
    Ah...you forget parallelization. Just form multiple parties and have them each go in... The rules never said that the cave didn't allow for parallelization... – Aron Jun 17 '15 at 13:35
  • @histocrat I wouldn't want that many gold coins even if each one was only 1 anstrom in size. Sure... With that much gold, it would get you everything you ever wanted in the universe...quite literally... – Aron Jun 17 '15 at 13:52
  • @aron : Well, gold would devaluate very very fast... :) – Tim Couwelier Sep 22 '15 at 08:10
  • Fermat's little theorem states that if n is a prime number, then for any integer a, the number a^n − a is an integer multiple of n. But Fermat's little theorem does not say that a^n-a is divisible by n if and only if n is a prime number. Therefore, is it possible that there exists a non-prime n smaller than your answer which satisfies all the conditions ? – Hemant Agarwal Sep 13 '20 at 03:53
  • @HemantAgarwal (and anyone else who is confused): You misread. Fermat's little theorem says that any prime number satisfies the first condition. But the second condition says that number of people going must not be prime (it has to be equal to (number of murderers) times (one plus the number of people killed by each), and both these factors are greater than one by assumption). So the answer should be the smallest non-prime number which satisfies the conclusion of Fermat's theorem with $a=2$. Such a number is called a Fermat pseudoprime to base $2$, and the smallest is $341=11\cdot31$. – A. Howells Aug 20 '23 at 02:55