Q6 Matemática  (Francophone Mathematical Olympiad 2022)

Para se conectar ao site OFM, Alice deve escolher uma senha. Este último deve ser composto por $n$ caracteres entre os seguintes $27$ caracteres: $$A,B,C,...,Y,Z,\#$$Dizemos que uma senha $m$ é redundante se pudermos colorir de vermelho e azul um bloco de letras consecutivas de $m$ de tal forma que a palavra formada pelas letras vermelhas seja idêntica à palavra formada por letras azuis. Por exemplo, a senha $H\#ZBZJBJZ$ é redundante, pois contém o bloco ZBZJBJ, onde a palavra $ZBJ$ aparece em azul e vermelho. Caso contrário, a senha $ABCACB$ não é redundante. Mostre que, para qualquer inteiro $n\ge 1$, existem pelo menos $18^n$ senhas de comprimento $n$, isto é, formadas de $n$ caracteres cada, que não são redundantes.