Monkeys And Coconuts

May 8, 2015

Today’s exercise has a bit of a Project Euler feel to it. Solving the problem for five or six sailors is easy, but solving it for thirty sailors is hard unless you figure out the secret. Let’s start with a simple recursion that solves the problem by brute force, counting up until the solution is found:

(define (coconuts sailors)
  (let loop ((nuts sailors) (left sailors)
             (takes sailors) (result (list)))
    (cond ((and (zero? takes) (zero? (modulo left sailors)))
            (reverse (cons (list left (quotient left sailors) 0) result)))
          ((and (positive? takes) (= (modulo left sailors) 1))
            (loop nuts (- left (quotient left sailors) 1) (- takes 1)
                  (cons (list left (quotient left sailors) 1) result)))
          (else (loop (+ nuts 1) (+ nuts 1) sailors (list))))))

Sailors is the number of sailors in the puzzle, and never changes. Nuts is the number of coconuts in the starting pile, and increases by 1 each time a trial solution fails. Left is the number of coconuts left each time a sailor takes his share, reduced by one-nth minus 1 for each sailor. Takes is the number of times a sailor has taken coconuts from the pile, decreasing by 1 each time a sailor wakes up and restarting from the number of sailors at each trial. Result is a list of how many coconuts remain at the start of each taking, the number of coconuts taken, and the number of coconuts given to the monkey. Here are the results:

> (coconuts 5)
((3121 624 1) (2496 499 1) (1996 399 1) (1596 319 1)
  (1276 255 1) (1020 204 0))
> (coconuts 6)
((233275 38879 1) (194395 32399 1) (161995 26999 1) (134995 22499 1)
  (112495 18749 1) (93745 15624 1) (78120 13020 0))

I computed the output for the cases from 2 sailors to 8 sailors (it starts getting slow at that point) and went to OEIS, where I found sequence A002021 and the formula for computing the initial number of coconuts:

(define (coconuts n)
  (if (odd? n)
      (- (expt n n) n -1)
      (* (- n 1) (- (expt n n) 1))))

And here’s the number of coconuts for each number of sailors up to thirty, which is computed in a blink of an eye:

> (map coconuts (range 31))
(0 1 3 25 765 3121 233275 823537 117440505 387420481
 89999999991 285311670601 98077104930805 302875106592241
 144456088732254195 437893890380859361 276701161105643274225
 827240261886336764161 668888937280041138782191
 1978419655660313589123961 1992294399999999999999999981
 5842587018385982521381124401 7169985424648610705329581195243
 20880467999847912034355032910545
 30675922867556534862328873875406825
 88817841970012523233890533447265601
 153902989505178932769916857210005094375
 443426488243037769948249630619149892777
 894929124057841121289463662840844356943845
 2567686153161211134561828214731016126483441
 5970842830744820999999999999999999999999999971)

You can run the program at http://ideone.com/NXe7Ks. This puzzle caused quite a stir at the Saturday Evening Post when it was published on October 9, 1926 as part of a story by Ben Ames Williams; 2000 people wrote the magazine in the next week asking for the solution.

Pages: 1 2

