Bonjour

Il y a clairement un invariant dans le problème ( la somme des valeurs des sommets ) . Il reste à fabriquer une fonction des sommets à valeurs entières qui décroit à chaque opération .

J'ai une petite idée mais pas le temps d'approfondir , @+

Vasimolo

Edit 1 : il me semble que ça marche même si les valeurs ne sont plus entières .
Edit 2 : je crois que j'ai trouvé , je rédigerai la solution plus tard .

J'avais essayé d'étudier la somme des valeurs absolues et la somme des valeurs absolues des différences consécutives qui étaient 2 notions sympa d'écrêtement mais ça marche pas ainsi que des solutions analogues qui ont abouties dans ma corbeille à papier.

Ma deuxième idée est de montrer que  :
1 )on ne peut pas revenir a un état quand on y est déjà passé (forcément vrai, sinon on pourrait trouver des trajectoires cycliques et le résultat serait faux)
2 ) il y a un nombre fini de possibilités pour les cases (vrai également si le résultat l'est). Il s'agit par exemple de borner les valeurs.

et de conclure avec le "théorème du tiroir" que on s'arrête à un moment, donc forcement quand tous les nombres sont positifs.
Mais je ne démontre ni le 1) ni le 2)...

Pour le 2 ) je pense que aucun nombre en valeur absolue ne peut être supérieur à la somme des valeurs absolues initiales donc il faut plutôt se pencher sur 1)

Bonne piste ?


______


"En fait il est assez difficile dans ce problème de trouver une quantité entière qui va strictement décroître à chaque opération"


j'en ai une :

Spoiler : [Afficher le message] ma sérénité

On assimile une opération à :
1) un déplacement de la valeur "réelle" négative vers le voisin gauche.
2) un déplacement de la valeur négative "fantôme" vers le voisin droite.
3) la création d'une valeur positive "fantôme" égale à la valeur négative. Donc toute valeur négative contient une valeur positive fantôme. 

Pour toutes les valeurs négatives réelles, on établit une relation réelle fléchée gauche vers une valeur positive. On part d'une valeur négative réelle de référence, et on établit la relation avec la 1ère valeur positive réelle rencontrée à gauche. Si la valeur négative réelle est supérieure en valeur absolue à la valeur positive réelle, on établit une nouvelle relation au départ du négatif vers le positif suivant, voire une 3ème relation,...Quand on a établi toutes les relations nécessaires au départ de catte valeur réelle négative, on recommence avec la 1ère autre valeur négative réelle à droite de la référence. La 1ère relation de cette seconde valeur négative réelle visera la 1ère valeur ou le premier reste de valeur positive réelle disponible à gauche. Comme il y a au total plus de positif que de négatif, toutes les valeurs réelles négatives seront en relation avec une (ou plusieurs) valeur positive réelle.

On réalise le même enchaînement pour les valeurs fantômes: valeurs négatives fantômes vers valeurs positives fantômes. La relation est cette fois fléchée vers la droite. A remarquer qu'ici, quand on aura établi toutes ces relations, le solde sera nul, car la somme des négatifs fantomes est égale à celle des positifs fantômes.

Chaque opération diminue la longueur de chaque relation établie. Quand la longueur d'une relation est à zéro, comme il y a rencontre de + et -, il y a effacement de la relation. L'ensemble des relations est donc convergent vers zéro, et donc les opérations s'arrêtent quand il n'y a plus de relations.

Salut Clydevil: non, les relations ne doivent surtout pas changer. Elles sont établies au départ et ne font que rétrécir ou disparaitre. Dans mon modèle, les relations fixent les objets (valeurs positives ou négatives) aux 2 extrémités. Les objets négatifs se déplacent, les objets positifs sont immobiles.
Tu aurais pu poser ce problème là: quand on actionne une valeur négative, celle ci est déplacée à gauche (ou à droite), et il reste 0 à l'emplacement de l'action. On aboutirait au même résultat final.

J'ai une solution , ça marche mais c'est vraiment tordu :

On note [latex]x_1 ; x_2 ; ... ; x_n[/latex] , les valeurs à chaque sommet , T la somme de ces valeurs et pour i dans [[1 ; n]] on définit :
[TeX]S_i=\{x_i ; x_i + x_{i+1} ; x_i + x_{i+1} + x_{i+2} ; x_i + x_{i+1} + x_{i+2}+ x_{i+3} ; ...\} .[/TeX]
Les indices des [latex]x_i[/latex] sont pris modulo n .

Chaque [latex]S_i[/latex] est infini mais contient un nombre fini d'éléments négatifs ( à chaque ronde on ajoute T ) .

Maintenant que se passe-t-il sur chaque [latex]S_i[/latex] si on effectue l'action proposée ? On notera [latex]x'_i[/latex] et [latex]S'_i[/latex] les nouveaux et pour plus de lisibilité on supposera par exemple qu'on prend l'opposé de l'élément négatif [latex]x_3[/latex] :
[TeX]x'_3=-x_3 , x'_2=x_2+x_3 , x'_4=x_3+x_4 .[/TeX]
Les autres [latex]x_i[/latex] sont inchangés : [latex]x'_i=x_i[/latex] .

Si on détaille les éléments de [latex]S'_i[/latex] on obtient :
[TeX]S'_1=S_1 , S'_2=S_2 , S'_3=S_4 \cup \{-x_3\}, S'_4=S_3-\{x_3\}, S'_5=S_5 , ...[/TeX]
L'ensemble des valeurs des [latex]S_i[/latex] est donc conservé , sauf [latex]x_3[/latex] qui est devenu [latex]-x_3[/latex] . On avait un nombre fini de valeurs négatives et on vient d'en perdre une ...

Vasimolo

Ah oui ça ne marche pas car il faudrait recréer des relations à chaque déplacement. Bon, l'idée ne semble pas pouvoir être prolongée...

Les valeurs ne sont pas forcément entières

Je veux bien développer un exemple numérique mais il cache les choses plus qu'il ne les montre .

Si on veut -3 et des 1 , il faut au moins 5 sommets . Par exemple x1=1 , x2=1 , x3=-3 , x4=1 et x5=1 alors :

S1={1;2;-1;0;1;2;3;0;1;2;3;...}
S2={1;-2;-1;0;1;2;-1;0;1;2;3;...}
S3={-3;-2;-1;0;1;-2;-1;0;1;2;-1;...}
S4={1;2;3;4;1;2;3;4;5;2;...}
S5={1;2;3;0;1;2;3;4;1;...}

Et pour les S'

S'1={1;-1;2;0;1;2;0;3;;1;2;...}
S'2={-2;1;-1;0;1;-1;2;0;1;2;...}
S'3={3;1;2;3;1;4;2;3;4;2;...}
S'4={-2;-1;0;-2;1;-1;0;1:-1;2;...}
S'5={1;2;0;3;1;2;3;1;4;2;3;...}

Il faut surtout regarder l'expression "formelle" des éléments de chaque ensemble ( le passage à l'écriture chiffrée écrase tout ) .

Vasimolo

J'ai trouvé un moyen d'illustrer mais ça va être un peu long .

Je fais ça dans la journée

Vasimolo

Une illustration avec le pentagone précédent :



Pour S1 , S2 et S5 on a les échanges suivant :



Pour S3 :



Et pour S4 :



Est-ce plus clair ?

Vasimolo

3eme indice (gros indice):
Spoiler : [Afficher le message] Prendre un sommet de référence sur le polygone, et regarder la suite des sommes partielles depuis ce sommet dans le sens de parcourt de votre choix.

@portugal: Regarde bien ce que cette inversion fait sur la suite, et tu verras que ça te permet de conclure.

@nodgim: cf MP