Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Affichage des résultats 1 à 22 sur 22

Pavage dominos

  1. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    47
    Messages
    2 523

    Pavage dominos

    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.

    -----

     


    • Publicité



  2. invité576543
    Invité

    Re : Pavage dominos

    Spoiler (?) pour b) et c)


    Citation Envoyé par homotopie Voir le message
    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,
     

  3. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 819

    Re : Pavage dominos

    Une tite piste :

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



    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
     

  4. invité576543
    Invité

    Re : Pavage dominos

    Citation Envoyé par homotopie Voir le message
    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,
     

  5. _Goel_

    Date d'inscription
    août 2005
    Localisation
    Toulouse
    Âge
    35
    Messages
    3 234

    Re : Pavage dominos

    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 ?
    Le succès c'est d'être capable d'aller d'échec en échec sans perdre son enthousiasme
     


    • Publicité



  6. invité576543
    Invité

    Re : Pavage dominos

    Citation Envoyé par _Goel_ Voir le message
    Où est mon erreur ?
    "dont on a retiré une case"

    Cordialement,
     

  7. _Goel_

    Date d'inscription
    août 2005
    Localisation
    Toulouse
    Âge
    35
    Messages
    3 234

    Re : Pavage dominos

    Oups...
    on va faire comme si j'avais rien posté ok !?
    Le succès c'est d'être capable d'aller d'échec en échec sans perdre son enthousiasme
     

  8. _Goel_

    Date d'inscription
    août 2005
    Localisation
    Toulouse
    Âge
    35
    Messages
    3 234

    Re : Pavage dominos

    Je suis sûr qu'il y a un truc !
    Le succès c'est d'être capable d'aller d'échec en échec sans perdre son enthousiasme
     

  9. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    47
    Messages
    2 523

    Re : Pavage dominos

    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 )
     

  10. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    47
    Messages
    2 523

    Re : Pavage dominos

    Citation Envoyé par _Goel_ Voir le message
    Je suis sûr qu'il y a un truc !
    Oui comme pour la magie mais faut le trouver.
     

  11. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 819

    Re : Pavage dominos

    Citation Envoyé par homotopie Voir le message
    +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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
     

  12. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 819

    Re : Pavage dominos

    Citation Envoyé par homotopie Voir le message
    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
    Dernière modification par shokin ; 12/01/2007 à 07h19.
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
     

  13. invité576543
    Invité

    Re : Pavage dominos

    Citation Envoyé par homotopie Voir le message
    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,
     

  14. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 819

    Re : Pavage dominos

    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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
     

  15. invité576543
    Invité

    Re : Pavage dominos

    Citation Envoyé par homotopie Voir le message
    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,
     

  16. invité576543
    Invité

    Re : Pavage dominos

    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,
     

  17. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    47
    Messages
    2 523

    Re : Pavage dominos

    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
     

  18. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 819

    Re : Pavage dominos

    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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
     

  19. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    47
    Messages
    2 523

    Re : Pavage dominos

    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??
     

  20. invité576543
    Invité

    Re : Pavage dominos

    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,
     

  21. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 819

    Re : Pavage dominos

    Citation Envoyé par homotopie Voir le message
    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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
     

  22. Speedy311

    Date d'inscription
    août 2017
    Âge
    19
    Messages
    1

    Re : Pavage dominos

    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.
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. pavage d'un icosaèdre
    Par toe dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 28/02/2007, 16h44
  2. fils fondu dominos a mon cumulus urgent svp
    Par tintin59390 dans le forum Dépannage
    Réponses: 3
    Dernier message: 27/11/2006, 17h20
  3. Dominos : vitesse du front
    Par m81 dans le forum Physique
    Réponses: 6
    Dernier message: 14/12/2004, 11h00
  4. problème de pavage
    Par gargulp dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/06/2004, 14h56
  5. Front de chute de dominos
    Par m81 dans le forum Physique
    Réponses: 0
    Dernier message: 24/05/2004, 08h09