La danse des corbeaux

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Patastronch

22 arbres sont mis en rond. Sur chaque arbre se pose un corbeau. Toutes les minutes, 2 corbeaux se déplacent sur un arbre voisin. Peuvent ils, apres un certain nombre de minutes, se rassembler tous sur un meme arbre ?


Posted by: fahr451

je ne comprends pas l'énoncé

peuxtu préciser "voisin"

si voisin n'implique pas le même arbre pour les deux corbeaux c'est évident

c'est donc le même arbre choisi pour les 2 ?


Posted by: Patastronch

Citation:
Posté par fahr451
je ne comprends pas l'énoncé

peuxtu préciser "voisin"

si voisin n'implique pas le même arbre pour les deux corbeaux c'est évident

c'est donc le même arbre choisi pour les 2 ?


Non pas forcément. 2 corbeaux quelconques vont sur une arbre voisin ( juste a coté) quelconque qui peuvent etre différent pour les 2 corbeaux.


Posted by: Imod

Dans ce type d'exercices , il faut trouver l'invariant : il y a toujours un nombre pair d'arbres avec un nombre pair de corbeaux . C'est vrai au départ et ça le reste à chaque étape , conclusion : c'est impossible .

Imod


Posted by: fahr451

je ne comprends rien

pour 4
numérotés dans le sens des aiguilles d'une montre
1ere étape corbeau 1 va sur 2 et corbeau 4 va sur 3

2 ieme étape les 2 corbeaux 2 vont sur 3

c'est fini

idem pour 2n


Posted by: Flodelarab

Citation:
Posté par fahr451
je ne comprends rien

pour 4
numérotés dans le sens des aiguilles d'une montre
1ere étape corbeau 1 va sur 2 et corbeau 4 va sur 3

2 ieme étape les 2 corbeaux 2 vont sur 3

c'est fini

idem pour 2n
a priori, j'avais compris de la même façon que toi.


Posted by: Imod

Citation:
Posté par fahr451
je ne comprends rien

pour 4
numérotés dans le sens des aiguilles d'une montre
1ere étape corbeau 1 va sur 2 et corbeau 4 va sur 3

2 ieme étape les 2 corbeaux 2 vont sur 3

c'est fini

idem pour 2n


En effet c'est possible si le nombre d'arbre est multiple de 4 mais sûrement pas pour un simple multiple de 2 il suffit d'essayer avec 2 arbres pour s'en rendre compte .

Imod


Posted by: fahr451

ah oui

j'ai tout faux j'avais pensé (abusivement) que ça marchait pour 4 donc pour tout le monde


Posted by: Imod

Citation:
Posté par fahr451
ah oui j'ai tout faux


Pas plus que moi mais je pense avoir trouvé !!! Comptons le nombre minimal de sauts menant tous les corbeaux sur la branche fatidique : 2(1+2+...+10)+11 . Tout passage par l'autre côté ou éventuels aller-retours ne change pas la parité du nombre de déplacement qui est donc impair : impossible .

Imod


Posted by: Patastronch

En effet, Imod a trouvé l'astuce










-