Wikipedia:Reference desk/Archives/Mathematics/2011 February 10

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 10

Need help with puzzle. No solution please

The following puzzle has given me absolute hell:

An island is inhabited by five men and a pet monkey. One afternoon the men gathered a large pile of coconuts, which they proposed to divide equally among themselves the next morning. During the night one of the men awoke and decided to help himself to his share of the nuts. In dividing them into five equal parts he found that there was one nut left over, which he promptly gave to the monkey. He then hid his one-fifth share, leaving the rest in a single pile. Later during the night, another man awoke with the same idea in mind. He went to the pile, divided it into five equal parts, and found that there was one coconut left over. This he gave to the monkey, and then hid his one-fifth share, restoring the rest to one pile. During the same night, each of the other three men arose, one at a time, and in ignorance of what had happened previously, went to the pie, and followed the same procedure. Each time, one coconut was left over, and it was given to the monkey. The next morning all five men went to the diminished coconut pile and divided it into five equal parts, finding one coconut left over. What is the least number of coconuts the original pile could have contained?

---

Isn't the premise flawed? It seems like if the original pile had n coconuts, where n is a number divisible by 5 with a remainder 1, then each time a man takes n/5 + 1 share away, he makes the pile a multiple of 5, and therefore there would be no coconut left for the monkey. i.e. If there were 51 coconuts originally, the guy divides them into 5 equal piles with 1 left over, takes his 1/5 (10 coconuts) and hides it, then gives 1 to the monkey, you have 40 coconuts, and that is clearly evenly divisible by 5.

If anyone could point me in the right direction, I'd be much obliged. Please no solution though!

Thanks,

170.140.169.129 (talk) 05:10, 10 February 2011 (UTC)

