Coconut Problem - Challenging

• Jan 25th 2007, 07:29 PM
Ideasman
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?
• Jan 25th 2007, 07:34 PM
ThePerfectHacker
I can do the problem using the Chinese Remainder Theorem but I do not know if you heard of it?
• Jan 25th 2007, 07:36 PM
Ideasman
Quote:

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?
• Jan 25th 2007, 07:38 PM
Ideasman
Quote:

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.
• Jan 25th 2007, 07:54 PM
ThePerfectHacker
Quote:

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 $\displaystyle n$ that makes the fraction a whole number. Which leads to solving a congruence (ax = b (mod n) ).
• Jan 25th 2007, 07:57 PM
Ideasman
Quote:

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 $\displaystyle 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.
• Jan 25th 2007, 08:04 PM
ThePerfectHacker
Quote:

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.
• Jan 25th 2007, 08:07 PM
Ideasman
Quote:

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
• Jan 25th 2007, 08:09 PM
Ideasman
Now how would I find the smallest n that makes it a whole number?
• Jan 25th 2007, 08:11 PM
Ideasman
Quote:

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
• Jan 26th 2007, 06:17 AM
ThePerfectHacker
Quote:

Originally Posted by Ideasman
Which is equivalent to (16n)/81 - 130/81

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

Using continued fractions we get that $\displaystyle 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.
• Jan 26th 2007, 06:39 AM
Soroban
Hello, Ideasman!

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

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

Let $\displaystyle N$ = number of coconuts.

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

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

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

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

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

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

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

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

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

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

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

Check

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

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

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

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

• Jan 26th 2007, 05:15 PM
Ideasman
Quote:

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

Using continued fractions we get that $\displaystyle 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.