Coconut Divisibility Problem
Brian Rothstein
Nov 01, 2000
1 Problem
N boys go camping one weekend. While in the wilderness, the
boys collect a number of coconuts. They take the coconuts back to
their cabin and agree to divide them up equally before they leave
the next morning. That night, one of the boys wakes up (from
excitement) and decides to gather his share of coconuts right that
moment. However, when he counts the coconuts he finds that the
number is not divisible by n, but by giving one coconut to the
pet monkey, the remaining amount is divisible by n, so the
boy gives one coconut to the monkey and takes 1/n of the
rest for himself.
Later that night another boy wakes up (also from excitement) and
decides to gather his share of coconuts right that moment (not
realizing that the other boy has already taken his share.) When
he counts the number of coconuts he finds that if he gives one to
the pet monkey then the remaining amount will be divisible by n,
so the boy gives one coconut to the monkey (who has already
disposed of the previous one) and takes 1/n of the rest
for himself.
Similarly, all of the n-2 other boys awake one by one in the
middle of the night in order to get their share of coconuts, and
all of them have to give one coconut to the monkey before taking
1/n of the rest.
In the morning, as the boys are leaving the cabin, they notice
that there are still some coconuts left. Since each of them has
taken their share, they're not really sure why there should be any
left. Not wanting to think about it too hard, though, they just
decide to split the remaining coconuts evenly since the remaining
amount is exactly divisible by n.
The question, then, is how many coconuts were there to begin with?
Give the minimum possible value.
2 Solution
Let a equal the starting number of coconuts and nb equal the
number of coconuts left in the morning. Also notice that c -c/n = (c)([(n-1)/ n]) so instead of constantly
subtracting 1/n of the remaining amount from the
remaining amount we can simply multiply the remaining amount by
[(n-1)/ n]. Now let x = [(n-1)/ n]. This gives the
following equation:
|
(···(((a-1)x - 1)x - 1)x ···-1)x = nb |
| (1) |
where we subtract 1 and then multiply by x, n times.
|
Þ axn - (x + x2 + x3 + ···+ xn) = nb |
| (2) |
Then by adding and subtracting 1 on the left we get:
|
axn - (1 + x + x2 + x3 + ···+ xn) + 1 = nb |
| (3) |
|
Þ axn - |
xn+1 - 1
x - 1
|
+ 1 = nb |
| (4) |
|
Þ axn = |
xn+1 - 1
x - 1
|
- 1 + nb |
| (5) |
Now substituting back [(n-1)/ n] for x we get:
And since [(n-1)/ n] - 1 = -1/n, we have:
|
a( |
n-1
n
|
)n = -n(( |
n-1
n
|
)n+1 - 1) - 1 + nb |
| (7) |
|
Þ a( |
n-1
n
|
)n = n - n( |
n-1
n
|
)n+1 - 1 +nb |
| (8) |
|
Þ a( |
n-1
n
|
)n = -n( |
n-1
n
|
)n+1 - 1 +n(b+1) |
| (9) |
Now multiplyling by nn on both sides we get:
|
a(n-1)n = -(n-1)n+1 - nn + nn+1(b+1) |
| (10) |
Now suppose that we had a pair (a,b) which satisfied
(10). Notice then that (a+tnn+1, b+t(n-1)n) also
satisfies the equation since the extra tnn+1(n-1)n cancels
out on both sides. Therefore, valid values of a occur at
intervals of tnn+1. From now on I'll just write the equation
like this:
|
a(n-1)n º -(n-1)n+1 - nn (mod nn+1) |
| (11) |
This is equivalent to writing the exact equation:
|
a(n-1)n = -(n-1)n+1 - nn + tnn+1 |
| (12) |
where t is just some integer. This is ok, because in the end if
we're able to get an equation like this:
then this really means
for some integer t. But remember that valid values of a repeat
every nn+1 so another valid value would be a - tnn+1
which simply equals c.
Also notice the following properties of modular arithmetic. Assume
a = b + ct:
|
a = b + ct Û a º b (mod c) |
| (15) |
|
ax = bx + ctx Û ax º bx (mod c) |
| (16) |
|
a+x = b+x + ct Û a+x º b+x (mod c) |
| (17) |
So we can add and multiply with integers in a modular equation
just as we do in a normal equation.
Now consider the integer:
Notice that:
|
Þ yn = |
cnn+1 + (-1)n
(n-1)n
|
|
| (20) |
where c is some integer.
Now going back to (11) and multiplying by yn on both
sides we get:
|
a(n-1)nyn º -(n-1)n+1yn - nnyn (mod nn+1) |
| (21) |
|
Þ a(cnn+1 + (-1)n) º -(n-1)(cnn+1 + (-1)n)- (ny)n (mod nn+1) |
| (22) |
Just lumping the acnn+1 and -(n-1)cnn+1 terms into the
generic tnn+1 term, we get:
|
a(-1)n º -(n-1)(-1)n - (ny)n (mod nn+1) |
| (23) |
Then by multiplying by (-1)n on both sides and noting that
(-1)2n = 1, we get:
|
a º -(n-1) - (ny)n(-1)n (mod nn+1) |
| (24) |
|
Þ a º (-1)n+1(ny)n - (n-1) (mod nn+1) |
| (25) |
Using the fact that y = 1 + n + n2 + ···+ nn, we
have:
|
ny = n + n2 + n3 + ···+ nn+1 |
| (26) |
|
Þ (ny)n = (n + n2 + n3 + ···+ nn+1)n |
| (27) |
Now since every term of this product must be the result of
multiplying n terms chosen from (n + n2 + n3 + ···+ nn+1), every term of the result must be a multiple of
nn+1 except for the one in which we pick n n's. So this
gives:
for some integer d.
Now plugging the value for (ny)n back into (25) and
lumping the dnn+1 with the generic tnn+1 term we get:
|
Þ a º (-1)n+1nn - (n-1) (mod nn+1) |
| (29) |
|
Þ a = (-1)n+1nn - (n-1) + tnn+1 |
| (30) |
Since we can subtract any multiple of nn+1 from a and have
another valid result, just subtract tnn+1 to get:
If n is odd then we have our answer. If n is even, then we must
add back one term of nn+1 to the right in order to make a
positive. So if n is even then we get:
Putting the two cases together we get:
File translated from TEX by TTH, version 2.25.
On 02 Apr 2001, 14:10.