It's no surprise that this puzzle is giving you hell, because in fact this puzzle is specifically designed to give people hell. :-) It's a very famous puzzle; it was first introduced to a wide audience in a short story called "Coconuts" by Ben Ames Williams, published in 1926 in the Saturday Evening Post. In the story, a man named Wadlin is an accountant who works for a building contractor named Dean Story, whose competitor is Marr. Both Story and Marr intend to place bids on a building contract. The night before the bids are due, Wadlin, knowing Marr’s love of puzzles, gives this problem to him. Marr stays up till dawn trying to solve it and thus misses the deadline, allowing Story to win the bid at a comfortable profit. (Mr. Williams didn't include the solution to the puzzle in his story. In the first week after it was published the Post received over 2,000 letters from readers asking for the answer or offering solutions. The editor-in-chief, George Horace Lorimer, sent a desperate telegram to Williams that read, "FOR THE LOVE OF MIKE, HOW MANY COCONUTS? HELL POPPING AROUND HERE.")

Here's an example to see why the premise isn't flawed, at least: Start with 21 coconuts. Then you can give one to the monkey, split the remainder into five piles of 4 coconuts each, take one pile, and put the remaining 16 coconuts back into a pile. Now 16 gives a remainder of 1 when divided by 5, so at least the second man can do his thing. Of course, with this example you run into a problem with the third man, but at least it shows that you don't necessarily end up with a multiple of 5 after the first man is done.

Here is a hint about the solution: It's not unique. If you find one solution to the problem, you can always add a certain number of coconuts to get another valid solution. So there are in fact infinitely many solutions. This is why, if you try to write out equations to solve, you will find that you have one fewer equation than the number of variables, so you can't solve the system explicitly. —Bkell (talk) 05:22, 10 February 2011 (UTC)

By the way, there is an excellent presentation of this problem in the chapter called "The Monkey and the Coconuts" in The Colossal Book of Mathematics by Martin Gardner, including a very clever solution that uses ARTNGVIR PBPBAHGF (possible spoiler there, encrypted with ROT13). —Bkell (talk) 05:27, 10 February 2011 (UTC)

Well, we know that the pile in the morning is one more than a multiple of 5. So it's $5n+1$ for some $n$. We also know that it should be a multiple of 4, since that's what the fifth man left us with. So $5n+1\equiv 0$ (mod 4). What form does that tell us $n$ needs to be in? Once you have that, what's the expression for the size of the pile before the fifth man got to it (expressed without fractions)? Can you find a pattern?--203.97.79.114 (talk) 08:24, 10 February 2011 (UTC)

What I'd to is to work with fractional coconuts. Start out with X coconuts. Remove one for the monkey, and subtract a fifth of the remainder. Do this five times, then remove one coconut for the monkey and divide by five. The result is how many coconuts each man gets in the final division, and has the form ${\tfrac {4^{5}X-M}{5^{6}}}$ for some M that's easy to compute. This fraction, at least, must be an integer, so $4^{5}X\equiv M{\pmod {5^{6}}}$. Because $4^{5}$ and $5^{6}$ are relatively prime, Euclid's algorithm can be used to find a unique solution to that, and thus directly the least positive X that matches. It then remains only to verify that the intermediate divisions also come out even for this X. –Henning Makholm (talk) 09:51, 10 February 2011 (UTC)

(But the strategy sketched by 203.97 is probably simpler in practice, particularly with pen and paper -- it avoids most or all of the long divisions I'd need. –Henning Makholm (talk) 09:59, 10 February 2011 (UTC))

But even easier is to note Bkell's hint, find the fixed point of the iterated function

$x_{n+1}={\frac {4}{5}}(x_{n}-1)$

to locate a theoretical but unrealistic solution, and then use the fact that all solutions are congruent mod 5⁶ (because there are six divisions into five parts) to find the smallest positive solution. Gandalf61 (talk) 10:40, 10 February 2011 (UTC)

Very clever, that. It reduces the actual calculation to almost nothing. But I think I find the link from "because there are six divisions into five parts" to "all solutions are congruent modulo 5⁶" a bit too sketchy for comfort. I don't think I'd be convinced it works until I think through something like the abstract argument I present above. –Henning Makholm (talk) 12:38, 10 February 2011 (UTC)

rot13 question: including spoiler.

“ V qba'g trg vg. V jebgr n crey cebtenz gb fgrc guebhtu rirel cvyr fvmr sebz bar gb n ovt ahzore, naq tb ba gb gur arkg bar vs vg pbhyqa'g jbex guebhtu gur fgbel nf jevggra. ohg vg qvq abg fgbc hagvy svsgrra gubhfnaq fvk uhaqerq naq gjragl-bar! Gung, ubjrire, ivbyngrf gur pbaqvgvbaf bs gur fgbel, nf gur fgbel ersref gb n "cvyr" bs pbpbahgf, naq guvf ahzore qbrf abg nyybj gur fgbel gb or sbyybjrq - vg vf abg cbffvoyr gb pbhag be qvivqr be uvqr gung znal pbpbahgf va gur zvqqyr bs gur avtug, naq vg jbhyqa'g whfg or n "cvyr" bs pbpbahgf. fb, vg jbhyq frrz gurer vf ab fvmr bs "cvyr" gung jbhyq zrrg gur pbaqvgvbaf bs gur fgbel. Vf zl nafjre ernyyl gru "pbeerpg" bar? Cyrnfr uryc. ”

Yes, the answer that you got from your Perl program is correct. As with many mathematical problems, you have to make certain simplifying assumptions - in this case, we assume coconuts with an infinitesimal volume and pirates who can count infinitely quickly and always accurately. Also, the pirates must be very unobservant, as the number of coconuts before the final division in the morning is less than a third of what is was the night before. Gandalf61 (talk) 13:57, 10 February 2011 (UTC)

The pirates can be plenty observant—none of them will want to draw attention to their own treachery. But they must be deaf to not be woken by the shuffling of so many coconuts. --Tardis (talk) 15:12, 10 February 2011 (UTC)

Please calculate the total taxi fare and other fees from Itoman, Okinawa all the way to Cape Soya, Hokkaido.

Taxis are notoriously overpriced in Japan. Therefore, I have a years-old curiosity: How much would it cost to ride a taxi from Itoman City, Okinawa Prefecture, all the way up to Cape Soya? Please calculate the base fare, then add in the other ancillary costs like ferry tickets, highway tolls, feeding and lodging the driver, possibly fuel, and all the other costs to be taxied from the southernmost roadable point in Japan to the northernmost. I would most appreciate any mathematician being able to finally put my curiosity to rest. --70.179.173.95 (talk) 07:22, 10 February 2011 (UTC)

The link http://maps.google.com gives you the distance (3.619 km) and mark which roads are priced. Bo Jacoby (talk) 10:11, 10 February 2011 (UTC).

H2: equidistant curve tangent to a given line

In the hyperboloid model of the hyperbolic plane (where t is imaginary), I have two lines L and M, defined by their unit normals u and v. If |u·v| > 1 they are ultraparallel, and some curve equidistant to L is tangent to M, at point P. Here's my question: Can I find u·P (a function of the signed distance between the nearest points of L and M) without generating P? —Tamfang (talk) 08:00, 10 February 2011 (UTC)

Failing that, is there a more efficient way to get P than with two cross-products? —Tamfang (talk) 17:54, 10 February 2011 (UTC)

differentiation by first principles

how to differentiate е to the power root x? —Preceding unsigned comment added by 180.215.15.1 (talk) 12:55, 10 February 2011 (UTC)

$d(e^{\sqrt {x}})=e^{\sqrt {x}}d({\sqrt {x}})=e^{\sqrt {x}}d(x^{\frac {1}{2}})=e^{\sqrt {x}}{\frac {1}{2}}x^{{\frac {1}{2}}-1}dx={\frac {e^{\sqrt {x}}}{2{\sqrt {x}}}}dx$

Bo Jacoby (talk) 13:44, 10 February 2011 (UTC).

Basic Probability

This question should be easy, but I am confused. You have one ordinary pack of 52 playing cards and you select 5 at random. What is the probability of drawing 3 King's in your sample? I know that the probability of one king is 4/52, but the fact that the sample is 5 and they are asking for the probability of drawing 3 of them leaves my simple brain a bit confused :( —Preceding unsigned comment added by 85.210.82.116 (talk) 13:32, 10 February 2011 (UTC)

See hypergeometric distribution and binomial coefficient. The deck contains 4 kings and 48 non-kings. You can pick 3 kings out of 4 in ${\binom {4}{3}}=4$ ways. You can pick 2 non-kings out of 48 in ${\binom {48}{2}}=1128$ ways. You can pick 5 cards out of 52 in ${\binom {52}{5}}=2598960$ ways. The probability is ${\frac {4\cdot 1128}{2598960}}=0.00174$. Bo Jacoby (talk) 14:11, 10 February 2011 (UTC).

And add 48/2598960 if four-king hands also count. The Poker probability article might also be of interest. –Henning Makholm (talk) 14:16, 10 February 2011 (UTC)

In lowest terms, these probabilities are 94/54145 and 19/10829. —Tamfang (talk) 17:58, 10 February 2011 (UTC)

Compactly generated space

If X is compactly generated and Y is locally compact is the function space X^Y compactly generated? Money is tight (talk) 13:40, 10 February 2011 (UTC)

Probability question

Say you choose k integers independently and uniformly randomly in the range 1 through n. What value of k will make the probability that all the numbers are different equal to 0.5? It seems to me that, as n becomes large, the solution is around k = c * sqrt(n) for some constant c. Is this correct? If so, what is the limiting value of c as n tends to infinity? Experminetally it seems a little over 1 for reasonably large n, but I'm wondering if in the limit it might be exactly 1? 86.181.206.175 (talk) 14:24, 10 February 2011 (UTC).

The birthday paradox is relevant to this discussion. I don't have time to reply in detail, but it seems that the following formula holds:

$k\approx {\sqrt {2n\ln \left(2\right)}}.$

Sławomir Biały (talk) 14:36, 10 February 2011 (UTC)

The exact probability is ${\frac {n!}{n^{k}(n-k)!}}$. Using Stirling's approximation gives $(1-k/n)^{k-n-1/2}e^{k}\;\!$, and the logarithm of this is ${\frac {-k^{2}}{2n}}+O\left({\frac {k}{n}}\right)$. Equating this to $\ln(1/2)$ gives Sławomir's result, and if you want a better one (which will have the same constant c) you can take higher order terms for the logarithm Taylor series and maybe even Stirling's approximation. -- Meni Rosenfeld (talk) 15:08, 10 February 2011 (UTC)

Thank you both. 86.179.119.40 (talk) 18:36, 10 February 2011 (UTC)

• For the record, I think there is a typo above. I think that formula should be $(1-k/n)^{k-n-1/2}e^{-k}\;\!$ 86.181.169.141 (talk) 14:07, 27 April 2011 (UTC)

Arc length integral

Hey. In my textbook we are asked to show that the lower sum of ${\sqrt {1+(f')^{2}}}$ from a to b is less than or equal to the length of f(x) from a to b, which in turn is less than or equal to the upper sum of ${\sqrt {1+(f')^{2}}}$ from a to b, for any partition of [a,b]. The arc length of f on an arbitrary partition {t_i} of [a,b] is defined to be $\sum _{i=1}^{n}{\sqrt {(t_{i}-t_{i-1})^{2}+[f(t_{i})-f(t_{i-1})]^{2}}}$. If I factor out (t_i-t_i-1)², I have a Riemann sum of ${\sqrt {1+(f'(t_{j}))^{2}}}$ for some t_j in [t_i-1,t_i]. But how do I do this? Wouldn't the upper sum and lower sum always be equal (because t_j depends both on t_i-1 and t_i) ? And how can you say ${\sqrt {1+(f')^{2}}}$ if it is for a specific t_j and not for f' in general? Thanks. 72.128.95.0 (talk) 22:24, 10 February 2011 (UTC) ??? —Preceding unsigned comment added by 72.128.95.0 (talk) 03:43, 13 February 2011 (UTC)