Coconut Problem - Challenging

Printable View

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 $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 $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,
$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.
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 $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}$
Jan 26th 2007, 05:15 PM
Ideasman

Quote:

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.