Pavage dominos

[invite35452583]

Trois petites jeux énigmatico-mathématiques :
a) peux-t-on paver avec des dominos 2x1 un damier nxn dont a enlevé deux coins opposés ? (facile et classique c'est pour l'échauffement)
b) quelle(s) condition(s) faut-il pour pouvoir paver avec des dominos 2x1 un damier dont on a retiré une case ?
c) quelle(s) condition(s) faut-il pour pouvoir paver avec des dominos 3x1 un damier 8x8 dont on a retiré une case ? Ou peut-être est-ce impossible.
d) Peut-on paver avec des dominos du type :
x
xx
un damier 1024x1024 dont on a retiré une case ?

Je ne serais pas là de la soirée (retour demain) mais les spécialistes de ce genre de jeu sur le forum pourront me suppléer sans peine au besoin.
-----

[invité576543]

Spoiler (?) pour b) et c)

b) quelle(s) condition(s) faut-il pour pouvoir paver avec des dominos 2x1 un damier dont on a retiré une case ?

n impair. Position de la case manquante à somme des coordonnées paire.

Démo simple, tout rectangle n x m avec un côté pair est pavable. Et on peut dessiner 4 rectangles (dont certains éventuellement nuls) en tournant autour de la case manquante. Et si la somme des coordonnées est paire, l'un des deux côté de chaque rectangle est nécessairement pair et l'autre impair.

Si somme impaire, je peux étendre au damier (n+1, n+1). On peut remplir le bord ainsi ajouté moins une case (2n+1 est impair), et la case manquante est de somme de coordonnées impaire... L'égalité du nombre de cases somme pair et somme impaire introduit une contradiction.

c) quelle(s) condition(s) faut-il pour pouvoir paver avec des dominos 3x1 un damier 8x8 dont on a retiré une case ? Ou peut-être est-ce impossible.

On procède modulo 3 pour la somme. Un domino 3x1 couvre chacune des trois valeurs.

Dans le carré 8x8, avec des coordonnées en 0..7, on a une case x+y=1 modulo 3 de trop. Faudrait donc enlever une telle case. Mais si on fait le changement de coordonnée (x, y) --> (x, 7-y), x-y=0 , soit x=y=2 modulo 3.

A une rotation près, il n'y a qu'une case possible. Et il facile de trouver un pavage: on enlève 3 lignes 3 colonnes au bords opposés, on se retrouve avec un carré 5x5, la case centrale manquante, on fait 4 rectangles 3x2 n tournant autour...

d) Peut-on paver avec des dominos du type :
x
xx
un damier 1024x1024 dont on a retiré une case ?

Je sèche...

Cordialement,

[shokin]

Une tite piste :

Un damier n*n dont on a retiré une case, c'est donc un damier à (n+1)(n-1) cases.



Shokin

[invité576543]

c) quelle(s) condition(s) faut-il pour pouvoir paver avec des dominos 3x1 un damier 8x8 dont on a retiré une case ? Ou peut-être est-ce impossible.
d) Peut-on paver avec des dominos du type :
x
xx
un damier 1024x1024 dont on a retiré une case ?

Je ne sèche plus.

On enlève un carré 4x4 au coin, et on découpe le reste en un carré 1020x1020 et deux rectangles 1020 x 4. Comme 1020 est un multiple de 3 et l'autre nombre un multiple de 2, on peut paver par des rectangles 3x2.

Reste un carré 4x4 et c'est facile de le paver sauf une case quelconque.

Maintenant si la question est en prenant une case quelconque de l'échiquier 1024x1024... On choisit un carré 4x4 contenant la case manquante tel que il reste un multiple de 3 de chaque côté dans les 2 directions (c'est toujours possible, on a 4 choix pour 3 valeurs). Et on organise en deux bandes latérales (3n x 1024) et 2 rectangles (4 x 3n)...



Cordialement,

[A voir en vidéo sur Futura]

[_Goel_]

Salut !

Pour la réponse d, je vais vous donner une solution perso...

1024x1024 = 1048576
1+4+8+5+7+6 = 31
3+1=4
4 différent de 3
donc 1048576 n'est pas divisible par 3
donc, comme une somme de n dominos de 3 cases pavant un échiquier recouvre 3xn cases... Il est impossible de recouvrir l'échiquier avec des dominos en L !

Où est mon erreur ?

[invité576543]

Où est mon erreur ?

"dont on a retiré une case"

Cordialement,

[_Goel_]

Oups...
on va faire comme si j'avais rien posté ok !?

[_Goel_]

Je suis sûr qu'il y a un truc !

[invite35452583]

