Énigme n°1, la solution

Ce résultat est très surprenant. 4 c'était facile, 5 c'est impossible.

Je ne vais pas faire tous les calculs ici, mais essayer d'expliquer au plus grand nombre comment on prouve ce résultat. N'hésitez pas à poser vos questions si vous ne comprenez pas.

Le fonctionnement de la démonstration

La preuve se fait en deux temps :

On montre que l'on peut faire 4
On montre que l'on ne peut pas faire 5

Dans ma grande mansuétude, je vous avais déjà offert la première étape, alors concentrons-nous sur la seconde.

Pour prouver le second point, nous allons donner un poids à la position initiale et ferons en sorte que chaque coup ne fasse pas augmenter le poids. Nous calculerons ce poids. Ensuite nous montrerons qu'une position avec un jeton à la distance = 5 a un poids supérieur à la position initiale. Hors comme chaque position a un poids inférieur ou égal à celle qui la précède, nous conclurons à l'impossibilité d'aller à une distance = 5.

Notations

Pour se comprendre, commençons par numéroter les cases. La colonne 0 correspond à la colonne sur laquelle on mettra je jeton le plus loin.

Numérotation des cases

Modélisation

Principe général

Il n'est pas trop difficile de se convaincre^[1] qu'un coup n'est utile que s'il permet un mouvement vers le bas ou vers la colonne n°0.

Il faut trouver une structure mathématique qui permette de quantifier l'efficacité d'un mouvement : si un mouvement est utile, alors il ne rapporte pas de point, s'il est mauvais il en fait perdre.

Le poids d'une position est la somme des poids des cases où il y a un jetons.

Exemple

La première grille représente la poids de chaque case, la seconde l'emplacement des jetons.

Exemple de poids Jetons pour l'exemple

Le poids de cette position est : 2 + 3x3 + 4 + 2x5 = 25.

Calcul des poids

Maintenant toute la force est de choisir intelligemment les poids, tout le reste n'est que calcul.

Un déplacement est une transformation de la forme :

Déplacements

Nous voulons que cette transformation ne modifie pas le nombre de points, nous souhaitons donc que poids(case rouge) + poids(case orange) = poids(case jaune).

Système de poids - 1

On construit ainsi itérativement des diagonales dont de cases de même poids. Il suffit de trouver les poids sur la colonne n°0 pour déterminer les poids sur toutes les cases.

Système de poids - 2

Fixons le début p(0) = 1.

La relation entre les poids des cases est donné par la relation p(i) = p(i+1) + p(i+2)

Cette relation fait fortement penser à la suite de Fibonacci F(i+2) = F(i+1) + F(i) avec F(0) = F(1) = 1.

Si on se rappelle de ses cours de maths de prépa ou de deug, alors on sait résoudre cette récurrence.^[2] Sinon, on la cherche sous forme d'une suite géométrique comme l'est Fibonacci.

Choisissons la suite géométrique la plus simple : p(i) = λ^i. On commence par vérifier que λ^i=λ^(i+1) + λ^(i+2). C'est vrai puisque p(0) = 1.

Il faut maintenant déterminer λ, c'est à dire que nous devons résoudre l'équation 1 = λ + λ² ce qui nous donne

λ = (-1 +/- sqrt(5) ) / 2

On choisis le signe + pour la beauté de la démonstration : λ est alors l'inverse du nombre d'or.^[3]

Calculs

Maintenant, il faut compter.^[4]

Calcul du poids de la position initiale

Quelle est le poids de la position initiale ? C'est la somme de tous les poids des rangées positives. Dans un élan de liberté, appelons S cette somme.

N'ayons peur de rien, supprimons la rangée n°0. Quelle est alors le poids des jetons restants ? Certains diront que c'est le poids précédent moins celui des jetons des la zéroième^[5] rangée. D'autres diront que λS parce que déplacer une rangée vers le haut, c'est multiplier par λ. En effet, p(i+1) = λp(i) puisque λ^(i+1) = λxλ^i.

Comme les deux ont raison : S - poids(première ligne) = λS.

Quelle est le poids de la première ligne ? Nous allons faire de même en appelant ce poids P. P = 2Q - 1 avec Q le poids des cases dont les numéros des colonnes sont positifs.

