Un peu de géométrie

[Trident]

Bonjour, j'espère que vous pourriez m'aider sur quelques questions concernant les pavages.

Voici un carré 8x8 en forme d'échiquier :


L'échiquier présente une particularité originale, c'est qu'il est colorié de sorte que deux cases qui se suivent seront toujours de couleur différente.
On veut savoir si on enlève un nombre de cases de l'échiquier, peut-on recouvrir la surface restante avec des dominos de taille 1x2.

Et en fait, j'aimerais montrer que : la surface obtenue en enlevant p cases de l'échiquier est recouvrable si et seulement si elle contient autant de cases noires que de cases blanches.

L'implication "==>" est facile. Un domino 1x2 où qu'il soit placé recouvre toujours 1 case noire et 1 case blanche. Donc n dominos recouvreront toujours n cases noires et n cases blanches donc recouvreront un nombre de cases noires égal au nombre de cases blanches.

Par contre, comment montrer que si il y a autant de cases noires que de cases blanches, alors forcément, on pourra recouvrir le tout avec des dominos 1x2 ?

Merci par avance si quelqu'un a une idée.

[Dlzlogic]

Bonjour,
Amusant votre problème, mais je ne suis pas sûr qu'il soit parfaitement défini.
Question 1 : les cases supprimées doivent-elles être contigües ?
Question 2 : les dominos utilisés ont-ils exactement la dimension de 2 cases ?

[wserdx]

Bonjour,
Amusant votre problème, mais je ne suis pas sûr qu'il soit parfaitement défini.
Question 1 : les cases supprimées doivent-elles être contigües ?
Question 2 : les dominos utilisés ont-ils exactement la dimension de 2 cases ?

Je pense que ce n'est pas tant les cases supprimées que les cases restantes qui doivent être contiguës : Si on ne laisse par exemple que les cases des quatre coins, c'est sûr on va avoir du mal à les recouvrir. Mais même sans cela, c'est pas sûr que ça marche.
J'ai composé l'exemple suivant de 4 cases blanches et 4 cases noires: (les X sont des cases enlevées) qui, je pense est impossible à recouvrir par des dominos 2x1.

[Doraki]

Oui c'est clair que si tu laisses des cases isolées sans aucun voisin, ça va pas être possible.

Par contre tu peux faire un empilage de dominos de manière à ce que la hauteur soit impaire sur les cases qui restent et soit paire sur les cases qui sont enlevées
(ou autrement dit, en autorisant des dominos qui se chevauchent et en travaillant modulo 2, ça va)

[Trident]

Bonjour à vous deux, merci de participer à la discussion.

Bonjour,
Amusant votre problème, mais je ne suis pas sûr qu'il soit parfaitement défini.
Question 1 : les cases supprimées doivent-elles être contigües ?
Question 2 : les dominos utilisés ont-ils exactement la dimension de 2 cases ?

Non, on peut supprimer deux cases qui ne se suivent pas. On peut enlever la case se trouvant par exemple 2ème ligne , 3ème colonne et la case se trouvant 6ème ligne, 4ème colonne.

Finalement, avec vos remarques, je crois que dans le problème, on suppose que un domino peut recouvrir deux cases qui se suivent et par "cases qui se suivent", on entend deux cases qui sont de couleur différente. Donc par exemple, la case se trouvant à la 1ère ligne et 1ère colonne se suit avec la case se trouvant à la 8ème ligne et première colonne. C'est pas très "réaliste" mais c'est comme ça que le problème a dû être posé vu sa résolution que j'ai trouvé (voir plus bas).

Je pense que ce n'est pas tant les cases supprimées que les cases restantes qui doivent être contiguës : Si on ne laisse par exemple que les cases des quatre coins, c'est sûr on va avoir du mal à les recouvrir. Mais même sans cela, c'est pas sûr que ça marche.
J'ai composé l'exemple suivant de 4 cases blanches et 4 cases noires: (les X sont des cases enlevées) qui, je pense est impossible à recouvrir par des dominos 2x1.

Donc du coup, avec ma remarque plus haut, on peut recouvrir les deux cases que j'ai marquées d'un * avec un domino (pas très réaliste en effet...).

Donc voici la solution qui montre que c'est alors toujours possible :
Elle est basée sur ce dessin :


Ça a été trouvé par un certain Paul Halmos (mathématicien) qui l'explique de cette manière là :

On parcours l'échiquier de manière cyclique comme sur la figure. Après en avoir retiré deux cases, il restera soit un chemin d'un nombre pair de cases (cas des deux cases adjacentes), soit deux chemins d'un nombre pair de cases (cas des cases non adjacentes), donc ce qui reste peut toujours être recouvert par des dominos 1x2.


Donc maintenant que le problème est définie correctement, il y a une autre question qui me pose problème,c 'est toujours basé sur le même principe.

On veut savoir si c'est possible de recouvrir un carré 9x9 privé d'une case avec des dominos 1x2. A quelles conditions sur la case supprimée est-ce possible ?
Si vous avez des idées..

[Trident]

Oula, j'ai fais une grosse confusion.
Mon problème de départ était de savoir si la surface était recouvrable en enlevant uniquement 2 CASES et non pas "p cases" (c'est un autre problème, et là, je pense qu'on ne peut pas recouvrir).
Donc du coup, je reformule ma nouvelle question.

Avec la même idée, si on supprime une case d'un carré 9x9 , peut-on recouvrir la surface restante avec des 1x2 , ou jamais ou cela dépend de la case supprimée ?

[Doraki]

Ben dans un carré 9x9 il vaut mieux faire en sorte d'avoir 4 cases de chaque couleur après en avoir enlevée une.