Bonjour

Pour la question initiale on peut aussi remarquer que le pavage se réalise avec deux parties symétriques .

Imod

oui, "il se trouve que "...

1) prouver que c'est la seule partition possible (dimensions des dominos)
2) que effectivement c'est la seule façon de les disposer (à symétrie près)

Bonjour,

pour le rectangle 7x8 je trouve une unique solution avec 6 dominos (cette solution a un centre de symétrie).

Pour ce même rectangle je trouve une unique solution avec 5 dominos et aucune avec moins de 5.

Pour la dernière question je n'ai pas encore trouvé (c'est plus long !)

Pour la démonstration je cherche d'abord les différentes façons d'écrire 28 comme une somme de 6 carrés (resp 5 carrés) puis pour chaque façon je cherche à placer les pièces.

Le pavage en dominos différents rappelle celui en rectangles semblables que j'avais proposé il y a quelques temps . Je garde le problème en mémoire même si j'ai beaucoup trop d'occupations annexes en ce moment

Imod

Bonjour,
Je réponds à la seconde question (moins de 6 dominos), avec 5 dominos dont 3 de dimension 12 :

 Cliquez pour afficher

Des réponses ont été données pendant que je réalisais la figure

je me doutais bien que le problème de base ne résisterait pas longtemps.

quoique ....
il n'est pas imposé que les côtés soient entiers

salut

le plus petit pavé ne serait-il pas :

constitué de deux dominos ?

désolé !! le total n'est pas un domino !!

Le problème du domino pavé avec des dominos distincts n'est pas simple du tout . Je pense qu'il faut prendre le problème à l'envers c'est-à-dire chercher quels sont les rapports des côtés des rectangles que l'on peut obtenir avec 1 , 2 , 3  , … dominos  . La disposition des pièces impose le rapport , il n'est donc pas utile de chercher à faire varier les tailles des dominos que l'on peut supposer entières . Par exemple avec 2 dominos on obtient un seul rapport : 5/2 , avec 3 dominos deux possibilités 13/10 et 12/5 … Il faut ensuite utiliser ces différents rectangles pour essayer de construire un domino .

Ce qui n'est pas simple

Imod

c'est ardu ... (à cause de l'explosion exponentielle des agencements possibles)

un indice : il paraîtrait (je n'ai pas retrouvé mes sources) qu'il faille au moins 8 rectangles.

La nuit porte conseil

En fait l'arborescence n'est pas si compliquée . En partant d'un rectangle formé de deux dominos distincts , il y a à chaque étape deux façons de compléter la figure en prolongeant alternativement un côté ou l'autre . C'est à dire que (a,b) va donner (a,b+a/2) ou (a,b+2a)  et ensuite (a+b/2,b) ou (a+2b,b) . Il n'y a plus qu'à lister les possibilités en partant de (a,b)=(1,2) et s'arrêter dès que  le rapport a/b est égal à 1/2 ou 2 .

Imod

sauf que .... à une étape intermédiaire rien n'interdit que le domino ajouté "dépasse" ou soit plus petit, ce qui ne donne pas un rectangle.
et ce d'ailleurs même dès le second domino (les deux premiers dominos ne forment pas obligatoirement un rectangle)

dans la solution connue (trouvée jadis sur internet, mais je n'en ai pas retrouvé la source) :

J'avais repensé à la chose dans la journée et j'avais bien vu qu'il manquait pas mal de branches à mon arbre

Principalement , on peut ajouter un domino à la suite du précédent si cela n'a pas déjà été fait . Une question importante tout de même et c'est peut-être celle que tu poses : le rectangle final s'obtient-il nécessairement par l'ajout d'un domino à un rectangle préexistant ?

Ce problème est très stimulant

Imod

la solution que j'ai est comme montré ci dessus : un des dominos occupe toute la largeur de l'ensemble.
mais aucune idée s'il y en a d'autres pour lesquelles ce ne serait pas le cas.

comme j'ai dit qu'il y en avait 8, et qu'ils sont tous différents et que le plus petit domino entier possible est le 1x2 (utilisé ou pas ??) ...

L'idée que j'avais en tête ( vraiment pénible à la main ) :

On part de deux dominos distincts formant un rectangle dont la forme est clairement 5X2 . Il y a deux ou trois façons d'ajouter un  domino pour construire un nouveau rectangle en ajoutant un domino sur l'un des côtés . On peut réitérer la manœuvre jusqu'à  obtenir le bon rapport .

C'est clairement un travail de robot mais la solution minimale est-elle forcément obtenue par ce procédé ?

Imod

j'ai répondu par la négative dans mon message d'avant.
"pour construire un nouveau rectangle " élimine trop de possibilités, dont le minimum.

Je ne suis pas sûr que nous parlions de la même chose . Il me semble qu'un rectangle fabriqué avec des dominos est toujours construit à partir d'un unique domino et que le rectangle final ne peut être obtenu qu'en ajoutant un domino à un rectangle déjà construit  . En me basant sur ce modèle j'ai vérifié ( à la main ) qu'il n'y avait pas de solution avec 7 dominos .  Je vais voir avec 8

Imod

ce que je dis est que ta méthode construisant des rectangles successifs ne prend pas en compte des départs du genre



et pourtant un tel départ est nécessaire pour obtenir des solutions optimales (voire même peut être bien des solutions tout court)

_{(ce départ est un indice)}

Je l'ai

En plus la solution est très simple uniquement avec des entiers et le plus grand domino a tout simplement une largeur égale à 10 . J'ai tout de même vérifié la construction que j'avais en tête en ajoutant progressivement des dominos sur la longueur ou la largeur d'un rectangle déjà construit mais on ne peut pas en 8 dominos . Pour plus de 8 dominos je n'ai pas vérifié

C'est un bel exercice

Imod