Bonsoir,
finalement avant demain.
à mmy
Le cas 3) rien à redire (à part qu'en décalant on reste avec des multiples)
Le cas 2) peut être simplifié dans la dernière partie (cf résolution classique du cas 1)
Le cas 4) connaît une réponse plus simple mais encore bravo d'avoir trouvé celle-là.
Je laisse encore un peu de temps (en particulier pour la 4)

Et, pendant que c'est chaud
5) on retire deux cases d'un damier 8x8, à quelle condition peut-on remplir par des dominos 2x1 ?

+question subsidiaire pour Shokin :
dans le pire des cas en combien de pièces connexes faut-il découper un carré de n² cases dont on a retiré une case pour reconstituer un rectangle de n²-1 cases (un côté étant de longueur n+1, l'autre de longueur n-1) ? (je ne donnerai pas forcément la réponse )

[invite35452583]

Je suis sûr qu'il y a un truc !

Oui comme pour la magie mais faut le trouver.

[shokin]

+question subsidiaire pour Shokin :
dans le pire des cas en combien de pièces connexes faut-il découper un carré de n² cases dont on a retiré une case pour reconstituer un rectangle de n²-1 cases (un côté étant de longueur n+1, l'autre de longueur n-1) ? (je ne donnerai pas forcément la réponse )

En 4 pièces, non ?

Shokin

[shokin]

Et, pendant que c'est chaud
5) on retire deux cases d'un damier 8x8, à quelle condition peut-on remplir par des dominos 2x1 ?

Que ces deux cases soient de couleurs opposées (après plusieurs essais).

Je dirais que cette condition est requise pour tout rectangle dont les côtés sont pairs et dont on enlève deux cases.

Au fond, il y a peut-être une démonstration toute simple : deux cases qui forment un domino sont forcément de couleurs opposées. Donc ces deux cases que l'on enlève doivent aussi l'être.

Reste à démontrer que cette condition est suffisante :

Si ces deux cases forment un domino, et sont donc de couleurs opposées, on a simplement enlevé un domino du damier. Considérons alors deux cases reliées par un seul coin, et donc de même couleur. Toutes deux sont inscrites dans un carré 2*2, dont deux placement de deux dominos sont possibles. Donc pour passer, d'une case otée à une autre case otée qui lui est reliée par un coin, il suffit de changer la disposition du domino dans ce carré. Alors à partir de deux cases opposées (notamment formant un domino), on peut obtenir toutes les paires de deux cases de couleurs opposées. NB : démonstration tentée su'l pouce et peut-être boîteuse.

Shokin

[invité576543]

5) on retire deux cases d'un damier 8x8, à quelle condition peut-on remplir par des dominos 2x1 ?

Comme dit Shokin, suffit qu'elles soient de somme de parité distincte.

Mais la démo de Shokin ne me convient pas.

En voilà une autre.

On forme le rectangle dont les deux cases sont les coins opposés. Ce rectangle a, de par la condition imposée, un côté pair et un côté impair. Facile à remplir en bouchant les bandes latérales dans la direction impaire.

Le côté pair coupe l'échiquier en trois bandes; sa bande est de largeur paire, pas de problème, les deux autres bandes sont de longueur 8, donc paire, pas de problème.

Cordialement,

[shokin]

Il est vrai que ta démonstration est plus simple, claire et directe que la mienne, boîteuse et dont j'étais à peine convaincu.

Que sera le 6) ?

Shokin

[invité576543]

