Défi 9 ( un jeu de taquin )

[Imod]

Un petit problème pas trop difficile pour finir l'année .

On se donne un rectangle à côtés entiers impairs mXn recouvert à part la case supérieure gauche par des dominos 2X1 . Montrer que l'on peut en déplaçant les dominos selon le principe du taquin ( c'est à dire en faisant glisser un domino vers la case vide ) libérer chaque case d'angle .

Bon courage et bonne fin d'année !

Imod

[Imod]

Pas beaucoup de réactions semble-t-il ? :dodo:

Je donnerais bien un indice mais j'ai toujours eu une façon un peu saugrenue d'aborder ( et parfois résoudre ) les problèmes et j'aimerais bien voir une autre façon de faire . En tout cas , il n'y a pratiquement pas de calcul à faire il "suffit" comme souvent de trouver "la" bonne approche .

Imod

[MikO]

ok ftg jcrois que c mieu.

[alben]

Pas beaucoup de réactions semble-t-il ? :dodo:
Imod

Hé laisse nous cuver un peu !!
Il suffirait de prouver que toutes les dont les coordonnées sont toutes deux impaires sont libérables.
Y a plus qu'à
:briques:

[Imod]

Pas de problème Alben , n'ayant pas de réponse je me demandais s'il restait quelqu'un au bout du fil . Je te laisse peaufiner ta solution ( qui ressemble beaucoup à la mienne ) !

Imod

[darkmaster]

Enfin, je trouve la solution. Mon français est pas très bien, donc démandez-moi si vous être pas compris.

D'abord, on note that tous les cases qui peut être libérés ce sont les cases dont les coordonnées impares. On remplace ces cases par les points d'un graphe. Après , on contruit un graphe par placer les vecteurs entre les points:
on considère deux point voisins: si il y a un domino qui a un bout sur un point et un bout vers un autre, on met un vecteur entre eux, le sens est le sens de domino. Comme image:
[img][img=http://img412.imageshack.us/img412/5783/graphewc0.th.png][/img]
( dans l'image, la case vide c'est la case inférieur gauche)
Et bon , pour la rectangle (2t+1) x (2v+1) on obtient un graphe (t x v). Chaque point dans le graphe est lié avec au moins d'un autre point par un vecteur. Et c'est sûr qu'il y a pas de cycles dans le graphe. ( Si il y a un cycle , c'est facile de démontrer que le cycle occupe 9+6k+4d cases , mais il faut un nombre pair (2u) de cases pour le périmètre, donc le nombre de cases intérieures du cycle est 9+6k+4d-2u qui est impair. On ne peut pas mettre les dominos dans l'intéreur du cycle (absurde) )
Par suite, on peut libérer tous les cases dont les coordonnées impaires par aller en sens inverse des vecteurs. ( Si on ne peut pas accéder le point A , c'est à dire qu'on ne peut pas accéder un point B qui a le vecteur vers A, et c'est à dire qu'on ne peut pas accéder un point C qui a le vecteur vers B et different que A et B car il y a pas de cycle, ect.., et bien , à cause de la limité du nombre de points, on a une contradition)
Bonne année pour tous.

[Imod]

Bonjour darkmaster .

Il y a 2 petites choses que je n'ai pas compris .

1°) Comment construis-tu ton graphe orienté ?
2°) Pourquoi une boucle cernerait un nombre impair de cases : prends cinq dominos et tu peux facilement faire une boucle avec deux cases ( donc un domino ) à l'intérieur .

Il reste des choses à voir mais ton idée est sûrement une bonne piste .

Bon courage !

Imod

[darkmaster]

Salut, Imod,
Pour la question 1:
Comme l'image que j'ai posté:
Les cases considerées (les cases dont les coordonnées impaires) se tranforment aux points de graphe.
et le vecteur est mis entre deux points A et B si il y a un domino dont un bout sur la case A et autre bout vers la case B. (le sens de la flèche est vers B)
Pour la qestion 2:
cinq domino n'est pas accepté car il faut mettre cinq points pour la boucle (on peut jamais faire ça)
On peut contruire une boucle par d'abord prendre un carré (3 x 3) qui contient 4 points aux angles et réunir d'autres carrés (3 x 3) à lui pour la rendre une boucle plus grande ( Chaque fois on fait ça on adjuste 6 ou 4 cases ). Et bon, le nombre des cases doit e^tre 9+6k+4d.
Et regarde le périmètre, il contient u points , il a donc 2u dominos.
Et bien le nombre des cases intérieuses est 9+6k+4d-2u impaire.

[Imod]

Je te lirai et te répondrai plus tard ( j'ai autre chose de prévu ce soir ) , désolé !

A tout à l'heure .

Imod

[Imod]

Bonsoir , Darkmaster , avec toutes mes excuses pour mon absence .

Il y a encore beaucoup de choses qui me gènent dans ta "solution" . Le graphe orienté que tu crées peux très bien être orienté dans les deux sens ( prendre deux dominos dans le prolongement l'un de l'autre ) . D'autre part , certaines cases impaires ne pourrons jamais être libérées et ton raisonnement n'en tiens pas compte . Pour finir , il est certain qu'une boucle comme tu l'as définie contient un nombre impair de cases mais encore faudrait-il vraiment le prouver .

Le problème n'est pas fini , loin de là !

Imod

[darkmaster]

et encore une fois je te comprends pas.

Le graphe orienté que tu crées peux très bien être orienté dans les deux sens ( prendre deux dominos dans le prolongement l'un de l'autre )

C'est à dire quoi?

certaines cases impaires ne pourrons jamais être libérées et ton raisonnement n'en tiens pas compte

Donne-moi un example .

il est certain qu'une boucle comme tu l'as définie contient un nombre impair de cases mais encore faudrait-il vraiment le prouver .

Uhm le but est prouver qu'il y a un chemin pour aller de la case vide à la case que l'on veut. Tu sais que chaque case est lié avec une autre case, mais c'est pas suffit de dire qu'il y a un chemin. Donc il faut prouver qu'il y a pas de boucle comme ça.

Je pense que la démontration est correcte. Peut-être mon manque de vocabulaire la rend mauvais.Désolé.

[Imod]

Désolé , Darkmaster , mais ta démonstration n'est vraiment pas complète , je te le prouverais dès demain ce soir je suis celui qui ne conduit pas ( si tu vois ce que je veux dire ) :we:

Imod

[darkmaster]

Désolé , Darkmaster , mais ta démonstration n'est vraiment pas complète , je te le prouverais dès demain demain car ce soir je suis celui qui ne conduit pas ( si tu vois ce que je veux dire ) :we:

Imod

je comprends.
Et demain je vais poster quelqu'images pour ma démontration.

[Imod]

Un exemple de case impaire ne pouvant pas être libérée :



Modif : je crois que j'avais mal compris ce que tu appelais "cases impaires" , donc d'accord pour le graphe ( et mon contre-exemple n'en est pas un ) . Il reste quand même à montrer :
1°) Le graphe n'a pas de boucle .
2°) Le graphe est connexe car même sans boucle , on pourrait imaginer un circuit allant d'une case de bord à une autre .

Imod

[darkmaster]

Un exemple de case impaire ne pouvant pas être libérée :



Modif : je crois que j'avais mal compris ce que tu appelais "cases impaires" , donc d'accord pour le graphe ( et mon contre-exemple n'en est pas un ) . Il reste quand même à montrer :
1°) Le graphe n'a pas de boucle .
2°) Le graphe est connexe car même sans boucle , on pourrait imaginer un circuit allant d'une case de bord à une autre .

Imod

Pour modif: oui, ton example n'est pas la "case impare".
Pour la question 2: on peut pas faire le circuit. Imagine combien de cases on a pour le circuit: 2(m+n)-5 cases , et combien de cases on doit avoir pour les dominos: un nombre pair
Pour la boucle: J'ai trouvé un trou dans ma démontration. Je vais corriger. Mais on peut facilement noter que toutes les boucles sont les réunion des carré (3 x 3) tels que ils ont "cases impaires" communs.

[darkmaster]

Et bon, il n'y a que 4 types de réunir un carré aux autres:
Type 1: adjouter 8 cases:



Type 2: ajouter 6 cases:

type 3: ajouter 4 cases:

type 4: ajouter 2 cases:

Voilà, le nombre des cases d'une boucle doit être la forme : 9+8s+4q+2k qui est impaire. On peut pas mettre les dominos dans la boucle. Donc, il n'y a pas de boucles.

[darkmaster]

Je vais essayer d'être plus clair pour démontrer que le graphe est connexe:
Supposé que le graphe est pas connexe: c'est à dire qu'on peut pas libérer une case impaire A_0. On sais bien que A_0 doit être liée avec une autre case A_1. On peut pas libérer A_0 , On peut pas donc libérer A_1. Et On sais bien que A_1 doit être liée avec une autre case A_2. On peut pas libérer A_1 , On peut pas donc libérer A_2. Et on peut toujours faire ça car il y a pas une boucle ( A_n n'est pas liée avec A_i , i < n-1). Et bon, n tend ver l'infinie, mais n est limité ( contradition)

[Imod]

D'accord , Darkmaster , on peut considérer le problème résolu et tu peux proposer un autre défi . Personnellement j'avais trouvé une petite astuce évitant le côté un peu pénible de la démonstration de la non-existence de boucle en considérant un graphe rouge et un noir qui correspondent pour ta démo à pair et impair .

On numérote les cases du rectangle de la façon suivante :

0 ; 1 ; 2 ; … ; m-1
m ; m+1 ; … ; 2m-1
…
(n-1)m ; (n-1)m+1 ; … ; nm-1 .

Dans un premier temps , on ne déplace pas les dominos : la case 0 est vide et les autres sont occupées par un domino et un seul . Chaque domino recouvre une case paire et une case impaire .
On divise les cases paires en deux catégories , les rouges et les noires :
Rouges : le reste ( et le quotient ) de la division du numéro de la case par m est pair .
Noires : le reste ( et le quotient ) de la division du numéro de la case par m est impair .

On colorie ensuite chaque domino de la couleur de la case paire qu’il recouvre et on colorie les cases de la même façon , on a ainsi colorié l’ensemble des cases et l’ensemble des dominos en deux couleurs .

On remarque ensuite que chaque domino dans sa position initiale dispose au plus d’un seul déplacement possible celui qui amène sa case paire sur sa case impaire et que la case d’arrivée de la case impaire est de la couleur du domino . Partant d’un domino on peut construire une ligne brisée en reliant la case paire du domino à la case ou aboutirait sa case impaire si on déplaçait le domino et en réitérant le processus sur le nouveau domino , on obtient une chaîne de dominos ( unicolore ) .



1°) Deux chaînes de couleurs différentes ne peuvent pas se croiser :

La case du croisement serait bicolore .

2°) Une chaîne ne peut pas faire de boucle :

S’il existait une boucle , il existerait à l’intérieur de celle-ci un domino dont la couleur ne serait pas celle de la boucle . En créant la chaîne générée par ce domino on obtiendrait une nouvelle boucle et ainsi de suite à l’infini ce qui bien sûr est impossible .

Considérons maintenant une case d’angle autre que la case vide et considérons la chaîne engendrée par le domino ( rouge ) qui occupe cette case . Cette chaîne ne pouvant boucler va terminer sa course sur une case n’ayant pas de domino . Comme tous les dominos rouges disposent d’un déplacement qui ne sort pas du rectangle , la chaîne ne peut se terminer que dans le coin supérieur gauche . Il suffit alors de déplacer les dominos en remontant cette chaîne pour libérer la case d’angle .

Voilà , c'est un peu moins fastidieux que l'étude des différents cas mais ta méthode est tout à fait valable . :++:

Imod

[darkmaster]

uhm oui, Imod. Je déteste aussi la disjonction des cases. Merci d'avance.