Monkeys and coconuts: a challenge

[Bart]

Hi,

First of all. This is not a school assignment.
(See my wiki page to see what I'm doing in real life.)

For those who have nothing better to do, or just like the challenge.

Here's the situation.

After a huge storm 5 sailors are stranded on a tropical island.
On the island there is no other human being.
There are trees and 1 monkey (maybe other monkeys too, but the don't show themselves).

The sailors gather as much coconuts as they can and then go to sleep.
During the night one after each other the sailors wake up.
Each sailor in turn, when awake, sees the pile of coconuts and divides it into 5 equal shares.
After dividing there is exactly 1 coconut left, and he gives that to the monkey.
He hides his share of coconuts and then puts the remaining back onto 1 pile.

When the day breaks, all of the sailors wake up again and see a rather smaller pile.
(Nobody of course is willing to tell what he's donduring the night).
The sailors then divide this final pile into 5 equal shares, and this time no coconut is leftover (so the monkey gets none).

Q1: How many coconuts where there at the beginning (it can be proven that there is an infinite amount of solutions, so what is the smallest amount)?

Q2: Can you write an equation that calculates the smallest possible solution?

Q3: Can you write a search function that finds the smallest possible solution, with the condition that the input of that function must be the amount of coconuts that each sailor gets in the final division? (Starting with the total amount is way to easy).
(A prototype could be: function IsPossibleSolution(FinalShare: Integer; out N: Integer): Boolean;)

Q4: Can you generalize the function from Q3 so that it accepts 6 arbitrary remainders (0..4) for each step in the division? It can be assumed that after each division, the remainder is given to the monkey.

Q5: Given the same situation, but now in the final division there is again 1 coconut remaining (which goes to the monkey). How many coconuts where there at the beginning?

Q6: Given the function from Q5: what is the solution if the remainders are (from first division to last): 4, 3, 2, 1, 0, 1?

Bart

[lainz]

Nice. It keep my thinking... I can't solve it right now. My mind is more artistic than nothing.

[BitBangerUSA]

ya got some ambiguity in the part above Q1.

6 <> 0..4

'He shares...' which sailor? last one? each one?

[Blaazen]

add Q1: My function says 3121 coconuts. Am I right? 

[Bart]

6 <> 0..4

In total there are 6 divisions.
Each of the 5 sailors does one, and in the morning there is the final division.

Since each division is a division by 5 (there are 5 sailors), the remainder can only be in the range of 0..4.

'He shares...'

I never said "He shares".
Each sailor divides the pile into 5 equal amounts, and the remainig 1 cocounut from this action goes to the monkey.

Bart

[Bart]

add Q1: My function says 3121 coconuts. Am I right? 

I don't want to comment on that in public yet.
I'll pm you.

Bart

[Blaazen]

So should we send you PMs with answers and later you will announce winner ?

[BitBangerUSA]

6 <> 0..4

In total there are 6 divisions.
Each of the 5 sailors does one, and in the morning there is the final division.

Since each division is a division by 5 (there are 5 sailors), the remainder can only be in the range of 0..4.

'He shares...'

I never said "He shares".
Each sailor divides the pile into 5 equal amounts, and the remainig 1 cocounut from this action goes to the monkey.

Bart

true. it was 'He hides his share...'
very interesting problem.

seems to me to be a task that calls for recursion and working backwards...

[skalogryz]

seems to me to be a task that calls for recursion and working backwards...

Nope. it's just a loop.

Each "iteration result" should be dividable by 4 without modulus (since a sailor ...puts the remaining back onto 1 pile.)
But since we're going backwards, we need to calculate the "previous" state, which is reversive of and divides it into 5 equal shares.
After dividing there is exactly 1 coconut left, and he gives that to the monkey.

Now for Q6, 1 coconut should be replaceable by a value passed to a function.

anyway, it's all too easy, and i think it's Bart's school assignment.

[BitBangerUSA]

it does seem like an assignment - but i'll not google.

the sequence in Q6 looks suspicious - when the remainder is 0, the amount divided must have been a multiple of 5. given that, the last division can't result in a remainder of 1.

[eny]

Following Numberphile are we?
https://www.youtube.com/user/numberphile/videos

[taazz]

Step 1 define the 6 equations one for each devision something along the lines of
1)X = 5A+1
2)A = 5B+1
3)B = 5C+1
4)C = 5D+1
5)D = 5E+1
6)E = 5F+1

Replace all unknowns with their equations starting from the bottom up. we have something like
5) D = 5E+1 => D = 5(5F+1)+1 => D = 25F+6
4) C = 5D+1 => C = 5(25F+6)+1 => C = 125F+30+1 => C = 125F+31
3) B = 5C+1 => B = 5(125F+31)+1 => B = 625F+155+1 => B = 625F+156
2) A = 5B+1 => A = 5(625F+156)+1 => A= 3125F+780+1 => A = 3125F+781
1) X = 5A+1 => X = 5(3125F+781) + 1 =>  X = 15625F+3905+1 => X = 15625F+3906 smaller possible integer number is 1 so starting number is 19.531

of course the above assume that the last devision gave a coconut to the monkey as well which makes it the solution for Q5. Calculations  are made while typing the solution mostly in my head so it probably has errors. It is simple a description for the methodology for calculating the final equation to create a function for it ee

