jeudi 1 mars 2007
Echec et Dominos
Prenez un plateau de jeu d'échec (8 cases sur 8 cases).
Prenez 32 dominos (on admet que chaque dominos prends exactement deux cases sur le plateau précédent)
Problème n°1:
Placez les 32 dominos sur le plateau.
Facile n'est ce pas ?
On enlève maintenant un domino, la case tout en haut à gauche et la case tout en bas à droite du plateau.
Problème n°2:
Placez les 31 dominos sur le plateau.
Il n'y a pas d'astuce, le problème est ce qu'il semble être. Creusez-vous bien la tête ^^
Commentaires
Je viens de me rendre compte d'une boulette dans l'énoncé :
On ne peut pas superposer les dominos (je dis ça pour les petits malins) ^^
Un domino couvre obligatoirement une case noire et une case blanche. Si tu enlèves deux cases diamétralement opposées, elles sont de la même couleur, par exemple blanches.
Donc il ne reste plus que 60 couples de cases blanche/noires + 1 couple noir/noir.
Donc on ne peut poser que 30 dominos.
En réalité, je n'ai pas la solution à ce problème, on me l'a posé en me disant
"si, si, il y a un moyen!".
Mais ton raisonnement semble juste, cela voudrait donc dire qu'il est effectivement impossible de poser nos 31 dominos...
Propose à celui qui te dit qu'il y a un moyen de raisonner sur un échiquier de taille quelconque, avec un côté pair de cases : 8x8, 6x6, 4x4 et ... 2x2
Sur un échiquier 2x2, il n'est pas très difficile de montrer qu'on ne peut placer aucun domino si on supprime les deux cases blanches. C'est même franchement évident.
Ensuite, par simple récurrence en rajoutant des cases, on peut montrer que ce n'est pas possible sur un échiquier 4x4 : on peut placer les autres dominos, mais il reste ce coeur 2x2 avec deux cases noires qu'on ne peut pas gérer. Les différentes combinaisons peuvent déplacer le coeur, voire l'éclater, mais ça ne change rien.
C'est beaucoup plus facile à traiter avec un échiquier qu'à expliquer. Ci joint juste une disposition qui permet de passer d'un échiquier 4x4 à deux cases manquantes à un échiquier 6x6 à deux cases manquantes
http://img148.imageshack.us/img148/5146/echiquier6x6rc2.jpg
Poster un commentaire
Rétroliens
URL pour faire un rétrolien vers ce message :
http://www.canalblog.com/cf/fe/tb/?bid=19944&pid=4173593
Liens vers des weblogs qui référencent ce message :