Bonne réponse de ceux qui ont répondu "Zeckendorf".
Le titre faisait référence au binaire d'une part et à Fibonacci d'autre part. Le mécanisme est le suivant (prenons la première lettre, 21, pour l'exemple)
21 en binaire s'écrit 10101. On fait correspondre le 1er chiffre au premier nombre de la suite de Fibonacci (1), le 2ème a 2, le 3ème à 3, le 4ème à 5, le 5ème à 8, etc... et on additionne ceux pour lesquels on a un 1 en base 2
Donc 21 = 10101 en base 2 = 1 + 3 +8 = 12, la 12ème lettre de l'alphabet est un L. En appliquant la même chose aux autres lettres, on obtient
"La réponse est Zeckendorf"
Voilà. 2 petites remarques
1) Si on considère que beaucoup d'énigmes cryptées sur P2T ont une solution qui commence par "la reponse est", et que c'est peut-être le cas ici, on se rond compte que ça s'applique plutôt bien avec les chiffres en place. Dans un 2nd temps, on remarque que pour tous les chiffres et leur correspondance en lettres qu'on a trouvé, les chiffres sont dans l'ordre croissant par rapport à l'ordre alphabétique (A=1, E=8, L = 21, ...) En supposant que c'est le cas partout, on peut déduire que 9 = F par exemple (vu que E = 8) et ainsi de suite pour trouver
L A R E P O N S E E S T 72 E 4 K E N 5 O R F
72 est un lettre située après T dans l'alphabet, et 4 et 5 valent soit B et C, soit C et D, c'est déjà pas mal comme décryptage bourrin
2) Pourquoi la réponse est-elle Zeckendorf ?
Edouard Zeckendorf était un mathématicien belge, qui a démontré dans les années 70 que tout nombre entier pouvait être écrit sous la forme d'une somme de nombres de Fibonacci non consécutifs, et ce de manière unique.
La démonstration n'est pas bien complexe, elle se décompose en 2 grandes parties:
a. Démonstration de l'existence d'une décomposition d'un nombre en une somme de nombre de Fibonacci non consécutifs:
C'est clairement vrai pour 1, 2, 3 et 5 qui sont des nombres de Fibonacci. C'est tout aussi vrai pour 4 (3+1), pour 6 (5+1), ...
On va donc procéder par une récurrence forte: sachant que pour tout i inférieur ou égal à n, une telle décomposition de i existe, peut-on en trouver une pour n+1 ?
Si n+1 est un nombre de Fibonacci, alors la réponse est oui
Sinon, n+1 est compris entre 2 nombres de Fibonacci, disons le F(k) et le F(k+1)
Dans ce cas, on pose X = (n+1) - F(k).
(n+1) < F(k+1)
donc (n+1) < F(k) + F(k-1), c'est la définition de la suite de Fibonacci
donc X < F(k-1), en otant F(k) de chaque côté
donc X peut se décomposer en une somme (notée Sx) de termes qui ne contient pas F(k-1)
donc Sx + F(k) ne contient pas 2 termes consécutifs, et Sx + F(k) est une décomposition de n+1, vu que x + F(k) = n+1
b. Démonstration de l'unicité de cette décomposition:
Supposons que toute somme de nombres de Fibonacci non consécutifs et compris entre F(1) et F(n) est inférieure à F(n+1)
C'est vrai pour n=1 (F(1) = 1 < F(2) = 2)
Si c'est vrai au rang n et moins, alors pour toute somme S de nombres de Fibonacci non consécutifs et compris entre F(1) et F(n), on a deux cas
- S contient F(n) : dans ce cas, on ne peut pas y ajouter F(n+1)
- S ne contient pas F(n) : dans ce cas, on peut y ajouter F(n+1), mais comme S est une somme de termes compris entre F(1) et F(n-1), alors S < F(n)
et donc S + F(n+1) < F(n+2).
Par récurrence donc, on a montré que toute somme de nombres de Fibonacci non consécutifs et compris entre F(1) et F(n) est inférieure à F(n+1)
Ensuite, par l'absurde, supposons que la décomposition de ne soit pas unique, c'est à dire que 2 sommes différentes de termes non consécutifs donnent le même résultat.
Dans un premier temps, on enlève tous les termes communs de ces deux sommes : ça ne change pas le fait que les deux résultats sont égaux. Vu que les termes sont différents, il doit en rester au moins un dans chaque somme.
Dans un second temps, on prend le plus haut terme de chaque somme (qui sont forcément différents vu l'étape d'avant). Disons que l'un est F(i), que l'autre est F(j) et que i < j et donc F(i) < F(j): une somme de termes compris entre F(1) et F(i) est inférieure à F(i+1), lui même inférieur (ou égal) à F(j), ce qui est absurde.
CQFD
http://mathworld.wolfram.com/Zeckendorf … ation.html
Accueil
