Problème proposé par Michel Lafond

On dit qu’un mot  M  de  n  bits contient un palindrome  P  s’il existe dans  M  une suite de bits consécutifs formant un mot  P  symétrique.
Exemple :  M = (1110010)  contient les 13 palindromes  1, 1, 1, 0, 0, 1, 0, 11, 11 ,00, 111, 010, 1001.
Q₁ : Démontrer que tout mot de  n  bits contient au moins  2n – 2  palindromes.
Q₂ : Démontrer que pour tout  n ? 2 il existe un mot de n bits qui contient exactement  2n – 2  palindromes.
Q₃ : Démontrer qu’un mot aléatoire de  n  bits  [la valeur de chaque bit est tirée à Pile ou Face] contient en moyenne :    
Si  n  est pair : E = 3n - 7 + 7/2^n/2
Si  n  est impair :  E = 3n - 7 + 5/2^(n-1)/2

 Solution

Michel Lafond,Patrick Gordon et Daniel Collignon ont résolu tout ou partie du problème.