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...