Code: [Select]

Function HowManyCoconuts( EachSailorGot:Byte)Qword;
begin
  Result := 15625*EachSailorGot+3906;
end;


the sequence in Q6 looks suspicious - when the remainder is 0, the amount divided must have been a multiple of 5. given that, the last division can't result in a remainder of 1.

basically neither can the second division. If the first division by 5 gives one reminder which is given away then the second division by 5 should have no reminder at all. As an exercise in logic and task subdivision is nice but (in the famous words of Mr spock) it is illogical.

[marcio2003]

Code: [Select]

unit Unit1;
{$mode objfpc}{$H+}
interface
uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;
type
  { TForm1 }
  TForm1 = class(TForm)
    B1: TButton;
    E1: TEdit; { e1.text = 1 }
    E2: TEdit; { e2.text = 1000 }
    L1: TLabel; { result: after 5 sailors }
    L2: TLabel; { result: start }
    procedure B1Click(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end;
var
  Form1: TForm1;
  i: integer;
  T: array [ 0..5 ] of real;
Implementation
{$R *.lfm}
{ TForm1 }
procedure TForm1.B1Click(Sender: TObject);
begin
  L1.Caption:= '?';
  L2.Caption:= '?';
  for i:= StrToInt( E1.Text ) to StrToInt( E2.Text ) do
  begin
    T[5]:= i * 5; { min T[5] mod 5 = 0 } { After 5 sailors }
    T[4]:= ( T[5] * 5/4 ) + 1;  { After 4 sailors }
    if frac( T[4] / 4 ) > 0 then
      continue;
    T[3]:= ( T[4] * 5/4 ) + 1;  { After 3 sailors }
    if frac( T[3] / 4 ) > 0 then
      continue;
    T[2]:= ( T[3] * 5/4 ) + 1;  { After 2 sailors }
    if frac( T[2] / 4 ) > 0 then
      continue;
    T[1]:= ( T[2] * 5/4 ) + 1;  { After 1 sailor }
    if frac( T[1] / 4 ) > 0 then
      continue;
    T[0]:= ( T[1] * 5/4 ) + 1;  { Start }
    if frac(( T[0] - 1 ) / 5 ) = 0 then
    begin
      L1.Caption:= IntToStr( i );
      L2.Caption:= IntToStr( trunc( T[ 0 ] ));
      ShowMessage( 'Solution found for this interval.' );
      break;
    end;
  end;
  if L1.Caption = '?' then
    ShowMessage( 'No solution for this interval.' );
end;
end. 

[skalogryz]

Step 1 define the 6 equations one for each devision something along the lines of
1)X = 5A+1
2)A = 5B+1
...

According to the task, it should go like this:
1) X = A + 4*A + 1
2) 4 * A = B + 4* B + 1
3) 4 * B = C + 4 *C + 1
... keep in mind the condition He hides his share of coconuts and then puts the remaining back onto 1 pile

Thus the next division takes place only on the 4-parts of 5N

[Eugene Loza]

I don't remember the exact formulation of this problem for fish and fishers but Witgenstein or Dirac got answer 'minus 5 fishes'.

As for this problem:

Amount of coconuts = Q

Q = 5*N1 +1;
4*N1 = 5*N2 + 1;
4*N2 = 5*N3 + 1;
4*N3 = 5*N4 + 1;
4*N4 = 5*N5 + 1;
N5 = 5*N; for Q1 and N5 = 5*N+1; for Q5

then:

Code: [Select]

procedure TForm1.Button1Click(Sender: TObject);
var n:integer;
    Q,n1,n2,n3,n4,n5:integer;
    solution:boolean;
begin
  memo1.clear;
  n:=0;
  solution:=false;
  repeat
    inc(n);
    n5:=5*n{+1};
    begin
    n4:=5*n5+1;
    if n4 mod 4 = 0 then begin
      n3:=5*n4 div 4+1;
      if n3 mod 4 = 0 then begin
        n2:=5*n3 div 4+1;
        if n2 mod 4 = 0 then begin
          n1:=5*n2 div 4+1;
          if n1 mod 4 = 0 then begin
            Q:=5*n1 div 4+1;
            memo1.lines.add(inttostr(Q));
            solution:=true;
          end;
        end;
      end;
    end;
   end;
  until n>10000;
end;

Q1 -------- 3121
Q2 -------- I was trying to but got stuck finally too unexperienced in digital math
Q3...Q4 --------- no sense
Q5 --------- 6246
Q6 --------- didn't understand the question

----------------------------------- (UPD) ------------------------------------

a next step towards Q2: Solved the equations system with multiplication and no division:
4*4*4*4*Q = 5*5*5*5*5*N5 + 5*5*5*(5 + 4) + 5*5*4*4 + 5*4*4*4 +4*4*4*4;
N5 = 5*N; for Q1 and N5 = 5*N+1; for Q5
i.e.
256*Q = 15625*N + 1161 {+3125};
(hopefully no mistakes here)
Its equation but it doesn't calculate anything actually yet and "15625*N + 1161 {+3125} mod 256 = 0" is not a 'solvable' equation.