2013 AMC 10B Problem 22

P21-25~7 minPrint

Arrangements with Restrictions Modular Arithmetic Split into exhaustive cases and handle each Set up the equation/formula and compute; no special trick needed

The regular octagon $ABCDEFGH$ has its center at $J$ . Each of the vertices and the center are to be associated with one of the digits $1$ through $9$ , with each digit used once, in such a way that the sums of the numbers on the lines $AJE$ , $BJF$ , $CJG$ , and $DJH$ are all equal. In how many ways can this be done?

Show solution without answering

Key insight

J is on every line, so the lines have equal sums exactly when the four opposite pairs have equal sums. The eight outer numbers add to 45 - J.

Solution

Every line goes through the center $J$ . So each line's sum is $J$ plus the two opposite corners on it. The four line sums are equal exactly when the four opposite pairs $\{A, E\}$ , $\{B, F\}$ , $\{C, G\}$ , $\{D, H\}$ all have the same sum. Call that pair sum $s$ .
The digits $1$ to $9$ add up to $45$ . The eight corners use every digit except $J$ , so they add up to $45 - J$ . They form four pairs, each adding to $s$ , so $4s = 45 - J$ .
That means $45 - J$ must be a multiple of $4$ . Check each $J$ :

$J$	1	2	3	4	5	6	7	8	9
$45 - J$	44	43	42	41	40	39	38	37	36

Only $44$ , $40$ and $36$ are multiples of $4$ , so $J = 1$ , $5$ or $9$ .
4. In each case, the pairs are forced. Pair the smallest remaining digit with the one that completes the sum, and repeat:
- $J = 1$ , $s = 11$ : $\{2, 9\}, \{3, 8\}, \{4, 7\}, \{5, 6\}$ .
- $J = 5$ , $s = 10$ : $\{1, 9\}, \{2, 8\}, \{3, 7\}, \{4, 6\}$ .
- $J = 9$ , $s = 9$ : $\{1, 8\}, \{2, 7\}, \{3, 6\}, \{4, 5\}$ .
5. Now place the pairs. The four pairs go on the four lines in $4 \times 3 \times 2 \times 1 = 24$ ways. On each line, either number of the pair can go at either end, which is $2$ ways per line and $2 \times 2 \times 2 \times 2 = 16$ ways for all four lines. That gives $24 \times 16 = 384$ ways for each choice of $J$ .
6. Total: $3 \times 384 = 1152$ .

The answer is $\boxed{\textbf{(C)}\ 1152}$ .

Why this works

The center is shared by every line, so it drops out when you compare the sums. That turns "four equal line sums" into "four equal pair sums", which a quick divisibility check settles. After that, counting is just arranging: which pair goes on which line, and which way round.

Concise solution

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

Each of the four lines passes through the center $J$ , so its sum is $J$ plus the sum of a pair of opposite vertices. The lines have equal sums exactly when the four opposite pairs $\{A, E\}, \{B, F\}, \{C, G\}, \{D, H\}$ all have the same pair-sum $s$ .

The eight vertex numbers are everything except $J$ , so $4s = 45 - J$ . Thus $45 - J$ must be a multiple of $4$ , which happens for $J = 1, 5, 9$ only.

$J = 1$ : $s = 11$ , pairs $\{2,9\}, \{3,8\}, \{4,7\}, \{5,6\}$ .
$J = 5$ : $s = 10$ , pairs $\{1,9\}, \{2,8\}, \{3,7\}, \{4,6\}$ .
$J = 9$ : $s = 9$ , pairs $\{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}$ .

In every case the eight remaining digits split into four pairs in exactly one way. Assign the four pairs to the four lines: $4! = 24$ ways. Within each line, decide which end gets which number: $2^4 = 16$ ways. Each case contributes $24 \cdot 16 = 384$ labelings.

Total: $3 \cdot 384 = 1152$ .

The answer is $\boxed{\textbf{(C)}\ 1152}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)
Introduction to Number Theory, Chapter 10: Units Digits