Seventeen Camels and Where They Can Take You

“Oh, it’s just a trick thing.” – Ben Ames Williams, Coconuts

Here are six puzzles, some of them classics, that don’t look much alike on the surface. After stating them, I’ll give a hint about what they have in common. Then I’ll present solutions that all make use of the same slick trick in one form or another.

Puzzle 1: A wealthy merchant died, leaving seventeen camels to be distributed among three heirs. The merchant’s will stipulated that one half of the camels should go to the eldest heir, one third of the camels should go to the second heir, and one ninth of the camels should go to the youngest heir. The most literal-minded course of action would be to butcher some of the camels, giving eight-and-a-half camels to the eldest heir, five-and-two-thirds camels to the second heir, and one-and-eight-ninths camels to the youngest heir, with the remaining one-eighteenth of a camel left for the vultures. But surely the merchant hadn’t intended such carnage! While they were puzzling over their situation, a passing trader stopped to ask what the problem was. When they explained the impasse they were facing, the trader solved their problem with one simple suggestion. What was it?

Puzzle 2: Five sailors and a monkey were shipwrecked on a desert island. The sailors spent the first day gathering coconuts for food; then they piled all the coconuts together and went to sleep for the night. One sailor woke up and decided to take a fifth of the coconuts while the others slept. The sailor divided the coconuts into five piles with one coconut left over, then hid one of the piles, merged the other four piles, and gave the extra coconut to the monkey. One after another, the other four sailors did the same thing, each one dividing the current pile into five equal piles with one coconut left over, hiding one pile, merging the other four piles, and giving the leftover coconut to the monkey. In the morning the five sailors divided what coconuts were left, and the coconuts came out in five equal shares with none left over. How many coconuts were there in the beginning? (

There are actually infinitely many possible answers to the problem; so the question really asks, What’s the smallest possible number of coconuts in the original pile, if we take the story to be true?)

If that’s too hard to tackle straight off, here’s a warm-up to get you in the right frame of mind: what’s the smallest positive integer that leaves remainder 2 when divided by 3, remainder 4 when divided by 5, and remainder 6 when divided by 7?

Puzzle 3: Suppose your Introduction to Discrete Mathematics teacher taught you a formula that you don’t remember how to prove, involving concepts from graph theory. A graph is a collection of dots (called vertices) together with some line segments or curves (called edges) that connect one vertex to another; we’ll assume there are only finitely many vertices and edges. A graph is said to be connected if there’s a way to travel from any vertex to any other vertex along a path that uses edges of the graph. A cycle in a graph is a path in the graph that starts at a vertex, travels along an edge, then travels along another edge, and so on, eventually returning to the original vertex without reusing any edges. Finally, a graph is called a tree if it contains no cycles. For instance, the graph shown here is not connected because there is no path from vertex a to vertex d; neither is the graph a tree because there is a cycle composed of the edge from a to b, the edge from b to c, and the edge from c to a.

The teacher’s formula, E = V−1, says that the number of edges in a finite tree is always 1 less than the number of vertices. So for instance in the tree shown in the picture below we see 10 vertices and 9 edges.

The trouble is, you’re taking the midterm exam and the teacher has asked you about forests. You remember that a forest is just like a tree except that it doesn’t have to be connected – it’s only required to be free of cycles. So every tree is a forest, but a forest could consist of two trees, or three trees, or even more. The exam problem says: “Suppose the graph G is a forest consisting of two trees. Suppose also that G has ten vertices. How many edges does G have?”

Your cheat sheet has the formula E = V−1 but that only works for trees; it doesn’t apply to forests in general. What do you do?

Puzzle 4: Suppose you have 4 suspect coins, 1 of which is counterfeit (either heavy or light). You also have a pan balance scale. Is it possible in just two weighings to find the bad coin and to determine whether it is heavy or light? If not, what simple additional object would enable you to do it?

Puzzle 5: If you deal out the 52 cards in a randomly-shuffled deck until you find one of the 4 jacks and then stop, how many cards should you expect to have to deal on average?

Puzzle 6: Given a deck of cards numbered 1 through N (with N > 1), not necessarily arranged in order, we define a grand swap as the following N-step procedure: swap the part of the deck that’s above the 1 with the part that’s below the 1; then swap the part of the deck that’s above the 2 with the part that’s below the 2; and continue in this manner, until finally you swap the part of the deck that’s above the N with the part that’s below the N. If one of the “parts” that you’re trying to swap is empty, the swap is equivalent to simply moving the top card to the bottom or vice versa.

For example, suppose we start with 1, 2, 4, 3, with 1 on the top and 3 on the bottom. We swap the cards above the 1 (“all zero of them”!) with the cards below the 1 (all three of them) to get 2, 4, 3, 1. Then we swap the cards above the 2 with the cards below the 2 to get 4, 3, 1, 2. Then we swap the card above the 3 with the cards below the 3 to get 1, 2, 3, 4 (notice that the 1 and the 2 remain in the order they were in before; though two piles are swapped, each pile stays in its original order). Finally we swap the cards above the 4 with the cards below the 4 to get 4, 1, 2, 3.

