MathDB

6

Part of 2022 Czech-Austrian-Polish-Slovak Match

Problems(1)

Nice strings

Source: Czech-Polish-Slovak Match 2022 P6

9/3/2022
Consider 26 letters A,...,ZA,..., Z. A string is a finite sequence consisting of those letters. We say that a string ss is nice if it contains each of the 26 letters at least once, and each permutation of letters A,...,ZA,..., Z occurs in ss as a subsequences the same number of times. Prove that: (a) There exists a nice string. (b) Any nice string contains at least 20222022 letters.
combinatorics