Monkeys and coconuts: a challenge lazarus / 62-General ---------------------------------------------------------------------- Bart · 2015-04-30 18:41 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 · 2015-04-30 19:06 Nice. It keep my thinking... I can't solve it right now. My mind is more artistic than nothing. ---------------------------------------------------------------------- BitBangerUSA · 2015-04-30 19:20 ya got some ambiguity in the part above Q1. 6 <> 0..4 'He shares...' which sailor? last one? each one? ---------------------------------------------------------------------- Blaazen · 2015-04-30 20:05 add Q1: My function says 3121 coconuts. Am I right? ---------------------------------------------------------------------- Bart · 2015-04-30 20:08 Quote from: BitBangerUSA on April 30, 2015, 09:20:07 pm6 <> 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. Quote from: BitBangerUSA on April 30, 2015, 09:20:07 pm'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 · 2015-04-30 20:10 Quote from: Blaazen on April 30, 2015, 10:05:47 pmadd 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 · 2015-04-30 20:19 So should we send you PMs with answers and later you will announce winner ? ---------------------------------------------------------------------- BitBangerUSA · 2015-04-30 20:23 Quote from: Bart on April 30, 2015, 10:08:51 pmQuote from: BitBangerUSA on April 30, 2015, 09:20:07 pm6 <> 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. Quote from: BitBangerUSA on April 30, 2015, 09:20:07 pm'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 · 2015-04-30 20:33 Quote from: BitBangerUSA on April 30, 2015, 10:23:56 pmseems 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 · 2015-04-30 20:48 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 · 2015-04-30 21:10 Following Numberphile are we? https://www.youtube.com/user/numberphile/videos ---------------------------------------------------------------------- taazz · 2015-04-30 21:19 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; Quote from: BitBangerUSA on April 30, 2015, 10:48:21 pmthe 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 · 2015-05-01 00:10 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 · 2015-05-01 02:21 Quote from: taazz on April 30, 2015, 11:19:19 pmStep 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 · 2015-05-01 07:24 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. ---------------------------------------------------------------------- marcio2003 · 2015-05-01 16:27 I am sorry for my previous posted code. The solution is more simple than everything. Have n solutions to solve easy way with: Part_Per_Sailors( n ) = 1204 * n - 820 Amount_ Initial( n ) = 15625 * n - 12504 Is it the ultimate? What's the next steep? Code: [Select]procedure TForm1.B1Click(Sender: TObject); var   n: integer; begin   StringGrid1.Cells[ 0, 0 ]:= 'Solution';   StringGrid1.Cells[ 1, 0 ]:= 'AmountInitial';   StringGrid1.Cells[ 2, 0 ]:= 'FinalQuote/Sailors';   StringGrid1.AutoAdjustColumns;   for n:= 1 to 10 do { Ten initial solutions }   begin     StringGrid1.Cells[ 0, n ]:= IntToStr( n );     StringGrid1.Cells[ 1, n ]:= IntToStr( 15625 * n - 12504 );     StringGrid1.Cells[ 2, n ]:= IntToStr( 1024 * n - 820 );   end; end; ---------------------------------------------------------------------- Bart · 2015-05-01 16:27 Quote from: eny on April 30, 2015, 11:10:22 pmFollowing Numberphile are we? https://www.youtube.com/user/numberphile/videos Yep! Bart ---------------------------------------------------------------------- marcio2003 · 2015-05-01 16:32 I am sorry one more time: Part_Per_Sailors( n ) = 1024 * n - 820 ---------------------------------------------------------------------- Eugene Loza · 2015-05-02 04:03 Finally Q2: Q = 15625*Ni + 3121; where Ni=0,1,2,3... and Q = 15625*Ni + 6246; for Q5 Got this by demanding 8 times both sides of the equation be even, i.e. N=2N`+1