2009 AMC 10B Problem 11

P11-15~2 minPrint

Basic Counting Bases & Digits Map the objects to something easier to count

How many $7$ -digit palindromes (numbers that read the same backward as forward) can be formed using the digits $2$ , $2$ , $3$ , $3$ , $5$ , $5$ , $5$ ?

Show solution without answering

Key insight

The middle digit has no partner, so it must be the 5 that appears an odd number of times. The first three digits are 2, 3, 5 in any order.

Solution

A palindrome is decided by its first half and its middle, so count those.

A $7$ -digit palindrome looks like $a\,b\,c\,d\,c\,b\,a$ . Digits $1$ and $7$ match, $2$ and $6$ match, $3$ and $5$ match. Only the middle digit $d$ has no partner.
So every digit except the middle one is used in matching pairs. That means each digit is used an even number of times, except the middle digit.
We have two $2$ 's, two $3$ 's, and three $5$ 's. Only $5$ appears an odd number of times, so the middle digit must be $5$ .
That leaves $2, 2, 3, 3, 5, 5$ to split into three matching pairs: one pair of $2$ 's, one pair of $3$ 's, one pair of $5$ 's. So the first three digits $a, b, c$ are $2$ , $3$ and $5$ in some order.
The number of orders of three different digits is $3 \times 2 \times 1 = 6$ . For example $235\,5\,532$ and $523\,5\,325$ .
Each order gives exactly one palindrome.

The answer is $\boxed{\textbf{(A)}\ 6}$ .

Why this works

Once you know the first half and the middle digit of a palindrome, the rest is forced. So count the first halves, not the whole numbers. The digit that appears an odd number of times has to sit in the middle, since every other position has a partner.

Concise solution

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

A $7$ -digit palindrome has the form $abcdcba$ : the last three digits mirror the first three, and the fourth digit $d$ stands alone.

Every digit other than $d$ is used an even number of times, so $d$ must be the digit with odd multiplicity. Among $2, 2, 3, 3, 5, 5, 5$ that is $5$ , so $d = 5$ . Removing one $5$ leaves $2, 2, 3, 3, 5, 5$ , which must split as a first half $abc$ and its mirror, so $\{a, b, c\} = \{2, 3, 5\}$ with each used once.

The first three digits are therefore a permutation of $2, 3, 5$ : there are $3! = 6$ of them, and each produces exactly one palindrome.

The answer is $\boxed{\textbf{(A)}\ 6}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Number Theory, Chapter 8: Base Numbers
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques