Problem

Source: 2021 Czech and Slovak Olympiad III A p5

Tags: combinatorics



We call a string of characters neat when it has an even length and its first half is identical to the other half (eg. abab). We call a string nice if it can be split on several neat strings (e.g. abcabcdedef to abcabc, dede, and ff). By string reduction we call an operation in which we wipe two identical adjacent characters from the string (e.g. the string abbac can be reduced to aac and further to c). Prove any string containing each of its characters in even numbers can be obtained by a series of reductions from a suitable nice string. (Martin Melicher)