Library / Harvard-MIT Mathematics Tournament /206 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:
An $n$ -string is a string of digits formed by writing the numbers $1, 2, \ldots, n$ in some order (in base ten). For example, one possible 10-string is
35728910461
What is the smallest $n > 1$ such that there exists a palindromic $n$ -string?

Solution

Solution:
The following is such a string for $n=19$ :
$9|18|7|16|5|14|3|12|1|10|11|2|13|4|15|6|17|8|19$
where the vertical bars indicate breaks between the numbers. On the other hand, to see that $n=19$ is the minimum, notice that only one digit can occur an odd number of times in a palindromic $n$ -string (namely the center digit). If $n \leq 9$ , then (say) the digits $1, 2$ each appear once in any $n$ -string, so we cannot have a palindrome. If $10 \leq n \leq 18$ , then $0, 9$ each appear once, and we again cannot have a palindrome. So $19$ is the smallest possible $n$ .

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.