2013 AMC 10A Problem 21

P21-25~7 minPrint

Divisibility & Factors Primes Sequences & Series Set up the equation/formula and compute; no special trick needed Start from the end state / desired conclusion and reverse

A group of $12$ pirates agree to divide a treasure chest of gold coins among themselves as follows. The $k^{\text{th}}$ pirate to take a share takes $\frac{k}{12}$ of the coins that remain in the chest. The number of coins initially in the chest is the smallest number for which this arrangement will allow each pirate to receive a positive whole number of coins. How many coins does the $12^{\text{th}}$ pirate receive?

Show solution without answering

Key insight

Work backwards: each step multiplies by 12 and divides by 1 to 11. Twelves supply every 2 and 3, so the last share needs 5, 5, 7, 11.

Solution

Going forward, the pile keeps shrinking by awkward fractions. Going backwards from the last pirate is easier.

What each pirate leaves. Pirate $k$ takes $\tfrac{k}{12}$ of the pile, so he leaves $\tfrac{12 - k}{12}$ of it. Pirate $1$ leaves $\tfrac{11}{12}$ , pirate $2$ leaves $\tfrac{10}{12}$ , and so on, down to pirate $11$ , who leaves $\tfrac{1}{12}$ . Pirate $12$ takes $\tfrac{12}{12}$ , which is everything left.
Call the last share $F$ . Pirate $12$ gets the whole final pile, $F$ coins.
Step backwards. Pirate $11$ left $\tfrac{1}{12}$ of his pile, so his pile was $12$ times as big: $F \times \tfrac{12}{1}$ . Pirate $10$ left $\tfrac{2}{12}$ , so his pile was that times $\tfrac{12}{2}$ . Keep going:

Pile just before pirate	Number of coins
12	$F$
11	$F \times \frac{12}{1}$
10	$F \times \frac{12}{1} \times \frac{12}{2}$
9	$F \times \frac{12}{1} \times \frac{12}{2} \times \frac{12}{3}$
$\vdots$	$\vdots$
1	$F \times \frac{12}{1} \times \frac{12}{2} \times \cdots \times \frac{12}{11}$

4. What must be true. Every pile must be a whole number. (Then each pirate's share, the pile before him minus the pile after, is whole too.) The starting pile grows when $F$ grows, so the smallest start means the smallest $F$ .
5. The 2s and 3s take care of themselves. Each $12 = 2 \times 2 \times 3$ brings two 2s and one 3. The numbers we divide by bring fewer. For example, $1 \times 2 \times \cdots \times 11$ contains only eight 2s and four 3s, while eleven 12s bring twenty-two 2s and eleven 3s. The same holds at every row of the table.
6. The other primes do not. We also divide by $5$ , $7$ , $10 = 2 \times 5$ and $11$ . Twelves never contain $5$ , $7$ or $11$ , so $F$ itself must supply them: two 5s (one for $5$ , one for $10$ ), one $7$ and one $11$ . So $F$ is a multiple of
$5 \times 5 \times 7 \times 11 = 1925.$
7. 1925 works. With $F = 1925$ every factor in the table cancels, so every pile is a whole number.

The twelfth pirate receives $\boxed{\textbf{(D)}\ 1925}$ coins.

Why this works

When the rule is "take a fraction of what is left", work with what is left, not with what is taken. Walking backwards turns each step into "multiply by 12, divide by a small number." Then the whole question is which prime factors the 12s cannot supply: here $5, 5, 7$ and $11$ .

Alternative approach

Use the answer choices. The last share is what is left of $1 \times 2 \times \cdots \times 11$ after all its 2s and 3s are cancelled by twelves, so it cannot be even or a multiple of $3$ . Choices (A) $720$ , (B) $1296$ , (C) $1728$ and (E) $3850$ are all even. Only (D) $1925$ is left.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Let $N$ be the initial number of coins. When pirate $k$ takes $\frac{k}{12}$ of the pile, the pile shrinks to $\frac{12-k}{12}$ of its size. After pirates $1$ through $11$ have gone, the chest holds
$N \cdot \frac{11}{12} \cdot \frac{10}{12} \cdots \frac{1}{12} = \frac{N \cdot 11!}{12^{11}},$
and pirate $12$ takes $\frac{12}{12}$ of this, i.e. all of it.

Every pirate's share is a whole number exactly when the pile is a whole number after each step; the tightest requirement is the final one, that $\frac{N \cdot 11!}{12^{11}}$ be an integer (the earlier piles are this quantity multiplied back by fractions with smaller denominators, and one checks they stay integral for the $N$ found below).

Factor: $12^{11} = 2^{22} \cdot 3^{11}$ and $11! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7 \cdot 11$ . So $N$ must supply $2^{22-8} \cdot 3^{11-4} = 2^{14} \cdot 3^{7}$ , and the smallest choice is $N = 2^{14} \cdot 3^7$ .

Then the twelfth pirate receives
$\frac{2^{14} \cdot 3^7 \cdot 11!}{2^{22} \cdot 3^{11}} = \frac{11!}{2^8 \cdot 3^4} = 5^2 \cdot 7 \cdot 11 = 1925.$

The answer is $\boxed{\textbf{(D)}\ 1925}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.4)