6 Responses to “Monkeys And Coconuts”

  1. Rutger said

    Bruteforce in Python..
    With all the stealing, better call them pirates..

    def recur(num_sailors, current_sailor, nuts):
    	pile_size = nuts // num_sailors
    	if current_sailor > 0:
    		# don't upset the monkey!
    		if nuts % pile_size != 1:
    			return False
    		return recur(num_sailors, current_sailor - 1, nuts - pile_size - 1 )
    	else:
    		return nuts % pile_size == 0
    
    for num_pirates in range(3, 30):
    	i = num_pirates
    	while not recur(num_pirates, num_pirates, i):
    		i += 1
    	print num_pirates, i
    
    

    3 25
    4 765
    5 3121
    6 233275
    7 823537
    8 117440505
    9 387420481
    ..

  2. dan pink said

    This site interests me. Are you collecting answers to problems? Can a robot solve these problems?

    I am very put off by the way the questions are worded – “your task is to …”. It reminds me of lunatics who write on a blog demanding that people sent them answers to problems.

  3. namako said

    You can solve the difference equation and apply a divisibility condition to get a formula for the least number of coconuts:

    We start with C coconuts and N sailors.
    Let C_0 = C be the initial number of coconuts.
    From the problem’s description, C_n = (C_n – 1) * (N – 1) / N, and this is a positive integer.
    The final condition is that N | C_N.

    The solution to the difference equation is C_n = (C+N-1)((N-1)/N)^N + 1 – N.

    Since C_n needs to be an integer for each n, and hcf(N-1,N) = 1, we need N^n | (C+N-1), hence N^N | (C+N-1).
    Rewrite to C+N-1 = kN^N for some integer k.
    The final condition means that N | k(N-1)^N +1 – N.
    Rewriting again, k(N-1)^N +1 -N ≡ 0 (mod N)
    so k ≡ (-1)^(N-1) (mod N)
    Choosing k to minimise C, then, k = 1 if N is odd, and N-1 if N is even.

    So C = N^N -N +1 if N is odd, (N-1)N^N -N +1 if N is even.

    I get 5.970842831×10^45 on my calculator for 30 sailors. Which is a lot of coconuts! But the monkey only gets 30 of them.

  4. Mike said

    @namako – Nice.

    I started with the number of coconuts in the morning (base) and worked backwards to see how many would be in the original pile (pile).
    We know that base is divisible by the number of sailors (nsailors). We also know that it is divisible by nsailors-1, because the last sailor pile*(nsailors-1)/nsailors after he took his cut. So, base is a multiple of nsailors*(nsailors – 1).

    To find the size of the pile before the sailor gave one to the monkey and took a cut: pile = pile * (nsailors) // (nsailors – 1) + 1. Each time, the pile must be divisible by nsailors – 1. If not, increase base and try again. Each time, I printed the base number of coconuts and the number of sailors before the test failed. Observing patterns in the printout, I figured out how to increase the step size fairly rapidly.

    def how_many_coconuts(nsailors=5):
        seen  = [None]*nsailors
        base = nsailors*(nsailors - 1)
        seen[0] = base
        step = base
    
        best = 0
        while True:
            pile = base
            #print('\n', pile, end=' ')
            for sailor in range(nsailors):
                pile = pile * nsailors // (nsailors - 1) + 1           # note: // is integer division
    
                if pile % (nsailors - 1): 
                    #print(sailor, end=' ')
                    if sailor > best:
                        if seen[sailor]:
                            step = base - seen[sailor]
                            best = sailor
                            #print(step, '<- new step', end=' ')
                        else:
                            seen[sailor] = base
                            #print('<- first seen', end=' ')
                    break
            else:
                return pile
    
            base += step
    
    print(how_many_coconuts(6))
    
  5. matthew said

    Another approach: we can find a Diophantine equation of the form Ax = By + C where x is the initial number of coconuts, and y is the number of coconuts given to each pirate at the end, and A, B and C are some constants depending on the number of pirates. So for 5 pirates we have 1024x = 15625y + 8404. We can solve such equations in a standard way using the extended Euclidean algorithm:

    def egcd (a,b):
        x,y,z,w = 1,0,0,1
        while b != 0:
            q,r = divmod(a,b)
            a,b =  b,r
            x,y,z,w = z,w,x-q*z,y-q*w
        return a,x,y
    
    def monkey(n):
        A,B,C,m = 1,n,0,n-1
        for i in range(n):
            # Ax = By + C where:
            # x is number of coconuts when i pirates are yet to chose
            A,B,C = m*A,n*B,n*C+m*A
        return A,B,C
    
    for n in range(1,31):
        A,B,C = monkey(n)
        # For A,B find Ax + By = d = gcd(A,B)
        (d,x,y) = egcd(A,B)
        assert(d == 1) # A and B are co-prime
        # Cx + kB is general solution, find smallest positive
        print(n,C*x%B) 
    
  6. zoltan said

    Rutgers solution is bad, only the first result is good:

    java:
    public int calcNumberOfCoconutsFor(int sailors) {
    for (int i = sailors; i < 240000; i++) {
    System.out.println(“current number: ” + i);
    int remaining = i;
    int withoutMonkeyShare = remaining – 1;
    for (int j = 0; j < 5; j++) {
    if (withoutMonkeyShare % sailors == 0) {
    int oneOfFullPart = withoutMonkeyShare – withoutMonkeyShare / sailors;
    if (((oneOfFullPart / (sailors – 1)) * sailors) % sailors == 0) {
    remaining = oneOfFullPart;
    withoutMonkeyShare = remaining – 1;
    System.out.println(“remaining number: ” + remaining);
    if (j == 4 && remaining % sailors == 0) {
    return i;
    }
    }
    }
    }
    }
    return 0;
    }

    results:
    5 – 3121
    6 – 7771
    7 – 16801

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: