Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 25-09-2009 20:37:14

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Libérer lse coins

Bonsoir smile

Une sorte de jeu de taquin avec des dominos .

On recouvre sans chevauchement et complètement ( hormis la case 1X1 en haut à gauche ) un rectangle mXn avec des dominos 1X2 . On peut alors faire glisser les dominos dans le rectangle comme dans un jeu de taquin ( appelé aussi pousse-pousse ) . Peut-on toujours libérer les cases de coin quelle que soit la disposition initiale des dominos ?

http://img136.imageshack.us/img136/1929/dominosdecoin.jpg

Sur cet exemple c'est possible cool

Vasimolo



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 25-09-2009 23:15:42

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

libérer lrs coins

Je ne trouve pas de configuration ou on ne puisse pas liberer les coins.
Ca ne prouve rien, mais c'est un debut...

dans cet exemple:

http://www.prise2tete.fr/upload/dhrm77-domino1.PNG
pour liberer en haut a droite il faut passer par en bas a gauche...


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #3 - 26-09-2009 13:42:27

gabrielduflot
Expert de Prise2Tete
Enigmes résolues : 34
Messages : 609

Libérrer les coins

a condition que m et n soient impairs on pourra toujours trouver une solution

 #4 - 28-09-2009 09:27:21

bagouze
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 589
Lieu: Lille

Lbérer les coins

Je sais pas comment on peut démontrer un truc pareil, mais pour avoir simplement cherché (en vain) une situation où c'est impossible, je répondrai donc oui big_smile


"Nous sommes tous dans le caniveau, mais certains d'entre nous regardent les étoiles." (O. Wilde)

 #5 - 28-09-2009 22:33:07

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Libérer les cons

Bonsoir smile

Comme le fait remarquer gabrielduflot le pavage n'est possible que lorsque les deux côtés du rectangle sont impairs mais ça ne répond pas vraiment à la question roll

On présent bien que la réponse est oui mais l'exemple de dhrm77 montre que les déplacements peuvent être assez laborieux mad

Je vous laisse chercher encore un peu cool

Vasimolo

 #6 - 28-09-2009 22:36:13

kosmogol
Banni
Enigmes résolues : 49
Messages : 11,928E+3

libérer kes coins

Pour ma part, tu peux ajouter la fin de phrase suivante à :

Je vous laisse chercher encore un peu

ou attendre un peu plus longtemps la réponse lol

--
mais elle sera toujours lue avec beaucoup d'intérêt wink


http://enigmusique.blogspot.com/

 #7 - 28-09-2009 23:03:33

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

libéret les coins

Un message bien sympa wink mais c'est tellement plus chouette quand on peut trouver soi même ( avec un peu d'aide ) .

Je précise que ces problèmes mon souvent demandé beaucoup-beaucoup- ...   d'efforts et qu'il n'y a aucune honte à sécher un peu et même beaucoup big_smile

Vasimolo

 #8 - 29-09-2009 13:54:46

Bamby2
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 152

libéree les coins

perso j'ai envie de généraliser a toutes les cases "impaire" (1.1) (1.3) etc
comme le rectangle est de longueur impaire, en cas particulier on a tous les coins.

reste a démontrer que ça fonctionne.
j'ai essayé par récurrence, mais je ne suis pas satisfait de ma démonstration, puisque le rang N+1 n'a pas le "plan" du rang N (il y a des rectangle a cheval)... je sèche un peu sur cette difficulté.

 #9 - 29-09-2009 19:03:48

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

linérer les coins

Il est bien sûr question de parité ,

  j'ai aussi classé les cases et les dominos en différentes catégories mais j'ai très vite abandonné l'idée de la récurrence . J'ai une démonstration complète mais qui ne me convient pas beaucoup car un peu longue et "hermétique" smile

Une remarque , chaque domino , dans sa position de départ est soit "bloqué" soit "déplaçable" d'une seule façon .

Vasimolo

 #10 - 29-09-2009 22:21:09

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

mibérer les coins

Bonsoir E271828 smile

Je lirai ton message plus attentivement demain , mais je suis presque convaincu qu'il contient une faille ( on peut quand même espérer smile)

Le problème a été présenté il y a deux ans sur un autre forum , j'ai proposé une solution qui a été acceptée sans enthousiasme ( surtout de ma part roll) .

J'aimerai bien quelques idées originales de solution , mais bien sûr je vous donnerais mes idées , si personne ne trouve mieux ( ce qui m'étonnerais ) .

Vasimolo

 #11 - 10-10-2009 01:27:34

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

libérer les voins

