Before I give the solution, I owe it everyone to reveal the original source, which appeared in Scientific American. Here is the exact source:
Scientific American, April 1958.
The Second Scientific American Book of Mathematical Games and Diversions,
Chapter 9, The Monkey and the Coconuts,
Simon and Schuster, pages 104-111
I also would like to complement Sandeep Singh, who happens to be the only person to respond correctly to the puzzle. It was fun trying the puzzle with 2 sailors with my 8 year old, and the 3 sailor version even with adults.
The answer does not lend itself to a video solution, and hence only a text version this time. While there are more correct and technical solutions to the problem, here is one I thought is easier to follow (taken from BBC site):
The reasoning is as follows. Given that the pile of coconuts is divided 6 times into 5 piles, it is then clear that 5 × 5 × 5 × 5 × 5 × 5 = 15625 coconuts can be added to any answer for the number of coconuts to give the next higher answer. Indeed, any integer multiple of 15625 can be added to or subtracted from any answer to obtain another answer. This of course gives us inﬁnitely many negative answers. These all satisfy the equation (11). While there is no small positive integer n that gives rise to a solution to the equation (11), a little trial and error with negative values of n comes up with a solution n = −4, with f = −1. Adding 15625 to this negative solution leads to the smallest positive solution n = 15621.
Imagine the ﬁrst man A waking up to ﬁnd a pile of −4 coconuts. He tosses a positive coconut to the monkey, so there is now a pile of −5 coconuts. He hides his share of −1 coconut, and leaves a pile of −4 coconuts for the second man B to discover. The same thing then happens to B, C, D and E in succession, so there is now a pile of −4 coconuts in the morning. After tossing a positive coconut to the monkey, there is now a pile of −5 coconuts, so each of them has −1 coconut more!
As I am finding with many of these puzzles, as you start to explore the internet, you find a lot more theory behind each of these puzzles. Here are some links for the more mathematically oriented readers: