NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 10/07/2013 Orientation générale  DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique
	Pavage
Débutants Géométrie	Avec des DOMINOS			Glossaire Géométrie
INDEX Géométrie Jeux	Dominos	Pavage Fibonacci	Pavage sans faute	Échiquier
		Sommaire de cette page >>> Rectangles 2 x n >>> Cas des rectangles impair-impair >>> Rectangles 3 x n >>> Combien de dominos sur une ligne? >>> Rectangles 4 x n >>> Cas des rectangles pair-pair >>> Solution minimale (5x6) >>> Bilan >>> Anglais

Pavage MINIMAL du RECTANGLE

avec des DOMINOS

Un jeu amusant au début, un problème sérieux de mathématique dans la rubrique des pavages (tilings).

Il s'agit de paver un rectangle avec des dominos, sans faire apparaître de lignes droites horizontales ou verticales coupant le rectangle en deux. C'est un pavage sans défaut ou sans faute. Un peu à la manière de la construction d'un mur sans coupure verticale qui compromettrait la solidité de ce mur.

La solution minimale: rectangle 5 x 6 >>>

Anglais: Fault-free tilings of rectangle

Approche – Rectangles en 2 x n
Rectangle 2 x 3 Premier rectangle envisageable: 2 x 3 Nécessite: 2 x 3 / 2 = 3 dominos Quelle que soit la disposition, une ligne de fracture s'installe (bleue pointillée). Rectangle 2 x 4 Là aussi impossible; il y a même deux lignes de fractures: deux verticales comme sur la figure, ou une verticale et une horizontale. Rectangle 2 x 5 Impossible. Toujours quatre dominos couchés et un debout.	Aucun de ces pavages ne répond à notre critère.

Rectangles impair-impair
Rectangle 3 x 3 Un rectangle dont longueur et largeur sont impaires est impossible à paver. En effet, son aire est le produit de deux impairs; elle est impaire. Or, une quantité exacte de dominos produira une aire paire. Ici: aire = 3 x 3 = 9 pour aire des dominos de 4 x2 = 8 ou 5 x 2 = 10. Rectangles impair-impair impossibles à paver sans défaut avec des dominos.	Le rectangle 3 x 3 est impossible à paver avec des dominos, comme tous les rectangles impair-impair.

Rectangles 3 x n
Rectangle 3 x 4 Seule solution: juxtaposition de deux fois le pavage 2 x 3 vu ci-dessus. Une ligne verticale se matérialise. Rectangle 3 x 5 Impair-impair: impossible. Rectangle 3 x 6 Nous verrons que nous devons placer quatre dominos debout, deux touchant le haut et deux touchant le bas. Les cinq autres sont couchés. En essayant toutes les dispositions, il est impossible de ne pas faire naître une ligne de coupure du rectangle en deux rectangles. Il existe toujours un carré de deux dominos (en vert) à compléter par un domino couché, créant la coupure fatidique. Aux symétries près, le pavage est unique. Une pièce placée entraîne le positionnement de toutes les autres.	Ne répondent toujours pas à notre critère de ligne sécante non-autorisée

Combien de dominos sur une ligne?
Rectangle pair-pair (ici: 4 x 4) Question: une ligne horizontale ou verticale coupe combien de dominos ? Zéro, cas des lignes bleues. Elle est à bannir pour satisfaire notre critère Un n'est pas possible, car s'il y en a un seul, les suivants sont couchés conduisant à un compte impair (1 + 2k) incompatible avec une dimension paire. Deux ou multiple de deux: c'est le cas général pour la raison qui vient d'être invoquée (quantité paire de cases). Deux théorèmes Sur une dimension paire, nous trouverons 2k dominos debout Sur une dimension impaire, nous trouverons au moins 1 domino debout.