Voilà le type de représentation que j'ai utilisé , peut-être quelqu'un saura en tirer une solution courte et limpide ?

http://img340.imageshack.us/img340/2692/dominospoints.jpg

Vasimolo

 #12 - 10-10-2009 10:00:35

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

libérer les cpins

Ta représentation permet de mieux exprimer l'intuition que l'on pouvait avoir... principalement sur la position des dominos immobiles.

On remarque aussi que le tableau est recouvert soit de dominos "pair" (i.e. initiallement sur case (pair,pair) soit de dominos "impairs" (i.e. initiallement sur case (impair,impair). Il n'y a pas d'autres types (d'ailleurs, le type de dominos ne change pas même après mouvement).

On remarque que le "trou" ne se propage que de case (impair,impair) en case (impair,impair) puisqu'il bouge de 2 cases, la longueur d'un domino.

Cela permet d'affirmer que les dominos "pair" initiallement sur case (pair,pair) ne pourront jamais bouger (l'autre case qu'il recouvre n'étant pas (impair, impair).

Considérons 2 cases (impair,impair) sur le tableau, et démontrons qu'il y a toujours un chemin de dominos impairs qui les relie.

Par l'absurde, si il n'y avait pas de chemin, cela signifierait qu'il existe une ligne (brisée) de dominos pairs qui sépare le tableau en deux parties d'un bord à un autre avec chacune de nos 2 cases impaires dans une partie.
Or, une ligne de dominos pairs reliant 2 bords aurait donc des extrémités de type (impair,pair) ou (pair,impair) (ne pouvant avoir qu'une case contre le bord à chaque extrémité et ne pouvant d'ailleurs pas longer un bord). Une telle ligne a un nombre impair de cases, ce qui est impossible avec des dominos.

Donc il y a un chemin de dominos impairs qui relie nos 2 cases (impaires, impaires).
Sur un chemin de dominos impairs, on peut propager le "trou" de proche en proche.
Appliquée aux 3 coins, cela répond à la question (enfin je crois...).

 #13 - 10-10-2009 12:30:19

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Liibérer les coins

Merci pour ta réponse dylasse smile

J'ai sûrement raté quelque chose . Je ne comprends pas pourquoi le fait que les dominos pairs=rouges ne puissent pas longer le bord entraîne qu'une chaîne rouge de bord à bord comporte nécessairement un nombre impair de cases roll

Vasimolo

 #14 - 10-10-2009 13:31:47

Bamby2
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 152

Libérer les coinss

j'ai eu un peu de mal aussi, c'est le point de la démonstration qui m'a fait ticker a la 1ere lecture, mais après avoir retrouver quelque souvenir sur les permutations, ca semble évident.

suposons un chemin entre deux  cases, alors a chaque cases parcouru on fait UNE permutation (pair/impaire=>paire/paire ou paire/paire =>pair/impaire etc  etc 4 type de cases pouvant aller sur 4 autres type.)

les dominos contenant une case "rouges" ne touchent le bords que sur des cases "pairs impairs" ou "impairs pair"
il faut donc un nombre pair de permutation pour crée un chemin entre de telles cases.

donc, il y a un nombre impaire de case sur le chemin, cqfd.

 #15 - 10-10-2009 17:38:40

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Libére les coins

OK , j'ai compris , en effet comme les deux dimensions sont impaires il n'y peut pas y avoir de chaîne rouge d'un bord à un bord smile

Vasimolo

 #16 - 11-10-2009 12:48:33

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

libérer mes coins

Après réflexion, je me suis aperçu qu'il faut compléter ma démo.

En effet, on pourrait imaginer que 2 chemins rouges se rejoignent juste en un coin et ainsi créent une séparation entre les cases impaires que l'on veut relier.

C'est en fait impossible car les 2 extrémités non bord de ces 2 chemins devraient être des cases (pair,pair).

remarque : c'est amusant de voir que toutes les dominos immobiles (ou pairs) sont reliés par un chemin unique à un bord.

 #17 - 11-10-2009 17:56:43

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Libérer els coins

Je l'avais remarqué en effet smile

D'ailleurs si tu reprends le dessin avec les points rouges et noirs tu pourras remarquer qu'en partant d'un point noir quelconque et en suivant le chemin du domino qui le contient , on aboutit à un nouveau point noir et ainsi de suite jusqu'à la case libre . La même stratégie en partant d'un point rouge s'échoue sur le bord du jeu .

C'est comme ça que j'avais résolu initialement le problème , mais c'est un peu plus long qu'avec ta méthode wink

Vasimolo

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete