Le carré empoisonné

[ffpower]

:++:
Maintenant on peut negocier sur la notion de "compliqué".Car c est sur qu on pense p-e pas de suite a reflechir en ce sens,mais au final,c est une "3 lines proof" ^^

[Imod]

Nos amis américains appellent quickies ces petits problèmes à solution très courte et astucieuse : à déguster sans modération .

Imod

[nodgim]

Petite analyse du problème:
Une combinaison est gagnante quand le joueur peut ôter un rectangle tel que le résultat sera une combinaison perdante (pour l'adversaire). Inversement, une combinaison est perdante quand aucun rectangle ôté ne mène à une combinaison perdante, c'est à dire que n'importe quelle action mène à une combinaison gagnante (pour l'adversaire).
Comment trouver les combinaisons perdantes ?
Partir de 1, ajouter des carrés (1*1) et analyser.
On peut numériser les combinaisons en comptant par exemple le nombre de carrés dans chaque colonne, en partant du dernier carré.
Exemple: 421 est la combinaison avec 4 carrés dans la 1ère colonne, 2 dans la seconde et 1 dans la 3ème.

Liste des combinaisons perdantes pour un rectangle initial de 3*9:
1, 21, 32(221), 43, 54, 65, 76, 87, 98, 311, 422, 532, 553, 633, 642, 743, 752, 775, 844, 862, 954, 965, 972, 996.

En jouant sur le site indiqué par ffpower, on se rend compte que la machine joue bien ces codes pour gagner. Apparemment, le règlage du tableau à 9*3 ne marche pas, sinon j'aurais pu vérifier que je pouvais battre la machine à tous les coups.
Qui veut gagner peut chercher les codes pour un rectangle 10*6, c'est un peu long mais on peut le trouver.
Je n'ai pas trouvé un algorithme permettant de déduire les nombres perdants, puisque c'est un peu la même chose que la recherche des nombres premiers.

Pour vérifier qu'un rectangle de départ est toujours gagnant, il faut montrer qu'il existe toujours un nombre perdant de la forme aaaa...bbb.., c'est à dire avec seulement 2 nombres. Ce que je n'ai pas su faire.

[nodgim]

Bon, je crois avoir trouvé.
Soit E, le rectangle complet. E', le rectangle moins le premier carré en haut à droite, selon le petit dessin d'Imod.
Si E' est perdant, on joue E' depuis E et on gagne.
Si E' est gagnant, il existe E'' perdant accessible en une seule fois depuis E'. Or E'' est aussi accesssible depuis E. Donc E est gagnant.

Voilà, pas plus compliqué que cela! :id:

[Imod]

Bon, je crois avoir trouvé.
Soit E, le rectangle complet. E', le rectangle moins le premier carré en haut à droite, selon le petit dessin d'Imod.
Si E' est perdant, on joue E' depuis E et on gagne.
Si E' est gagnant, il existe E'' perdant accessible en une seule fois depuis E'. Or E'' est aussi accesssible depuis E. Donc E est gagnant.

Voilà, pas plus compliqué que cela! :id:

N'est-ce pas ce que j'ai dit dans le message #20 :we:

Imod

[nodgim]

Oh, en effet,j'ai dû en rater la lecture, ou je n'ai pas compris au moment où j'ai lu. :marteau:
Bon, pas grave, je suis tout de même content d'avoir trouvé, même avec beaucoup de retard. Il fallait que je suive mon propre chemin.