Positivez !
dans Les-mathématiques
Bon week-end !
S'il fait trop chaud pour sortir, vous pouvez réfléchir au frais à ce petit problème :
Cent nombres, dont la somme est strictement positive, sont placés le long d’un cercle. On peut remplacer trois nombres voisins quelconques $x,\, y,\, z$ par $x + y,\, -y,\, z + y$, respectivement. Montrez qu’il existe une et une seule collection de cent nombres positifs ou nuls qui peut être obtenue des cent nombres de départ à l’aide des opérations autorisées.
S'il fait trop chaud pour sortir, vous pouvez réfléchir au frais à ce petit problème :
Cent nombres, dont la somme est strictement positive, sont placés le long d’un cercle. On peut remplacer trois nombres voisins quelconques $x,\, y,\, z$ par $x + y,\, -y,\, z + y$, respectivement. Montrez qu’il existe une et une seule collection de cent nombres positifs ou nuls qui peut être obtenue des cent nombres de départ à l’aide des opérations autorisées.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour l'existence, ça n'a pas l'air trop méchant: on prend le plus petit qui sert de -y dans l'opération, ça "améliore" la situation, donc en recommançant, on finit par avoir que des positifs. Bon, je faisais surtout remonter le fil...
avec -3 ; -7, 45
Tu trouves que l'application d'une fois l'opération améliore?
Sinon, très très vague piste: [size=x-small]on imagine qu'ils sont disposés sur une horloge (avec 100 heures ) et que sur midi, il y a un x positif suivi d'un y négatif sur 1H.
on passe à x+y,-y,z+y ce qui permet d'avoir 2 nombres positifs juxtaposer. Peut-être que z+y est négatif, ou pas. S'il l'est
a, z-a, b deviennent a+z-a, a-z, b+z-a, autrement dit, on passe à z, a-z, b+z-a qui ne sont autres que z,y+z, z+b+y et je pense que ce genre d'idée peut marcher en indiçant bien[/size]
\begin{enumerate}
\item la somme des $x_i$ reste constante
\item Soit $T_i$ l'opération appliquée en prenant le $i^{ème}$ terme central. On a: $T_i^{-1}=T_i$
\item En faisant $T_i\circ T_{i+1}\circ T_i$, on a une espèce de super-opération qui pourra permettre de positiver deux (ou trois...) négatifs consécutifs.
\item N'y aurait-il pas moyen de déplacer les négatifs pour les regrouper ?
\item Après, j'ai envie de raisonner sur des boucles de trois nombres, quatre nombres,etc.
\item Faudra sans doute, tôt ou tard, se servir du fait que notre suite de nombres est bouclée: $x_1=x_{101}$
\end{enumerate}
Voilà, comme Christophe je veux juste faire avancer le schmilblick.
L'idée qui devrait marcher, c'est donc d'essayer de faire que dans chaque case on s'approche d'une sorte de moyenne le plus possible.
(Comme tu dis Jacquot, la moyenne ne bouge pas en plus)
C'est donc une sorte de théorème qui dit qu'on peut "lifter"
Je ne sais pas d'où Bu le sort ce problème, mais ça fait un peu penser aux exos d'algèbre linéaire où il faut considérer des matrices avec un extrait de la forme
(1,1,0)
(0,-1,0)
(0,1,1)
et traduire tel ou tel truc bien connu des alglinéairistes en solution populiste (du coup l'unicité et l'existence vont venir en même temps de considérations sur un groupe de matrices, avec peut-être des histoires de stochastique, et tout le tralala)
Comme algorithme permettant d'arriver à une suite de nombres positifs, je propose à chaque itération d'appliquer la transformation au plus petit nombre négatif de la suite.
Un petit programme en Maple pour faire le travail :
Par exemple en partant de [-2,7,-3,-8,12,5,-2] on obtient :
Sur les quelques exemples que j'ai essayés, ça marche.
Pour la preuve maintenant, je pense comme Christophe à une action d'un groupe de matrices (mais j'ai la flemme de réfléchir pour l'instant ).
let pr i n=if i<1 then n else i-1
let su i n=if i>n-1 then 0 else i+1
[size=x-small]let copier t n = let u=Array.create (n+1) 0 in begin for i=0 to n do u.(i)<-t.(i) done ; u end
let op i n t =let (a,b,c)=(pr i n,i,su i n) in begin t.(a)<-(t.(a)+t.(b)); t.(b)<- (-(t.(b))); t.(c)<-(t.(b)+t.(c)); copier t n end
let test t n =let r=ref (0, true, 0) in begin for i = 0 to n do let (a,b,c)=(!r) in let v=t.(i) in if v<c then r:=(i,false,v) done ; let (a,b,c)=(!r) in (a,b) end
let rec presente t n = let (a,b)=test t n in if b then [t] else let u=op a n t in t::(presente u n)
let has() n =let t=Array.create (n+1) 0 in begin for i=0 to n do let r=(Random.int 100) - 50 in t.(i)<-r done; t end
let somme t n =let s=ref 0 in begin for i=0 to n do s:=(!s)+(t.(i)) done; (!s) end
let met t n = let s=(somme t n)-1 in begin for i=0 to n do t.(i)<-(t.(i) - s) done end
let prepare n = let t=has() n in begin met t n; t end[/size]
Prenons une boucle plus petite, de DEUX nombres
Soient $x$ et $y$ leurs valeurs absolues
Existence:
Si notre boucle est $(x;y)$ elle est constituée de nombres tous positifs.
Si c'est $(x;-y)$ on a $x-y>0$.Notons $d$ cette différence
On fait $T_2$, l'opération de terme central à droite, obtenant $(d-y ; y)$
Si ces deux termes sont positifs, on s'arrête.
Si $d-y<0$ on fait $T_1$, obtenant $y-d ; 2d-y$
Si $2d-y<0$, on fait $T_2$, obtenant $3d-y ; y-2d$
$\R$ étant archimédien, il existe $n$ tel que $nd>y$.
Alors au bout de $n$ opérations, les deux termes de la boucle seront positifs.
Unicité: On voit bien que l'on procède par pas d'amplitude $d$ et que si l'on part dans le mauvais sens, on est obligé de revenir.
Maintenant, Mon ambition est d'entamer une récurrence en considérant une boucle de TROIS termes, puis de QUATRE et d'aller ainsi jusqu'à CENT.
Avec la remarque que je faisais plus haut: on peut travailler avec l'opération $T_{i,i+1}$ qui est la composée $T_i\circ T_{i+1}\circ T_i$: elle change les signes de deux termes voisins, tout en les permutant.. l'écart entre les positifs et les négatifs se réduira toujours par pas d'amplitude $d$, somme algébrique de tous les termes, non?
Petit problème: les deux nombres qui sont de même signe ne sont pas toujours les deux mêmes...
A voir . Je reviens plus tard.
Pour n=3, supposons $x,z\ge 0$ et $y<0$. Supposons par exemple $x\le z$. On transforme (x,y,z) en (x+y,-y,y+z). Si ces nombres sont positifs, c'est gagné. Sinon, on transforme en $(-(x+y),x,y+(x+y+z))$ donc soit c'est gagné, soit on est dans la même situation qu'au départ, sauf que le nombre négatif a été remplacé par $y+s$. Au bout d'au plus 2N étapes (où $y+Ns\ge 0$) c'est fini.
Le cas $x,y<0$ est analogue.
Pour n quelconque, on constate que l'on peut faire la transformation
$(x,y,z,t)\to (x+y,-y,y+z,t)\to (x+y,z,-y-z,y+z+t)\to (x+(y+z),-z,-y,t+(y+z))$.
Autrement dit, si le cercle initial consiste en $n$ nombres $x_1,\ldots,x_n$, soient $f(x_1,\ldots,x_n)=(x_1+x_2,x_3,\ldots,x_n)$, alors $f$ entrelace respectivement $T_1\circ T_2\circ T_1,T_3,\ldots,T_n$ et $T_1,\ldots,T_{n-1}$.
Par récurrence, on se ramène donc à $(x_1,\ldots,x_n)$ avec $x_1+x_2\ge 0$ et $x_3,\ldots,x_n\ge 0$.
Si $x_1,x_2\ge 0$ c'est gagné. Sinon, supposons par exemple $x_2<0$. On peut transformer successivement en $(x_1+x_2,-x_2,x_2+x_3,x_4,\ldots)$ jusqu'à $(x_1+x_2,x_3,x_4,\ldots,x_{n-1},-(x_2+\cdots,x_{n-1}),x_2+\cdots+x_n)$. Si l'un de ces transformés a tous ses termes $\ge 0$ c'est fini, sinon on transforme en $(x_2+s,x_3,\ldots,x_n,-(x_2+\cdots+x_n))$ et on se retrouve avec $(x'_1,\ldots,x'_n)$ où $x'_1+x'_2\ge 0$, $x'_3,\ldots,x'_n\ge 0$, $x'_1\ge 0$ et $x'_2=x_2+s$. En recommançant un nombre fini de fois on y arrive.
Pour l'unicité je n'ai strictement aucune idée.
On le retrouve parfois dans la littérature sous le nom de «jeu du pentagone» (cas n=5) ou «jeux de nombres».
On peut non seulement regarder ce jeux sur un cercle, mais le résultat reste vrai sur n'importe quel graphe de Coxeter fini.
De plus, il y a non seulement unicité de la configuration finale, mais aussi du nombre de mouvement nécessaire pour y arriver si on ne s'autorise à ne tirer que des sommets négatifs.
Plus précisément :
Soit \(\Gamma\) un graphe de Coxeter de matrice de Coxeter \(M\) et de groupe de Coxeter \(W\) et soit \(S\) l'ensemble des sommets de \(\Gamma\).
Soit \(p=(p(s))_{s\inS})\) une configuration sur \(\Gamma\) (i.e. un ensemble de poids réels).
On regarde le jeux suivant :
Un pas du jeux consiste à choisir un sommet \(s\), à changer sa valeur de \(p(s)\) à \(-p(s)\) et pour tout les sommets \(s'\) qui lui sont adjacent, changer leur valeurs de \(p(s')\) à \(p(s')+2\cos(\frac{\pi}{m(s,s')})\).
On a alors le théorème suivant :
Si les seuls pas autorisés sont ceux où \(p(s)\) est strictement négatif, alors le jeux se terminera (arrivera à une configuration \(\geq 0\) si et seulement si la configuration initial appartient au cône de Tits de \(W\), \(U\).
De plus, si la configuration initiale appartient à \(U\), alors la configuration final ainsi que le nombre de pas nécessaire pour y arriver ne dépend que de la configuration initiale.
Ca n'en montre pas moins que (encore que là JLT semble avoir pu tirer un bon coup franc) parfois on a des résultats où aucune récurrence ne donne d'amélioration, il semble qu'il faille passer par d'autres phénomènes (eux peuvent se prouver par récurrence) pour pouver le truc. (Là je pense surtout à l'unicité)
Et pourtant: l'élimination des coupures (théorème de logique) suggère que ce problème devrait avoir une solution "bête" c'est à dire prouvable juste à l'aide des hypothèses faites, des données, par passage du général au particulier. Mais "suggère" seulement, car il y a les nombres réels, etc, dans l'histoire
Soit $S$= somme de tout les nombres autour du cercle. On a déjà remarqué que c'était un invariant.
A une configuration donnée c'est-à-dire 100 nombres réels écris autour d'un cercle on associe tout le multiensemble de toutes les sommes sur tout les arcs de cercle.
C'est-à-dire que si les éléments autour du cercle sont dans l'ordre les $x_i$ avec $i\in\mathbb{Z}/100\mathbb{Z}$ on considère le multiensemble dont les éléments sont les $\displaystyle\sum_{k=0}^N x_{i+k}$ avec $i\in\mathbb{Z}/100\mathbb{Z}$ et $N\in\{0,\ldots,99\}$.
Si on applique l'algorithme suivant: à chaque fois que tout les nombres autour du cercle ne sont pas positifs on choisit le nombre le plus négatif $y$ et on applique la transformation à lui et ses deux voisins.
On a alors juste changé les deux éléments $y$ et $S-y$ du multiensemble en $-y$ $S+y$. On vérifie alors les deux faits suivants:
-La somme de tout les éléments du multiensemble qui sont négatifs a augmentée strictement.
-Modulo S le multiensemble n'a pas bougé.
De ces deux remarques on déduit assez facilement qu'au bout d'un nombre fini de coups on aura que des nombres positifs mais aussi qu'on connaît le multiensemble qui sera associé à cette configuration: c'est le multiensemble des restes modulo S des éléments du multiensemble de départ. (Le reste modulo $x>0$ d'un réel $y$ est le seul réel $r\in[0,x[$ tel que $y-r\in\mathbb{Z}x$).
Par contre je n'ai pas encore réussi à montrer que le multiensemble associé à la configuration finale détermine les nombres qui y apparaissent.
concernant l'unicité, une idée : je suppose les xi positifs ou nuls (éléments d'un groupe commutatif ordonné quelconque). Soit s une permutation de [1,100] telle que la suite des xs(i) soit croissante, sommes partielles de la suite de termes positifs ou nuls (ai). Ainsi, le problème se transpose dans Z100 à partir des éléments
(1,0,0,0,...)
(1,1,0,0,...)
(1,1,1,0,...)
(1,1,1,1,...)
dans un ordre quelconque.
Il semblerait qu'au fil des opérations, les coordonnées des éléments restent toujours soit positives, soit négatives, et qu'elles restent décroissantes en valeur absolues. Si cela était vérifié, il en résulterait aisément l'unicité.
Pour conclure le week-end, voici la solution qui devrait figurer dans le prochain numéro de "Diagonales" :
pour tout nombre entier $i$ entre 0 et 99, l'opération sur $x_{r(i-1)}, x_i, x_{r(i+1)}$ se traduit par l'échange de $y_{j-1}$ et $y_j$ pour tout nombre entier $j$ tel que $r(j) = i$.