Library / /6 of 11

, 2022

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Hong Kong

A 'palindrome' is a positive integer which reads the same from left to right as from right to left, such as $12321$ and $259952$ . Someone wrote down a five-digit palindrome $m$ and then removed a digit of $m$ to obtain a four-digit positive integer $n$ (that does not start with $0$ ). How many possible values of $n$ are there?

Solution

Answer: $2358$

Note that $m$ is of the form $ABCBA$ with $A$ nonzero, so $n$ is of the form $BCBA$ , $ACBA$ , $ABBA$ , $ABCA$ or $ABCB$ . The second, third and fourth cases can be combined, so we are down to three types of possible values of $n$ :

* Type I — Equal thousands digit and tens digit, with nonzero unit digit;

* Type II — Equal thousands digit and unit digit;

* Type III — Equal hundreds digit and unit digit.

There are $9 \times 10 \times 9 = 810$ possibilities of Type I (9 choices for the common thousands and tens digit, 10 choices for the hundreds digit and 9 choices for the unit digit), and similarly $9 \times 10 \times 10 = 900$ possibilities for each of Type II and Type III. However,

* 90 numbers are of both Types I and II (those of the form $XYXX$ with $X$ nonzero);

* 81 numbers are of both Types I and III (those of the form $XYXY$ with both $X$ and $Y$ nonzero);

* 90 numbers are of both Types II and III (those of the form $XXYX$ with $X$ nonzero);

* 9 numbers are of all three types ( $1111$ , $2222$ , ..., $9999$ ).

By the inclusion-exclusion principle, the answer is $810+900+900-90-81-90+9 = 2358$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.