22 arbres

par **aviateurpilot** » 18 Juin 2006, 00:00

22 arbres sont mis en rond ; sur chaque arbre se pose un corbeau. Toutes les minutes, deux corbeaux se déplacent chacun sur un arbre voisin du leur. Est-il possible pour les corbeaux, après un certain nombre de minutes, de se rassembler tous sur le même arbre ?

par **scelerat** » 19 Juin 2006, 08:35

Le nombre de deplacements necessaires est de 121 + 2k, il est impair...

par **olivthill** » 19 Juin 2006, 09:47

Numérotons les arbres de 1 à 22, et essayons de regrouper tous les corbeaux sur l'arbre numéro 1.

Le corbeau de l'arbre numéro 2, devra faire 1 saut ou bien 21 sauts s'il va dans l'autre sens. C'est un nombre impair.

Le corbeau de l'arbre numéro 3, devra faire 2 sauts ou bien 20 sauts s'il va dans l'autre sens. C'est un nombre pair.

Il faut que 21 corbeaux se déplacent.
Comme 21 est un nombre impair, et que les corbeaux doivent se déplacer deux par deux, le problème n'a pas de solution. Par contre, avec trois arbres (ou trois millions et un arbres) et 3 corbeaux (ou trois millions et un corbeaux), ce serait possible.

par **Jacques Lavau** » 19 Juin 2006, 11:13

Posons le déplacement le plus simple possible où le 1 ne bouge pas, et voit les autres se rassembler autour de lui.
a : 2 et 22 sautent sur place 1.
b : 3 et 21 sautent sur places 2 et 22 puis sur 1.
..
j : 11 et 13 sautent sur places 10 et 14... puis sur 1.
k : Le corbeau 12, opposé à 1, doit faire 11 sauts pour rejoindre l'arbre 1. Or c'est un nombre impair de sauts, dont seulement 10 ou 12 peuvent être compensés par des sauts d'un autre corbeau.

Mais je n'ai pas prouvé que cette impossibilité soit générale, que le fait que 22 soit pair, laisse la charge des déplacements à un nombre impair de corbeaux.

Généralisation : Tous les arbres étant occupés au départ, un des corbeaux va forcément revenir à son point de départ, donc faire un nombre pair de sauts. Ce qui impose un nombre restant impair de sauts à un nombre impair de corbeaux. Impossibilité générale donc.

par **aviateurpilot** » 19 Juin 2006, 13:27

Le corbeau de l'arbre numéro 2, devra faire 1 saut ou bien 21 sauts s'il va dans l'autre sens.

il peux faire 3 saut
2=>3=>2=>1

par **aviateurpilot** » 19 Juin 2006, 13:35

un des corbeaux va forcément revenir à son point de départ

mais pas tous les corbeaux
donc ce que t'a dit est faux

Jacques Lavau a écrit:donc faire un nombre pair de sauts. Ce qui impose un nombre restant impair de sauts à un nombre impair de corbeaux

par **Jacques Lavau** » 19 Juin 2006, 14:59

aviateurpilot a écrit:mais pas tous les corbeaux
donc ce que t'a dit est faux

Ce qui impose un nombre restant impair de sauts à un nombre impair de corbeaux : les autres corbeaux.
On peut les apparier presque tous sauf un.
Sur les 21 corbeaux restants, 10 ont un nombre pair de sauts à faire, 11 un nombre impair (des deux plus voisins, au diamétralement opposé). Il en reste donc bien un qui ne sera pas sur le même arbre que les autres.
Dans mon algorithme simplificateur, c'est le corbeau diamétral qui ne peut rentrer. On peut compliquer les jeux de sauts pour que le diamétral rentre, mais c'est un autre qui sort.

par **abel** » 19 Juin 2006, 16:56

C'est impossible, avc les meme arguments exposés précédemment.
On peut faire en sorte de se retrouver avec 21 corbeaux sur un arbre et 1 corbeau en dehors :
En rassemblant ts les corbeaux sur l'arbre 1 :
on déplace (2,3) sur (1,2) ce qui fait que 2 est sur 1 et 3 sur 2, puis on met (4,5) sur (3,4) etc...jusqu'à mettre (21,22) sur (20,21) du coup cela ns ramene a mettre 20 corbeaux sur 21 arbres et de proche en proche on arrive à 2 corbeaux sur 3 arbres donc le pb est equivalent à placer 2 corbeaux avec 3 arbres et on voit bien que cette situation est impossible sachant que chacun des 2 corbeaux est sur un arbre différent et le 3e arbre correspond à l'arbre ou il faut tous les placer.
Bon je sais que l'equivalence des 2 pb n'est pas trop justifiée mais ca se comprend non ???

par **aviateurpilot** » 19 Juin 2006, 17:19

abel a écrit:on déplace (2,3) sur (1,2) ce qui fait que 2 est sur 1 et 3 sur 2, puis on met (4,5) sur (3,4) etc...jusqu'à mettre (21,22) sur (20,21) du coup cela ns ramene a mettre 20 corbeaux sur 21 arbres.........cette situation est impossible sachant

