Monkeys and coconuts. - (Brady: Monkeys and coconuts?)
Yeah, so this is an old problem that was set
by a guy called Ben Ames Williams in The
Saturday Evening Post in the in the
1920s. They were inundated with
frustrated readers, desperate to know
the answer, couldn't work it out. In fact
the the editor at the time who's a guy
called George Horace Lorimer - I think
more people should be called Horace
nowadays - George Horace Lorimer
wrote to Williams who'd set the problem
and was like, you know for the love of
Mike what's the answer? Dunno why he used
Mike but okay. It was also popularised by
Martin Gardner later on, it's one of his
problems; but yeah so I thought I thought
we could we could talk about the monkey
and the coconut problem.
So basically the story goes that you've
got five sailors and they're shipwrecked
on a desert island, and there's a monkey
as well. And they go round and they
collect a bunch of coconuts and then
they go to sleep. In the middle of night
one of them wakes up, he's looking at the
coconuts, he thinks there's going to be
trouble in the morning so he goes over,
he starts separating them out you know
amongst the five sailors and then
there's one left over which
he chucks to the monkey who's watching
the whole thing right? He stashes his
pile, hides it, and then puts the rest
together puts it back in the middle. So
then the next sailor wakes up and he
hasn't realised what's happened, he does
the same thing, okay? So he stashes a pile,
gives one to the monkey and then puts
the rest together. And then the next
sailor wakes up and he hasn't realised,
he does the same thing. Each time the
monkey gets one but the pile of course
is getting smaller and smaller and
smaller and smaller. Anyway come morning
time all the sailors have done this. The
pile's got pretty rubbish by this stage
and they all realised that there's been
a bit of naughtiness going on in the
middle of the night. But none of them say
anything cause they're all feeling
guilty, so then they just go ahead and
they they separate the pile and it goes
evenly five ways,
okay, the monkey doesn't get one this
time. So then the question is how many
coconuts were there to begin with?
Probably people should pause at this
point and go away and try to calculate it.
Answer is - (Brady: Drumroll please!)
Right, 3121.
Okay? Now that's seems a bit
unsatisfactory so why is that the answer?
So to try and understand where
this number comes from we're going to
begin by trying to solve a slightly
easier problem, okay, and the problem we're
going to solve is; in the scenario we
described the monkey didn't get one on
the, in the final separation right? Now
we're going to say he does. Here's what's
going on right, so you start off with
some coconuts let's call it C naught, the
original amount of coconuts. And what
happens to your C naught? Well you give
one to the monkey, okay, and the rest get
separated five ways so each pile
contains s1- - (Brady: What does s stand for?)
That's just the number in the piles when
you do the first separations,
okay, and one for the monkey. Then that
first sailor takes his pile, hides it, how
many coconuts are you left with? Well
you're left with 4s1, right, because
there's four piles left. Then that four
get separated, one gets given to the
monkey, and the rest go five ways. In this
case it continues all the way down right,
okay, because at each stage, even the
very last stage, the monkey gets one. So
on the final separation you have the
following; so the fifth pile has four
times s5, and this one again will go five
ways, with the one left for the monkey. So
this is the sort of, you know, the problem.
What you're really after is this number
C naught, which is the original number of
of coconuts, so we want to relate this
guy to this guy. And we end up with the
following equation which, as I'm going to
write it it's not particularly
illuminating but let me just write it
anyway. - (Brady: Where'd that come from?)
You've got a bunch of equations
here and you can just eliminate- say from
these two equations you could eliminate
s1, and then give yourself C0 in
terms of s2 and then you keep iterating
that process and you end up with this
equation, okay? - (I'm taking your word for it.)
Yeah it's tedious. This is an example of
a linear Diophantine equation, it's got-
it's a linear equation and it's got- it's
Diophantine because we're looking for
integer solutions, these guys have got to
be integers. Now there are standard
methods for solving these kinds of
things, laid down by Euclid. There is an
ingenious solution to this problem which
which I particularly like. It's sometimes
attributed to Dirac, the great Dirac. He
himself sort of tried to deny that he'd
come up with it, said he'd got it from a guy
called Whitehead; so it's not clear where
the original solution came from but
anyway Dirac seems to be the first
point of contact for this.
The idea is to consider negative
coconuts. Let me just rewrite this
equation a little bit; so this first
number here this 1,024 is actually 4 to
the power 5. Okay this is just useful to
to know, to see some structure in the
equation. This number here is 5 to the
power 6, and this number here is 5 to
the 6 minus 4 to the 6. You can check
that they happen to be the same numbers;
and of course it's related to the 4s
and the 5s that are in the original
problem. So the first thing you notice
about this equation is it has a symmetry.
What you can notice is if I take a C
naught, if I have some solutions C naught
of this equation, if I happen to know a
solution; and I shift it by 5 to the 6
and at the same time I shift the s6 by
4 to the 5 it will still be a solution.
You know, you can see that. Just add 5 to the 6
to C naught, you get- then you'll get a
correction on this side of 4 to the 5
times 5 to the 6. And if you add 4 to the
5 to s6 you get a correction of 5 to the 6
times 4 to the 5. The equation's still
solved, ok? So all I need to know is find
one solution then I'll have an infinite
number, I just keep adding these values
and I still have solutions. So actually
there's an infinite number of solutions to
this problem; if there is one there's an
infinite number. So all I have to do is
come up with one. And it doesn't matter if
it's made out of negative or positive
coconuts, all I do is I just get the
negative value and I keep adding this until
I get the first positive value - that's
the idea. And then you see it's really easy
to find an answer with negative coconuts,
you just rearrange the equation slightly.
Bring this 4 over to this side, okay, and
then do a little manipulation; you should
be able to convince yourself that this
equation now holds. Ok so what I've done
here is I've taken this 5 to the 6
and factored it out, and I've taken this
4 to 6 over and I've again factored
it out of factor of 4 to the 5. Now it's
easy to spot a solution to this equation
now; can you spot it Brady? - (No.)
It's easy, come on. Just make both sides
naught, ok? If you make both sides naught
then that corresponds to C naught is
equal to minus 4, and s6 is equal to
minus 1. That's of course minus four
coconuts which is ridiculous; but it can
see it makes sense actually. Think
about what happens if you start with
minus 4 coconuts; minus four coconuts - give
one to the monkey how many of you got? Minus
five. Minus five divides equally between five,
so each pile then has minus one coconuts
in it. Four of them get put into the next
batch so you have minus four in the next
batch and the process is just- it's sort
of, it's the same at each stage and this
is why minus four works. But of course who
has minus four coconuts? So the answer is
just to add 5 to the 6, because remember
I can just add 5 to the 6 to any
answer and it gives me another answer.
The smallest positive integer is of
course 5 to the 6 minus 4, which is in
this case 15621. Okay? So that's the
solution to this simpler problem, okay?
(Brady: It's a bigger number?) - It's a bigger
number; well the monkey's getting more
coconuts this time right? But actually
it's kind of weird, the monkey gets one
more coconut in the end so you
need twelve thousand more coconuts
to begin with, it's kind of crazy. So now
let's just think about the original
problem that we wanted to solve. And the
idea is is fairly similar, except you
need some blue coconuts. - (Brady: Blue coconuts?)
You need some blue coconuts, yeah. So what we're
going to do is, we're going to take our
original pile but what we're going to do
is we're going to add four blue
coconuts to the pile; and you forget
about the monkey. So now what happened
was you've got your one coconut that
you gave to the monkey, in the
original problem, but now you're going to
put that with the four blue coconuts,
that makes five. That splits evenly
between five so this is where the trick
comes in. So what you do is you add four
blue coconuts, forget the monkey; the first
sailor wakes up in the night, splits them
five ways puts one blue coconut on four
piles, four different piles,
keeps their blue free pile for himself
and stashes it.
Now the problem is very simple; first
stage it just splits five ways, okay, and
then you go to the next stage and these
you lose one pile, so it goes down to
four, and then you split that one five
ways. Now what you can clearly see as
you're doing this is that the pile of
total number of coconuts, blue and
ordinary ones, is depleting by
four-fifths at each stage, that seems clear right?
These are tildes. So by the time you've
got to the last step the pile of
coconuts gets depleted by four-fifths to
the power of five, because you've done five
steps. But these aren't actually the
amount of coconuts that we want, okay?
This isn't quite the numb- we
want the un-tilded numbers. So the first
step, this number here, this C naught tilde,
is of course C naught plus four.
This C5 tilde, which is C five plus four,
okay which is the number of coconuts
that you ended up with; now this number
here is a multiple of five, right? Because
remember in the original story
laid down by Williams the last pile
really does split amongst five people
and there's not one left over for the
monkey. So this should be a multiple of
five let me just call that 5n. So
this is now the problem that you're
looking at. So let me rearrange it slightly,
let me write it as 5 to the 5, 5n plus 4,
just multiplying through by this 5 to
the 5, 4 to the 5, C naught plus 4. Now
again I've got a linear Diophantine
equation again, I can I could use the
this standard methods blah blah blah but
I'm not going to do that we're going to
be clever about it. Let me just call this
number- well I I mean I know what I
called it, I called it C5 tilde, okay? And this
is C naught tilde. So now I- if I'm
looking for integers I know that C5
tilde and C naught tilde are integers,
they certainly are.
If I find a solution C naught tilde then
I can certainly add to it 5 to the 5, and
similarly to C5 tilde I can always
add to that 4 to the 5. By the
same logic as in the previous case. I go
for the easiest case, that C naught tilde
and C5 tilde are both zero to solve
this equation. Now is that a good solution?
Okay so let's see. If C5 tilde is 0
that implies that n is minus 4/5, which
is not so good because that's not an
integer.
Ok so that hasn't worked, so then we go
to our next solution which is of course
C5 tilde, we just have to add 4 to
the 5 to it.
4 to the 5, okay now this is good because
that implies the n is equal to 4 to the
5 minus 4/5 if we rearrange this
equation. So that is, I think 204. So that
is an integer solution, so this guy works.
So we just have to work out what a
corresponding C naught is. The
corresponding C naught tilde is 0 plus 5
to the 5, so it's 5 to the 5. So C naught
tilde is 5 to the 5, which means that C
naught is 5 to the 5 minus 4 which is
3121.
You ever want to know about how many
coconuts you need to feed the
shipwrecked guys and the monkeys? There
you go, job done.
(Brady: You did on the back of an envelope!)
Literally - ah front of an envelope innit? But anyway. So
there you go, quite quite you know, just a bit of fun,
one of these recreational maths
problems. But erm- - (Brady: Do you think that was)
(really simple?) - I mean it was never
going to be simple because at the end of
the day, you know, it had people crying
left, right and centre to the Saturday
Evening Post begging them for the
solution, but there it is.