So, our grand swap sends 1, 2, 4, 3 to 4, 1, 2, 3.

Show that performing N+1 successive grand swaps always brings the deck back to its original order.

* * * * * * * * * * * * * * * * *

HINT

In all these puzzles, there’s an elegant solution in which you add a seemingly extraneous element that can subsequently be discarded.

As an example of adding something to a problem to make it simpler, consider the warm-up puzzle proposed at the end of Puzzle 2 (“What’s the smallest positive integer that leaves remainder 2 when divided by 3, remainder 4 when divided by 5, and remainder 6 when divided by 7?”); call the mystery number N. Since N leaves remainder 2 when divided by 3, N+1 must be exactly divisible by 3. Likewise N+1 must be exactly divisible by 5 and by 7, and since the numbers 3, 5, and 7 are relatively prime (that is, they have no factors in common bigger than 1), N+1 must be divisible by 3 × 5 × 7 = 105. So the answer to the warm-up puzzle is

(N+1) − 1 = 105 − 1 = 104.

For more examples of this “camel trick” in mathematics see the MathOverflow post The 17 camels trick and Tivadar Danka’s blog post The camel principle.

* * * * * * * * * * * * * * * * *

SOLUTION TO PUZZLE 1

The trader says “Borrow my camel!” Now there are 18 camels. The first heir receives one half of 18, or 9, camels; the second heir receives one third of 18, or 6, camels; and the third heir receives one ninth of 18, or 2, camels. This accounts for 9+6+2 = 17 camels. If the apportioning is done in a manner sensitive to the animals’ needs for familiar faces, these 17 camels will be precisely the deceased merchant’s camels, and the trader can ride off on the camel that was lent to the heirs.

This may seem like a purely recreational puzzle, but when seats in a governing body are apportioned based on population counts, one can face similar issues. In those situations, the relevant fractions (1/2, 1/3, and 1/9 in our puzzle) typically add up to 1, but there’s still a thorny problem to be solved if those fractions, when multiplied by the total population, fail to yield whole numbers. An analogous problem of a camelid kind would be: how can three heirs receive 1/2, 1/3, and 1/6 of the merchant’s camels if the total number of camels is 17? Clearly the apportionment can’t be done exactly if we don’t butcher any camels, but how close can we get? And what does “close” even mean in this context? There are many approaches to dealing with this kind of problem; to see how the U.S. handles it, see the Census Bureau post on Methods of Apportionment.

In an alternate version of the puzzle in which the fractions add up to more than 1 rather than less than 1, the trader can help the heirs by stealing a camel and then returning it!

SOLUTION TO PUZZLE 2

Let N be the number of coconuts in the original pile. Imagine an alternate scenario in which the monkey has four coconuts of her own at the start (suppose that they’re blue) and she adds them to the pile, so now there are N ordinary coconuts and 4 blue ones, for a total of N+4. The first sailor to wake will discover that the pile is evenly divisible by five. The sailor divides the big pile into five equal smaller piles. Since there are only four blue coconuts, at least one of the five piles contains none of them. The sailor takes such a pile and hides it, gives one of its coconuts to the monkey, and puts the other four small piles (which collectively contain all four blue coconuts) back together into one big pile. Each sailor does the same thing. During the final division in the morning, the four blue coconuts are left on the side; the monkey reclaims them.

Since the augmented pile (with the blue coconuts included) was evenly divided into fifths five times during the night, it must have contained 55 = 3125 coconuts or some multiple thereof when the sailors went to bed. So the smallest consistent answer N satisfies N+4 = 3125, giving N = 3121.

One can also have a bogus answer in which there are −4 coconuts at the start. If one allows negative coconuts, then the algebraic solutions are precisely the numbers of the form −4 plus a multiple of 3125; the smallest non-bogus answer is −4 + 3125 = 3121.

SOLUTION TO PUZZLE 3

Add an edge joining a vertex in one tree to a vertex in the other tree. Now your two-tree forest has become a single tree on ten vertices, so the teacher’s formula applies: the number of edges is 10−1, or 9. But remember, one of those edges is the extra edge that you added; if you erase it, the number of remaining edges will be 9−1, or 8. In fact, it can be shown that a forest on n vertices that consists of t trees must have n−t edges.

If you’re wondering why adding that new edge turned the two-tree forest into a single tree, note that the added edge that joins the first tree (call it T1) to the second tree (call it T2) cannot create a cycle, because if there were a cycle, it would have to cross from T1 to T2 along some edge and then from T2 back to T1 along some other edge, and there’s only one edge between T1 and T2. On the other hand, the new graph is certainly connected, and since we just learned that it’s free of cycles, it’s a tree.

SOLUTION TO PUZZLE 4

You should ask for a known good coin. Call the original coins A, B, C, and D and the known good coin G. The eight possibilities you must discriminate between are A− (A is the bad coin and is light), A+ (A is the bad coin and is heavy), B−, B+, C−, C+, D− and D+.