Énigme n°1
Par Celui le mardi 29 mai 2007, 18:18 - Énigmes - Lien permanent
Bon, j'avoue je n'ai pas fait que travailler aujourd'hui au labo, un collègue est venu avec cette énigme :
Considérons un plan infini de cases. On pose un jeton sur chacune des cases d'un demi-plan. La position initiale ressemble donc à cela :
(c'est infini dans toutes les directions)
Les jetons se déplacent selon la règle du solitaire. À quelle distance du demi-plan peut on poser un jeton ?
- Distance = 1, la solution est immédiate
- Distance = 2, idem
- Distance = 3, il ne faut chercher bien longtemps.
- Distance = 4, ça commence à devenir pénible, mais on y arrive sans
problème
→ 
→ 
Vous avez compris le principe j'espère.
Et comme je ne sais pas comment terminer ce billet voici un billet aux fins alternatives :
- (skyblog) Lâchez-vos coms !
- (Francis Pisani) Et vous, qu'en pensez-vous ?
- (Embruns) J'ai des commentateurs intelligents, ils vont bien trouver la réponse.
- (Jules) Indice : Ceteris paribus.
Commentaires
Bonjour,
pour le 3 y-a-t-il plusieurs solutions ?
je n'arrive pas au même résultat (o case vide et x pion) :
sinon pour le max... on m'a indiqué la réponse mais je n'ai pas compris l'explication... si jamais la semaine prochaine la solution pouvait être expliquée... ce serait cool ! ;o)
@+
@nap1128 :
Bonjour,
j'ai une solution à proposer, puis-je la poster ou préférez-vous
d'abord poster la votre ?
Allez-y, surtout ne vous en privez pas. Outre l'admiration des fans béats devant la solution, cela fera patienter mes lecteurs, et m'aidera à rédiger ma solution.
Parfait, alors ayant l'esprit mal tourné, je vais prendre le problème à l'envers :
Si en plus on autorise les pions à se superposer, la figure ci-dessus permet de facilement trouver une figure de départ qui permette d'obtenir un pion à la distance d souhaitée. En effet, il suffit d'additionner les pions qui permettent d'arriver aux distances d-1 et d-2. On obtient ainsi :
Par exemple, on peut vérifier pour d=3 :
Mais il faut encore remonter dans le temps pour arriver à la configuration initiale. Pour cela, on peut mettre un pion à gauche, un pion à droite, et s'il reste plus d'un pion sur cette case, on fait descendre les pions supplémentaires. Ainsi pour d=4, on obtient :
Si on remet maintenant le film à l'endroit, les cases marquées d'un 1 dans le damier de droite sont les pions qui vont être déplacés pour amener un pion jusqu'à une distance de 4, et ô magie on retrouve le dessin donné dans l'énoncé ;-)
Si maintenant on regarde d=5 (avec une notation en hexadécimal)
Aïe, ça y est, on a une réaction en chaîne, ça va péter ! On ne peut donc pas avoir de pion à une distance de 5 (bon d'accord, la démonstration n'est pas complète, il faudrait montrer qu'il n'existe pas de moyen plus efficace pour disperser les pions accumulés).
Si on ne peut pas obtenir de pion à une distance de 5 avec notre jeu modifié qui autorise la superposition de pions, c'est a fortiori vrai pour le jeu initial.
PS : un peu de maths sont nécessaires pour montrer que la réaction en chaîne ne peut pas s'arrêter. Si on part d'une position
on doit bouger x-3 pions vers le bas, on aboutit donc à la nouvelle position
Si on part d'une position avec x-3 >= y >= 3, on a alors
Les valeurs successives de x et y ne peuvent pas décroître.
Le résultat est juste, la démonstration un peu moins comme vous le laissez entendre : . Vous avez démontré que 4 est la distance maximale dans le cas où vous n'avez que 5 colonnes infinies de jetons. Mais l'infini est dans les deux dimensions. Je n'y ai pas réfléchis, mais il est peut-être possible d'adapter votre preuve en prenant en compte la l'idée me semblant très pertinente. Je publierai bientôt le mienne qui ne contient pas de raisonnement par l'absurde, et qui fonctionne dans le bon sens. En revanche celle-ci est mathématiquement plus lourde.