Nous allons calculer Q, nous nous intéressons donc qu'à ces jetons :

Calcul de Q

Déplaçons tous ces jetons vers la droite. C'est exactement ce que nous avons fait précédemment. Il y a deux manière de le voir : soit cela veut dire que l'on a enlevé le premier jeton, soit cela veut dire que l'on tout multiplié par λ : Q-1 = λQ donc Q = 1/(1-λ). Le poids de la première ligne est : 2/(1-λ)-1

Le poids de la position initiale est donc :

S = (1+λ)/(1-λ)²

Numériquement S = 11,09017...

Calcul du poids minimal pour aller sur la cinquième case

un jeton pour une distance 1 a un poids de 1/λ = 1,6...
un jeton pour une distance 2 a un poids de 1/λ² = 2,618...
un jeton pour une distance 3 a un poids de 1/λ^3 = 4,236...
un jeton pour une distance 4 a un poids de 1/λ^4 = 6,854...
un jeton pour une distance 5 a un poids de 1/λ^5 = 11,09017... = S

Ajout : Si vous n'êtes pas convaincus par l'égalité des valeurs numériques, sachez que Joun a donné une manière efficace de montrer cette égalité (S = 1/λ⁵) dans les commentaires.

Conclusion

On ne peut donc pas mettre de jeton sur la cinquième case, pour cela il faudrait enlever tous les jetons du demi-plan initial, ce qui est impossible.

Voilà, nous pouvons fièrement écrire CQFD ou dessiner un joli petit carré.

Notes

[1] en réalité, ce n'est pas si facile. Vous avez devant vous le meilleur outil jamais inventé pour raccourcir une preuve : l'argument d'autorité.

[2] Il manque p(1) pour pouvoir la résoudre de manière unique, nous sommes libre de fixer ce qui nous arrange.

[3] aussi connu sous le nom de phi barre caractère que je n'ai pas trouvé dans ma table UTF8, et inclure des équation LaTeχ dans le HTML, c'est moche, j'essayerais de faire du MathML la prochaine fois.

[4] Mathématiciens, vous qui savez compter, pardonnez-moi mon manque flagrant de rigueur dans la suite.

[5] liberté, quand tu nous tiens, plus rien ne résiste, surtout pas le français

Commentaires

1. Le mercredi 6 juin 2007, 22:05 par Joun

C'est une jolie solution. Deux remarques :

- Dans l'attribut alt= de la valeur de S, une parenthèse est mal placée
- Dans cette même formule, on peut avoir la réponse sans connaitre la
  valeur numérique, en remarquant que 1 + λ = (1/λ)(λ + λ²) = 1/λ
  et 1-λ = λ², d'où S = 1/λ⁵

2. Le jeudi 7 juin 2007, 01:04 par wdfx

"Il n'est pas trop difficile de se convaincre qu'un coup n'est utile que s'il permet un mouvement vers le bas ou vers la colonne n°0. (Argument d'autorité)."

Je ne pense que l'on doive le démontrer pour que la demo soit valide. Le système de poids se déduit à partir des seuls règles de déplacement. Ici, on veut montrer qu'aucune stratégie n'est payante,inutile de trouver quelle est la moins mauvaise.

3. Le jeudi 7 juin 2007, 01:50 par Celui

@Joun

(corrigé, merci bien)
Jolie remarque pour la valeur exacte de S, bien plus simple que ma méthode (que je n'ai donc pas mise parce que bien plus compliquée que la votre)

@wdfx
Vous avez tout à fait raison, l'argument d'autorité n'en est pas vraiment un. La seule chose qui est importante ici est en fait la convention que la colonne 0 est la colonne sur laquelle on mettra un jeton le plus loin.

4. Le jeudi 7 juin 2007, 10:00 par Joun

@Celui: Désolé d'insister, je ne vois pas la correction dans le billet, il faudrait remplacer alt="S = (1+lambda)/(1-lambda²)" par alt="S = (1+lambda)/(1-lambda)²".

5. Le jeudi 7 juin 2007, 10:47 par Celui

(Voilà, corrigé pour de bon)

Griffonnages