Rectangles 4 x m
Rectangle 4 x 4 Encore impossible de le paver sans coupure horizontale ou verticale. Nous pouvons le prouvé en utilisant nos théorèmes tout frais. Sur les trois horizontales, il faut 3 x 2 = 6 dominos "debout". Sur les trois verticales, il faut 3 x 2 = 6 dominos "couchés". Soit un total de 6 debout + 6 couchés = 12 dominos. Or, nous n'avons que 4 x 4 / 2 = 8 dominos à placer. Conséquence: pavage requis impossible. Notez pour la suite que le nombre de lignes est égal à 4 – 1; un de moins que la dimension. Rectangle 4 x 5 Encore impossible selon le même raisonnement illustré ci-contre. En horizontal, pair, au moins 2 dominos debout. En vertical, impair, au moins un domino couché. Total 4 x 2 + 3 x 1 = 11 dominos minimum pour un espace de seulement 10 dominos. Rectangle 4 x 7 Aire en dominos: A = 4 x 7 / 2 = 14 Dominos nécessaires: 3 x 1 + 6 x 2 = 15 Conclusion: impossible.	Toujours impossible!

Rectangles pair x pair
Nous venons de voir que le rectangle 4 x 4 n'est pas faisable. En utilisant le même raisonnement quels sont les rectangles pair-pair (n x m = 2k x 2k') infaisables car nécessitant trop d dominos? Ce sont ceux pour lesquels la quantité de dominos minimale (D) est supérieure à l'aire du rectangle (A) exprimée en dominos. A = m.n / 2 D = 2 (2k – 1) + 2 (2k' – 1) La table ci-contre donne les valeurs calculées. Avec m = 4 et quelle que soit la valeur de n, c'est impossible. Sans doute faisable avec le rectangle 6 x 8 et la réponse sera oui. Plusieurs solutions. Sans doute faisable au-delà et la réponse est oui, avec de multiples possibilités.	Faisabilité d'un rectangle pair-pair Rectangle 6 x 8 sans faute

Solution minimale
Rectangle 5 x 6 Pas de possibilité avec impair-impair comme 3 x 3 ou 5 x 5 Pas de possibilité avec pair-pair comme 2 x 2 ou 4 x 4 ou 6 x 6 Seuls candidats: les rectangles impair-pair. Or 2 x 3 ne marche pas; Or 3 x 4 ne marche pas; Et 4 x 5 qu'en pensez? Extension du 5 x 6 en 5 x 8 Une des solutions consiste à étirer le rectangle de la solution minimale en horizontal comme indiqué par le contour en vert. En utilisant cette procédure de décalage et inter calage de dominos horizontaux, on montre que: Si le rectangle m x n est une solution, tout rectangle m x (n + 2k) est aussi une solution. Extension du 5 x 6 en 7 x 6 Voyez le principe général qui consiste à: retirer un domino horizontal en bas, ajouter tous les dominos verticaux de la zone en vert, replacer le domino retiré dans le logement libre. Si le rectangle m x n est une solution, tout rectangle (m + 2k') x n est aussi une solution.	Solution minimale: 5 x 6

Bilan

En reprenant tous les cas exposés, nous pouvons dresser le tableau suivant:

Théorème de Ron Graham

Un rectangle m x n dont l'aire > 2 est une solution du pavage par dominos sans faute si et seulement si:

m 5, n 5,

m et n non simultanément égaux à 6, et

le produit m x n est pair.

La démonstration repose sur le procédé d'extension vu ci-dessus.

Généralisation

Un rectangle p x q, pavé par un domino a x b, est une solution du pavage sans faute si et seulement si:

a comme b divise p ou q,

a comme b peuvent se mettre sous la forme xa + yb de deux manières différentes au moins (x et y étant positifs),

pour (a,b) = (1,2) alors (p, q) (6,6) – Cas des dominos classiques.

English corner
A tiling of a rectangle is a division of the rectangle into non overlapping dominoes A fault line of a tiled rectangle is a line that cuts the rectangle into two pièces without cutting any dominoes. A tiling of a rectangle is fault-free if there no fault line.

Suite	Carré et rectangle à trou Dominos Échiquier et dominos Hexagone – pavage Polygone – pavage
Voir	Carré Carrés parfaits Construction géométrique des nombres Dodécagone Géométrie – Index Hexagone – Généralités Méandres Pavage mystérieux du triangle Pentominos Poincaré Polygone Triangle équilatéral
Cette page	http://villemin.gerard.free.fr/Pavage/DominoMi.htm