Skip to main content
OlympiadHQ

Browse · MathNet

Print

Baltic Way 2019

Baltic Way 2019 counting and probability

Problem

A palindrome is a word which is build using 2 letters and is equal to its reverse, for example: ABBA and ABABABABA are palindromes. Prove that any 2019-letter word (which uses 2 letters) is build by at most 808 palindromes.
Solution
Note that any 5-letter word may be build with at most two palindromes (case-by-case checking). Any 2019-letter word can be divided into 404 5-letter words, hence it can be divided into at most 808 palindromes.

Techniques

Coloring schemes, extremal arguments