ce n'ai qu'un exemple

par **aviateurpilot** » 19 Juin 2006, 17:23

Jacques Lavau a écrit:Ce qui impose un nombre restant impair de sauts à un nombre impair de corbeaux : les autres corbeaux
On peut les apparier presque tous sauf un.

on peut trouver plus d'un corbeau qui fait un nombre pair de sauts

par **abel** » 19 Juin 2006, 17:34

En fait il faut prendre le pb a l'envers. Si on imagine avoir 22 corbeaux sur 1 arbres, sachant que les deplacement sont "reversibles". on sort tous les corbeaux 2 par 2 et on n'arrivera pas à disposer les 22 corbeaux sur 22 arbres différents...

par **aviateurpilot** » 19 Juin 2006, 17:46

pour koi? :hein: :hein:

par **abel** » 19 Juin 2006, 18:12

- déjà les déplacement sont réversibles car si on bouge 2 corbeaux sur l'arbre voisin on peut tjs deplacer dans l'autre sens pr revenir a la situation initiale (en fait on fait des permutations d'un ensemble de 22 éléments qui sont des bijections et donc leur composées est une bijection et on sait exprimer leur inverse à l'aide des permutaitions autorisées).
- Maintenant si on a 22 corbeaux sur un seul arbre cela revient à avoir 12 sur un arbre et 10 sur un autre arbre en les sortant 2 par 2 sur un arbre voisin ce qui est equivalent a avoir 6,6,6,4. sachant qu'on peut "translater" les groupements de corbeaux, il n'est pas important d'avoir un arbre voisin. Ainsi on se ramene à 4,2,4,2,4,2,2,2 puis à 2,2,2,2,2,2,2,2,2,2,2 que l'on peut supposer tous voisin car on peut "translater" les groupes de 2 pr arriver à cette situation.
- si on a 2,2 on peut les séparer en 1,1,1,1 avec 2 translations du coup vu qu'on a 11 groupes de 2 on peut en prendre 10 pr arriver à :
1,1,...,1,2 du coup, le pb de départ revient a mettre 1 corbeau par arbre sur 20 arbres, un arbre vide et un arbre contenant 2 corbeau et on voit que c'est incompatible avc l'enoncé de départ car il faudrait bouger un seul corbeau et donc le passage d'une situation à l'autre est impossible en utilisant les permutations autorisées...donc on ne peut pas avoir 22 corbeaux sur un arbre...

EDIT : pour parler d'une maniere plus "mathematique" mon raisonnement revient à dire qu'il existe une permutation de singature 1 (car deplacer 2 corbeaux est une permutation de signature 1 et les composées st de signature 1) permettant de passer de 22 corbeau sur 22 arbres à 20 sur 20 arbres, un arbre vide et un arbre avc 2 corbeaux...Or il existe aussi une permutation de signature -1 permettant de lier ces 2 situations (deplacer un corbeau) donc c'est absurde.

par **Jacques Lavau** » 19 Juin 2006, 19:34

aviateurpilot a écrit:on peut trouver plus d'un corbeau qui fait un nombre pair de sauts

Sur les 21 corbeaux restants, 10 ont un nombre pair de sauts à faire, 11 un nombre impair de sauts (des deux plus voisins, au diamétralement opposé). Il reste donc bien un corbeau qui ne sera pas sur le même arbre que les autres.

Il ne fait aucun doute que 10 corbeaux qui ont un nombre pair de sauts à faire, c'est plus nombreux qu'un seul. Dupont et Dupond n'auraient pas mieux dit.
Thomson and Thompson, in english.

par **aviateurpilot** » 19 Juin 2006, 22:51

en fin
je vien de trouvé la solution
=> on numerote les arbres de 0 jusqu'à 21
=> on suppose que tous corbeaux seront sur l'arbre 0 à la fin
=> on prend un sens positif des deplacement si un corbeau ce deplace selon ce sens (saut+1) sinon (saut-1)

à t=0 soit le corbeau

avec i appartien à {0,1,2,...,21}
soit k le nombre des sauts +1 si k' le nombre des sauts -1
donc i+k-k'=0 [22]
donc i+k-k'=0 [2]
donc i+k-k'+2k'=0 [2]
donc i+(k+k')=0 [2] donc (k+k') et i ont la meme parité
k+k' est le nombre des deplacement de

=> donc un nombre pair de sauts pour

=> un nombre impair de sauts pour

car

donc le nombre total des sauts est impair (1)
or dans chaque minute 2 corbeaux se deplace alors le nombre total dois etre pair (2)
(1)#(2) impossible de se rassembler tous sur le même arbre
merci pour vos reponce

22 arbres

22 arbres

Posons le déplacement le plus simple possible

Les autres corbeaux

Il ne fait aucun doute que 10 corbeaux qui ont un nombre pai

Qui est en ligne