MathDB
exist at least 18^n passwords of length n

Source: P2 Francophone Math Olympiad Senior 2022

May 23, 2022
combinatorics

Problem Statement

To connect to the OFM site, Alice must choose a password. The latter must be consisting of nn characters among the following 2727 characters: A,B,C,...,Y,Z,#A, B, C, . . ., Y , Z, \# We say that a password mm is redundant if we can color in red and blue a block of consecutive letters of mm in such a way that the word formed from the red letters is identical to the word formed from blue letters. For example, the password H#ZBZJBJZH\#ZBZJBJZ is redundant, because it contains the [color=#00f]ZB[color=#f00]Z[color=#00f]J[color=#f00]BJ block, where the word ZBJZBJ appears in both blue and red. At otherwise, the ABCACBABCACB password is not redundant. Show that, for any integer n≥1n \ge 1, there exist at least 18n18^n passwords of length nn, that is to say formed of nn characters each, which are not redundant.
Back to ProblemsView on AoPS