# Thread: Coconut Problem - Challenging

1. ## Coconut Problem - Challenging

The Ultimate Puzzle Site - Brain-Teasers

Same question as there, but this problem only deals with 3 sailors and instead of splitting 1/5, they split 1/3 each time. Does this method work? If so, can someone help me complete it; I don't like their way of solving it.

Let n = total # of coconuts. Then,

(n - 1) - 1/3(n - 1) is after the 1st sailor;

Then, let k = (n - 1) - 1/3(n - 1), and after the 2nd sailor will be:

(k - 1) - 1/3(k - 1)

Then, let m = (k - 1) - 1/3(k - 1), and after the 3rd sailor will be:

(m - 1) - 1/3(m - 1);

Finally, when they all wake up and give 1 away and then split the remaining, we have to do it one more time.

Let n = (m - 1) - 1/3(m - 1), and thus the final answer is:

(n - 1) - 1/3(n - 1)...

Ok, now the tricky part is substituting that in. I have a whole white board filled up with substitutions, and it gets extremely messy with parentheses etc. Can anyone help?

2. I can do the problem using the Chinese Remainder Theorem but I do not know if you heard of it?

3. Originally Posted by ThePerfectHacker
I can do the problem using the Chinese Remainder Theorem but I do not know if you heard of it?
Sounds familiar from discrete- would you be able to do the substitutions instead, assuming my method works?

4. Originally Posted by Ideasman
Sounds familiar from discrete- would you be able to do the substitutions instead, assuming my method works?
I tried doing it, and got:

({(n - 1) - 1/3(n - 1)} - 1) - 1/3({n - 1) - 1/3(n - 1)} - 1)) for the first substitution, then plugging this in for m and then n etc etc by the time you're finished substituting you have like a page of algebra.

5. Originally Posted by Ideasman
I tried doing it, and got:

({(n - 1) - 1/3(n - 1)} - 1) - 1/3({n - 1) - 1/3(n - 1)} - 1)) for the first substitution, then plugging this in for m and then n etc etc by the time you're finished substituting you have like a page of algebra.
It works with the algebra approach, I know understand what you meant. Know you need to clean up the mess and then find the smallest $n$ that makes the fraction a whole number. Which leads to solving a congruence (ax = b (mod n) ).

6. Originally Posted by ThePerfectHacker
It works with the algebra approach, I know understand what you meant. Know you need to clean up the mess and then find the smallest $n$ that makes the fraction a whole number. Which leads to solving a congruence (ax = b (mod n) ).
Only problem is with this approach I get lost half-way through the substitutions having like 50 different parentheses.

7. Originally Posted by Ideasman
Only problem is with this approach I get lost half-way through the substitutions having like 50 different parentheses.
Parentheses never give no trouble even when there are many of them, because numbers are my friends. But there is one thing in group theory, if you ever take it, that I would imagine greatly confuses students even more than many paranthesis. It is called the factor group of a factor group. To explain basically you can think of a group as a set. A factor group is a set of sets. For example {{1,2,3},{4,2,1}}
Now the factor group of that is the set of sets of sets.
Thus,
{{{1,4},{1,2,3}},{{3,5},{4,5,6}}}
And you need to find how they add together.
I would imagine that gives students great difficutly.

8. Originally Posted by Ideasman
Only problem is with this approach I get lost half-way through the substitutions having like 50 different parentheses.
Aha! The power of computers. Ok, so I got:

[[[16/81*n-16/81]-8/27]-4/9]-2/3

9. Now how would I find the smallest n that makes it a whole number?

10. Originally Posted by Ideasman
Aha! The power of computers. Ok, so I got:

[[[16/81*n-16/81]-8/27]-4/9]-2/3
Which is equivalent to (16n)/81 - 130/81

11. Originally Posted by Ideasman
Which is equivalent to (16n)/81 - 130/81
Thus, you want to solve,
$16x\equiv 130 \mod 81$
We can divide by two because $\gcd(2,81)=1$,
$8x\equiv 75 \mod 81$

Using continued fractions we get that $x=60$ is the smallest positive integer which satisfies this congruence.

Since this answer is not correct means that your formula that you gave me is wrong.

12. Hello, Ideasman!

Ah, the "Monkey and the Coconuts" problem with three sailors.

I have an algebraic approach to this problem . . . lengthy but simple.

Let $N$ = number of coconuts.

Sailor #1 divides $N$ coconuts by 3 and there is a remainder of $1$.
. . $N \:=\:3A + 1$ [1]
He hides his $A$ coconuts and puts $2A$ coconuts back in the pile.

Sailor #2 divides $2A$ coconuts by 3 and there is a remainder of $1$.
. . $2A\:=\:3B + 1\quad\Rightarrow\quad A \:=\:\frac{3B + 1}{2}$ [2]
He hides his $B$ coconuts and puts $2B$ coconuts back in the pile.

Sailor #3 divides $2B$ coconuts by 3 and there is a remainder of $1$.
. . $2B \:=\:3C + 1\quad\Rightarrow\quad B\:=\:\frac{3C+1}{2}$ [3]
He hides his $C$ coconuts and puts $2C$ coconuts back in the pile.

In the morning, they divide $2C$ coconuts by 3 and there is a remainder of $1$.
. . $2C\:=\:3D + 1\quad\Rightarrow\quad C \:=\:\frac{3D+1}{2}$ [4]

In [4]: since $C$ is an integer, $D$ must be odd: . $D \:=\:2p-1$
Substitute: . $C\:=\:\frac{3(2p-1)+1}{2}\:=\:3p - 1$

Substitute into [3]: . $B \:=\:\frac{3(3p-1) + 1}{2}\:=\:\frac{9p-2}{2}$
. . Since $B$ is an integer, $p$ must be even: . $p\,=\,2q$
Substitute: . $B \:=\:\frac{9(2q) - 2}{2}\:=\:9q - 1$

Substitute into [2]: . $A\:=\:\frac{3(9q-1) + 1}{2}\:=\:\frac{27q - 2}{2}$
. . Since $A$ is an integer, $q$ must be even: . $q \,=\,2r$
Substitute: . $A\:=\:\frac{27(2r)-2}{2}\:=\:27r-1$

Substitute into [1]: . $N \:=\:3(27r - 1) + 1\:=\:81r - 2$

For the least positive value of $N$, let $r = 1$.

Therefore: . $\boxed{N \,=\,79}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Check

$79 \div 3 \:=\:26,\text{ rem.1}$

$52 \div 3 \:=\:17,\text{ rem.1}$

$34 \div 3 \:=\:11,\text{ rem.1}$

$22 \div 3\:=\:7,\;\text{ rem.1}$

13. Originally Posted by ThePerfectHacker
Thus, you want to solve,
$16x\equiv 130 \mod 81$
We can divide by two because $\gcd(2,81)=1$,
$8x\equiv 75 \mod 81$

Using continued fractions we get that $x=60$ is the smallest positive integer which satisfies this congruence.

Since this answer is not correct means that your formula that you gave me is wrong.
If it's wrong, how is it that Soroban came up 79, which ironically makes my expression an integer? I don't think it's coincidence.