dans le pire des cas en combien de pièces connexes faut-il découper un carré de n² cases dont on a retiré une case pour reconstituer un rectangle de n²-1 cases (un côté étant de longueur n+1, l'autre de longueur n-1) ? (je ne donnerai pas forcément la réponse )

En 4 c'est facile, suffit de couper en bandes par la case manquante, les deux bandes de par et d'autre une fois accolées forment un rectangle n x n-1, et le deux rectangles de par et d'autre de la case une fois mis bout à bout forment un rectangle 1 x n-1.

Je pense que la réponse est deux, en utilisant un découpage avec des escaliers à 45°...

Cordialement,

[invité576543]

En trois, c'est sûr. Suffit de couper un coin 1x1, le mettre à la place de la case manquante, et de couper en diagonale par un escalier à 45°.

En deux, je ne trouve pas...

Cordialement,

[invite35452583]

Donc bravo à shokin (qui aura donné la réponse à un problème dont je n'ai réfléchi qu'à l'énoncé, je pensais que c'était plus dur ) et pour le 5)
bravo encore à mmy pour la démo de la question subsidiaire et une simplification de la 5) bravo de continuer à proposer des défis (découpage à 45°)
Pour la 1), la 2) et la 5) on noircit une case sur deux et ç donne facilement des impossibilités (un domino recouvre une case blanche et une case noire)
1) nombre de cases noires-nombre de cases blanches=+/-2 si n pair (si n impair il n'y a pas un nombre pair de cases ça va être dur)
2) avant retrait il y a excés d'une case d'une couleur (celle des coins) pour n impair (il faut bien que le nombre de cases restantes soient paires)
5) avant retrait même nombre de cases noires que blanches =>il faut retirer deux cases de couleurs différentes.
Généralisons ce dernier cas en donnant une autre preuve :
rectangle dont les côtés ont un nombre impair de cases : il restera un nombre impair de cases.
sinon un côté pair, il y a un nombre identique avant retrait de cases noires et blanches=>il faut retirer deux cases de couleurs distinctes
Et cela suffit comme condition :
traçons avant retrait une ligne parcourant toutes les cases une et une seule fois. La condition sur le retrait induit qu'il reste deux morceaux d'un nombre pair de cases (case enlevée noire, puis une succession de "une case blanche+une case noire" jusqu'à la case blanche retirée)ou un seul mais avec un nombre pair également (cas où les cases retirées sont adjacentes).
Une telle ligne est-elle possible
si l'autre côté est de longueur 1 : triviale
si l'autre est de longueur plus grande :
on met le rectangle avec côté de longueur paire horizontalement, on part de la case en bas à gauche, on monte jusqu'à la case en haut à gauche puis on va jusqu'en haut à droite puis on va jusqu'en bas à droite et on revient en zigzaguant (tout droit si l'autre côté de longueur 2).

Ma solution pour le cas 4) :
1024x1024 c'est trop grand comme début, soyons plus modeste.
2x2, là ça va c'est facile
4x4, coupons en 4 damiers 2x2, la case retirée est dans un des 4 damiers je sais remplir ce damier ; puis je place un domino angulaire dans le coin extérieur de ce damier. Les 3 autres damiers sont désormais des damiers 2x2 dont on a retiré une case et donc on sait faire.
8x8, on recoupe en 4 damiers, celui dont on a retiré une case on sait faire, on place un domino dans le coin extérieur on revient au cas 4x4-1 case qu'on sait faire.
16x16 on coupe en 4 damiers...
...
1024x1024 on sait faire
on sait faire

Le 6) ? ... à vous de le créer

[shokin]

Bon... allons-y... pour un autre type de problèmes... toujours avec des domini...

6) a) Soient des domini 1*2 qui comblent un carré 2*2. Combien y a-t-il de possibilités de disposer ces domini ?
b) Même question dans un carré de 4*4.
c) Et dans un carré de 6*6 ?
d) Essayer de chercher une formule (je n'ai pas encore cherché) pour généraliser à 2n*2n.

7) Mêmes questions que 6), mais l'on veut autant de domini "verticaux" que de domini "horizontaux" !

Shokin

[invite35452583]

J'ai trouvé pour le 6)a)
Comment compte-t-on ? Les configurations images par symétrie du carré sont comptées pour un ou les distingue-t-on ?

?En ne distinguant pas les images je trouve 36 pour le 6)b), c'est bon??

[invité576543]

Sur le 6c, je m'étais penché sur la question l'année dernière ou celle d'avant, en plus ambitieux, rectangle nxm, avec au moins un des deux pairs. J'avais abandonné...

Pour la bande 2xn, ça va.

Récurrence simple sur le premier "vertical"

Bn = Bn-1 + Bn-3 + Bn-5 + ...

avec par convention B-1=1

D'où Bn = Bn-1 + Bn-2, c'est la suite de fibonacci 1, 2, 3, 5, 8, 13, ...

Mais quand on passe à la bande 3x2n, c'est une autre paire de manche.

Je ne pense pas que se limiter aux carrés soit vraiment une simplification, mais qui sait...

Cordialement,

[shokin]

J'ai trouvé pour le 6)a)
Comment compte-t-on ? Les configurations images par symétrie du carré sont comptées pour un ou les distingue-t-on ?

?En ne distinguant pas les images je trouve 36 pour le 6)b), c'est bon??

Oups... j'aurais dû préciser... on va dire que deux situations symétriques ou rotatives sont différentes, comme si le carré était numéroté de 1 à 2n dans les deux axes.

Bon... je vous laisse investiguer... astheure je vais me coucher.

NB : Pour le 6) plus que pour 6*6 et je n'ai pas trouvé de formule pour généraliser à 2n*2n.

Shokin

[Speedy311]

Pour la question d) (problème 4) cela marche pour n'importe quel damier avec un des côtés egale a 2^n. On démontre facilement par recurence et avec les congruences que 2^2n -1 est divisible par 3.