Library / /41 of 68

, 2017

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Let $w = w_{1} w_{2} \ldots w_{n}$ be a word. Define a substring of $w$ to be a word of the form $w_{i} w_{i+1} \ldots w_{j-1} w_{j}$ , for some pair of positive integers $1 \leq i \leq j \leq n$ . Show that $w$ has at most $n$ distinct palindromic substrings.

For example, aaaaa has 5 distinct palindromic substrings, and abcata has 5 ( $a, b, c, t, ata$ ).

Solution

Solution:

For each palindrome substring appearing in $w$ , consider only the leftmost position in which it appears. I claim that now, no two substrings share the same right endpoint. If some two do, then you can reflect the smaller one about the center of the larger one to move the smaller one left.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.