Pavage d'une grille 8 x 8 par des dominos

[Nemo22]

Bonsoir à tous!

J'ai un problème à résoudre:

Nous disposons d'une grille 8 x 8 et nous devons la recouvrir de 32 dominos. je dois montrer que quelle que soit la façon de couvrir cette grille, nous trouverons toujours deux dominos qui forment un carré 2 x 2.

Jusque là, je n'ai aucune piste alors n'importe quelle idée qui me permettrait de démontrer ça me sera utile.

Merci beaucoup

[anthony_unac]

Bonsoir,
Qu'entendez vous par "deux dominos qui forment un carré 2 x 2" ?

[samoufar]

Bonsoir,

Les dominos font une taille 1x2.

Par conséquent un carré de taille 2x2 signifie
- Ou bien deux dominos posés comme ça : ▭ l'un sur l'autre
- Ou bien deux dominos posés comme ça : ▯ l'un à côté de l'autre

[nodgim]

Réfléchis en posant le dernier domino.

[chan79]

salut
Si on commence en haut à gauche, pas le choix pour remplir en diagonale et on est coincé en bas à droite, quelle que soit la taille du carré

[nodgim]

Aussi.
Je donne ma méthode, sans construction: le trou pour le dernier domino a au moins un grand coté commun avec des dominos ( c'est à dire un coté intérieur). Si ce grand coté est contigu à 2 dominos, c'est que ces 2 dominos forment un carré. En revanche, si ce grand coté est contigu à un seul domino, c'est avec celui ci et le dernier domino posé qu'on formera un carré.
Cette logique permet de dire que, quelle que soit la taille du damier, rectangulaire ou carré, si on peut le remplir avec des dominos, alors il y aura toujours au moins un carré 2*2 rempli par 2 dominos.

[beagle]

" Si ce grand coté est contigu à 2 dominos, c'est que ces 2 dominos forment un carré"
Pourquoi ne serait-il pas adjacent à un vertical et un horizontal?

Perso j'avais fait comme Chan79 impossible de descendre une diago.
D'où mon idée ultérieure, necessité de mettre un carré au centre si on veut un seul carré et pas plus.
Cela marche on peut avec ce carré central.
Peut-on faire 1 seul carré qui serait placé autrement?

[nodgim]

Oui, bonne remarque Beagle.

En réalité, quand on pose 2 dominos voisins qui ne forment pas un carré, on laisse un vide formé par une largeur de domino et une longueur de domino. On est obligé de remplir la moitié de ce vide seulement si on ne veut pas faire un carré, mais on recrée un nouveau vide identique avec un domino en longueur et un domino en largeur.
Moralité : tout damier rectangulaire qu'on peut remplir entièrement de dominos contient obligatoirement au moins une paire de dominos en carré.

[beagle]

Mais continuons le combat!
Ce n'est pas si facile que cela de faire peu de carrés.
si on reprend l'exemple de chan79, en fin de diago vers le bas à droite on dit OK j'y mets un carré,
bah le problème c'est que tu ne peux pas remplir les deux zones restantes, même en acceptant des carrrés tu te retrouves coincé à mettre des verticaux zone de gauche et des horizontaux zone de droite, et tu restes avec des trous.
Donc pour le moment j'ai une structure avec le carré au centre, un seul carré.
Et j'ai une structure où le carré central est mis au centre des 4 carrés de 4x4, ce qui donne 4 carrés.

Z'avez-vous des structures à 2 carrés, 3 carrés ,...?

[nodgim]

Non, et je doute qu'on puisse en faire. Mais la preuve....

[beagle]

Non, et je doute qu'on puisse en faire. Mais la preuve....

toujours pas mieux.
Une autre structure à 4 carrés, toujours ces fameuses diagonales:
2 :carrés sup d'une diago , 2 : carrés centraux de la diago opposée ...

[Nemo22]

Merci à tous! Le but est de prouver qu'il y a au moins un carré quelle que soit la facon de paver la grille. Pensez-vous qu'une récurrence puisse generaliser pour n'importe quel carré de dimension n*n?
Merci!

[beagle]

euh il avait l'air bien chan79 ton 3 carrés.
Pour du 3 carrés:
méthode 1 tricher prendre le 1 carré qs au centre et le dégrader en mettre deux ailleurs
méthode 2: ressemblant à chan79, une enceinte qs et c'est le 6x6 que l'on pose les 3 carrés

et j'ai pas le temps d'en essayer dommage a plus tard.

[beagle]

d'après maitre chan79:"Si on commence en haut à gauche, pas le choix pour remplir en diagonale et on est coincé en bas à droite, quelle que soit la taille du carré"

"quelle que soit la taille du carré"

[chan79]

d'après maitre chan79:"Si on commence en haut à gauche, pas le choix pour remplir en diagonale et on est coincé en bas à droite, quelle que soit la taille du carré"

"quelle que soit la taille du carré"

tu as du citer celui-là, beagle

[beagle]

euh non, donc ça c'est le 2.
Tu avais du 3 que tu as effacé, l'était pas bon?

[beagle]

zut ça c'est du 2 qui fait 3 , c'est ça?

[chan79]

oui, trois carrés dont deux se chevauchent

celui que j'ai effacé n'était pas bon (4 dont deux se chevauchent: je le remets:

[beagle]

Toujours extraordinaire cette symétrie dans les solutions!
(je parle du 2 qui est 3)

[beagle]

"Merci à tous! Le but est de prouver qu'il y a au moins un carré quelle que soit la facon de paver la grille. Pensez-vous qu'une récurrence puisse generaliser pour n'importe quel carré de dimension n*n?
Merci!"

j'ai hier répondu oui sur le dessin et les commentaires de chan79.
maintenant mettre des dominos de 2 x1 dans les carrés d'ordre impair, hum,hum ...
Va falloir les comprimés les carrés de 2x2 pour que ça rentre!