Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
Résumé de la discussion (messages les plus récents en premier)
- freddy
- 28-09-2011 17:40:40
Re,
J'ai vu que vous aviez modifié la définition d'un état consistant : crochets doubles ouverts et non plus fermés
Ne devrait-il pas aussi y avoir s < t (et non plus inférieur ou égal) car un seul 0 entre des valeurs positives n'est pas inconsistant alors que 2 zéros consécutifs le sont ?Cordialement
Re,
oui, mais l'inégalité large ne mange pas de pain.
- freddy
- 28-09-2011 17:39:20
Bonsoir,
J'ai repris avec attention votre démonstration formelle que je trouve très bonne.
J'ai quand même un petit probème de compréhension sur ces notations :freddy a écrit :En effet, puisque l'état terminal est consistant, on a alors deux possibliités et deux seulement :
soit [tex]E_1^* = [\![\cdots,0,0,0,1,1,1,1,\cdots,1,1,1,0,0,0,\cdots]\!][/tex]
soit [tex]E_2^* = [\![\cdots, 0,0,1,1,1,1,0,1,1,1,1,1,0,0,\cdots]\!][/tex]
Des zéros me semblent en trop pour ne pas avoir d'états inconsistants... Il ne devrait y avoir qu'un seul 0 dans les deux cas ?
Pouvez-vous éclairer cette remarque bénigne ?Cordialement
Salut,
non, c'est simplement pour dire que ça se prolonge à droite et à gauche par une suite infinie de 0.
- totomm
- 28-09-2011 00:43:44
Re,
J'ai vu que vous aviez modifié la définition d'un Etat consistant : crochets doubles ouverts et non plus fermés
Ne devrait-il pas aussi y avoir s < t (et non plus inférieur ou égal) car un seul 0 entre des valeurs positives n'est pas inconsistant alors que 2 zéros consécutifs le sont ?
Cordialement
- totomm
- 27-09-2011 19:37:39
Bonsoir,
J'ai repris avec attention votre démonstration formelle que je trouve très bonne.
J'ai quand même un petit probème de compréhension sur ces notations :
En effet, puisque l'état terminal est consistant, on a alors deux possibliités et deux seulement :
soit [tex]E_1^* = [\![\cdots,0,0,0,1,1,1,1,\cdots,1,1,1,0,0,0,\cdots]\!][/tex]
soit [tex]E_2^* = [\![\cdots, 0,0,1,1,1,1,0,1,1,1,1,1,0,0,\cdots]\!][/tex]
Des zéros me semblent en trop pour ne pas avoir d'états inconsistants... Il ne devrait y avoir qu'un seul 0 dans les deux cas ?
Pouvez-vous éclairer cette remarque bénigne ?
Cordialement
- freddy
- 27-09-2011 19:12:47
Re,
on va s'attacher à montrer que [tex]\rho[/tex] est à valeur dans [tex]R_{+}[/tex]
Tout d'abord, supposons que [tex]a=b[/tex]. Donc nous nous trouvons au début du jeu et donc [tex] p=0[/tex].
Or [tex]\rho(0)=x_0=2n > 0[/tex], donc [tex]\rho(0) > 0[/tex]
Supposons maintenant que [tex]a < b[/tex] et considérons [tex] p \ge a+1[/tex].
On a la différence suivante : [tex]\rho(p)-\rho(p-1) = x_p-1 \ge -1[/tex]
Par conséquent, [tex]\rho(p) \ge \rho(p-1) -1[/tex] avec une égalité ssi [tex]x_p=0[/tex]
En particulier, on sait que [tex] \rho(a) \ge 1[/tex] par définition du support donc [tex]\rho(a+1) \ge \rho(a) - 1 \ge 0[/tex]
On est toujours dans le cas où [tex]a < b[/tex] et on suppose maintenant que [tex]p \ge a+2[/tex].
Pour démontrer le résultat du texte, on va raisonner par l'absurde en supposons qu'il est faux.
Désignons par [tex]k \ge a+2[/tex] le plus petit indice tel que [tex]\rho(k) <0[/tex].
Ce qui veut dire en particulier et par hypothèse que [tex] \rho(k-1) \ge 0[/tex]
On sait qu'on a les inégalités suivantes : [tex]0 > \rho(k) \ge \rho(k-1) - 1 \ge -1[/tex]
On déduit immédiatement que [tex] \rho(k) = -1[/tex] puisque les[tex] x_p[/tex] sont nécessairement des entiers.
Par suite, on déduit que [tex] \rho(k-1) = 0[/tex] et que [tex]x_k = 0[/tex] comme signalé plus haut.
Considérons alors [tex]m[/tex] le plus grand indice de l'intervalle[tex] [\![a,k]\!][/tex] tel que [tex]\rho(m) > 0[/tex]
Un tel indice existe puisque [tex]\rho(a) > 0[/tex] et on sait qu'on a [tex]\rho(j) >0[/tex] et [tex]\rho(j+1) \le 0[/tex]
On montre aisément que :
1) [tex]j[/tex] est différent de [tex] k[/tex] puisque [tex]\rho(k) = -1[/tex] ;
2) [tex]j[/tex] est différent de [tex] k- 1[/tex] puisque [tex]\rho(k-1) = 0[/tex] ;
On en déduit que [tex]j < k-1[/tex]
Par définition de [tex]k[/tex], [tex]j +1< k \Rightarrow \rho(j+1) \ge 0[/tex] et donc [tex]\rho(j+1)=0[/tex] ce qui implique que [tex]\rho(j) \le 1[/tex] et donc que [tex]\rho(j)=1[/tex] par hypothèse sur [tex]j[/tex]. On en déduit finalement que [tex]x_{j+1}=0[/tex]
Considérons le tableau ci après :
\begin{array}{c|c|c|} \rm i & \rm a & \rm a+1 & \rm \cdots & \rm j & \rm j+1 & \rm \cdots & \rm k-1 & \rm k \\ \hline x_i & x_a & & & x_j & x_{j+1} & & x_{k-1} & x_k \\ \hline \rho(i) & \ge 1 & \ge 0 & \ge 0 & 1 & 0 & 0 & 0 & -1 \end{array}
Par définition de j et de k, [tex] \forall\, i \in ]\!]j,k[\![,\; \rho(i) = 0 [/tex].
Donc puisque [tex]0 = \rho(j+2)-\rho(j+1)=x_{j+2}-1[/tex] alors [tex]x_{j+2}=1[/tex]
De la même manière, on déduit que [tex]x_{j+3}=1,\;x_{j+4}=1,\; \cdots,\;x_{k-1}=1[/tex]
On aurait alors le tableau ci-dessous :
\begin{array}{c|c|} \rm a & \rm \cdots & \rm j & \rm j+1 & \rm j+2 & \rm \cdots & \rm k-1 & \rm k & \rm \cdots & \rm b \\ \hline x_a & & x_j & 0 & 1 & 1\, 1\, 1\,& 1 &0 & & x_b \end{array}
On voit immédiatement que l'hypothèse implique que l'état E est inconsistant.
Q. E. D
- freddy
- 27-09-2011 17:26:00
Bonsoir,
on va montrer que si l'état [tex]F = T_p(E)[/tex] est inconsistant, alors E l'est aussi.
par définition, cela signifie qu'il existe dans l'état F une sous séquence de la forme [tex]0,1,1,1,\cdots,1,1,1,0[/tex]
A une symétrie près, on a trois cas possibles selon la valeur de l'indice p :
p
E [tex] ---,0, 1,1, \cdots, 1,1,0, ---[/tex]
F [tex] ---,0, 1,1, \cdots, 1,1,0, ---[/tex]
p
E [tex] ---,2, 0,1, \cdots, 1,1,0, ---[/tex]
F [tex] ---,0, 1,1, \cdots, 1,1,0, ---[/tex]
p
E [tex] ---,0, 1,0, 3,0, 1,\cdots,1,1,0 ---[/tex]
F [tex] ---,0, 1,1,1,1, 1,\cdots,1,1,0 ---[/tex]
On vérifie ainsi que l'inconsistance de F provient de celle de E.
Donc par contraposition, si E est consistant,[tex] F=T_p(E)[/tex] l'est aussi !
- totomm
- 27-09-2011 07:36:28
Bonjour,
Je n'ai pas la pratique des exposés mathématiques formalisés tout en pouvant les suivre.
Merci donc à freddy d'avoir publié le sien, même encore incomplet, c'est pour moi un bon exemple.
Voici ce sur quoi je m'étais reposé en langage ordinaire au post #9
Préliminaires : On peut montrer que l'ordre dans lequel s'effectuent les répartitions de 2 coquillages vers les positions voisines n'influe pas sur la situation finale (ce point n'est pas démontré ici, mais ce n'est pas difficile).
Soit i une position à partir de laquelle 2 coquillages vont être répartis, ayant a, b, c coquillages respectivement en i-1, i, i+1.
Si on considère S0 = a(i-1)²+bi²+c(i+1)² = i²(a+b+c)+2i(c-a)+(a+c).
Après répartition on obtient
S1 = (a+1)(i-1)²+(b-2)i²+(c+1)(i+1) = i²(a+1+b-2+c+1)+2i(c+1-(a+1)+(a+1+c+1).
Soit S1-S0=2 indépendant de i, d'où la suite du post #9 pour démontrer une récurrence sur la somme des carrés en exploitant la symétrie initiale.
La démo de freddy est bien meilleure, mais la mienne, succincte et intuitive, suffisait à asseoir mon propos.
Note : J'ai pensé aux moments d'inertie (masses mécaniques) plus qu'à des répartitions de probabilités pour la tendance à l'étalement des coquillages
Cordialement
- freddy
- 26-09-2011 17:12:47
Re,
oui pour les deux premiers, non pour le dernier à cause de 0,1,0.
Sous toute réserve !
Pour bien le vérifier, le résultat R1 donne un moyen simple de le faire. En attendant que j'en donne la preuve, sers t'en, je te prie.
[EDIT]
Grâce à la fonction [tex]\rho[/tex], je confirme mes dires.
- totomm
- 26-09-2011 14:28:26
Bonjour
On dit qu'un état E est consistant si son support ne contient aucun sous-intervalle[tex][\![s,t]\!][/tex] tel que :
- [tex]s \le t[/tex]
- [tex]x_s = 0[/tex]
- [tex]x_t = 0[/tex]
- [tex]\forall p \in [\![s,t]\!],\;x_p =1[/tex]
Question de compréhension indépendante de ce qui reste encore à définir dans la démo de freddy :
Les 3 états suivants sont-ils consistants ? (Les crochets [ et ] sont des 0 à gauche et à droite)
[1,1,1,1,1,1,1,0,1,2,0,1,1,2,1,0,1,1,1,1,1]
[1,1,1,1,1,1,1,0,1,2,0,1,2,0,2,0,1,1,1,1,1]
[1,1,1,1,1,1,1,0,1,2,0,1,2,0,1,0,1,1,1,1,2]
- freddy
- 25-09-2011 23:13:21
Bonsoir,
Pourrait-on avoir la référence de la démonstration complète ? Car le texte adapté et simplifié par freddy (post #16) manque de conclusions en l'état.
En particulier sur des questions de base :
Intuitivement le support ne peut que s'élargir, mais l'état terminal existe-t-il si le support est fermé en cercle ?
Dans l'état terminal, où se trouve la position vide par rapport à celle qui a reçu la dotation initiale ?
L'état terminal est-il atteint au terme du même nombre d'étapes si les états intermédiaires diffèrent ?Note : pour la compréhension du texte il faut remplacer 2 fois m0(E) par m1(E) et m2(E)
Cordialement.
Salut,
la mention (...) signifie que le travail n'est pas achevé. C'est un peu comme le "to be continued ..." des célèbres séries TV US ou AUS.
Sinon, la correction a été faite, mais donne moi un peu le temps de relire stp.
- totomm
- 25-09-2011 19:43:17
Bonsoir,
Pourrait-on avoir la référence de la démonstration complète ? Car le texte adapté et simplifié par freddy (post #16) manque de conclusions en l'état.
En particulier sur des questions de base :
Intuitivement le support ne peut que s'élargir, mais l'état terminal existe-t-il si le support est fermé en cercle ?
Dans l'état terminal, où se trouve la position vide par rapport à celle qui a reçu la dotation initiale ?
L'état terminal est-il atteint au terme du même nombre d'étapes si les états intermédiaires diffèrent ?
Note : pour la compréhension du texte il faut remplacer 2 fois m0(E) par m1(E) et m2(E)
Cordialement.
- karlun
- 25-09-2011 11:42:26
Bonjour,
j'ai tenté de démonter le mécanisme de distribution.
Mathamateur (+-*/) je ne peux que vous présenter les pièces démontées et les relations qui les animent.
Je me suis intéressé aux passages de p places à (p+2) places (en symétrie) en respectant le processus stochastique et j'aboutis à un ordonnancement qui me conduit au résultat annoncé (385).
Passons d' une place (possédant un nombre paire de coquillage (2)) à deux places:
2 étape 0 p=1
1 0 1 étape 1 p=3 1*
Il faut 1 étape.
Passons de 3 places dont la centrale possède un nombre paire de coquillage (2) à 5 places:
1 2 1 étape 0 p=3 2*
2 0 2 étape 1
1 0 1 2 étape 2
1 0 2 0 1 étape 3 p=5
et alors 1*
1 1 0 1 1 étape 1
Donc quelque soit l'ordre de décomposition des paires de coquillages,
pour passer de 1 à 3 places il faut : 1 étape
pour passer de 3 à 5 places il faut : 1 + 3 étapes
pour passer de 1 à 5 places il faut: 2 + 3 étapes
Passons de 5 places dont la centrale possède un nombre paire de coquillage (2) à 7 places:
1 1 2 1 1 étape 0 p=5
1 2 0 2 1 étape 1
2 0 1 2 1 étape 2
2 0 2 0 2 étape 3
1 0 1 2 0 2 étape 4
1 0 1 2 1 0 1 étape 5 p=7 3*
Et alors 2*
Soit conquérir la place n°2 et n°6 et donc revenir sur 2*
Et ensuite 1*
Donc
pour passer de 1 à 3 places il faut : 1 étape
pour passer de 3 à 5 places il faut : 1 + 3 étapes
pour passer de 5 à 7 places il faut : 1 + 3 + 5 étapes
pour passer de 1 à 7 places il faut: 3 + 6 + 5 étapes
Pour passer de 1 à 21 places il faut:
1 3 5 7 9 11 13 15 17 19
1 3 5 7 9 11 13 15 17
1 3 5 7 9 11 13 15
1 3 5 7 9 11 13
1 3 5 7 9 11
1 3 5 7 9
1 3 5 7
1 3 5
1 3
1
10 27 40 49 54 55 52 45 34 19
total= 385.
Notons que pour alimenter toutes la procédure il faudra prévoir au minimum 10*2 coquillages.
Voilà c'est un peu comme une épure je sais et la dimension "hasard" n'est pas prise en compte.
A+-*/
- freddy
- 25-09-2011 11:26:20
Hello tutti,
ci dessous la démonstration du résultat. J'ai repris et adapté celle du concepteur du sujet, à tout seigneur, tout honneur.
De la même manière que dans mon code, on va définir une notion qui va servir tout le long.
On définit un état [tex]E = \{x_p \in N,\;p \in Z\}[/tex]. L'indice p est la position relative du participant par rapport à celui qui reçoit la dotation initiale, soit [tex]x_0=2\times n,[/tex] et [tex]x_p[/tex] est le nombre de coquillage qu'il possède.
Le jeu continuant tant qu'il existe un indice p tel que [tex]x_p \ge 2[/tex], on peut définir l'état terminal [tex]E^*[/tex] comme celui où il n'existe aucun indice p tel que [tex]x_p \ge 2[/tex].
Continuons par définir l'intervalle borné d'entiers relatifs [tex]S_E=[\![a,b]\!][/tex] tel que :
- [tex]a \le b[/tex]
- [tex]x_a > 0[/tex]
- [tex]x_b > 0[/tex]
- [tex]\forall p \notin S_E[a,b],\;x_p =0[/tex]
Par assimilation aux notions de la théorie des probabilité, on voit que [tex]S_E[a,b][/tex] est en quelque sorte le support de l'état E.
Ainsi, après la première étape, on a [tex]S_E=[\![-1,1]\!][/tex], idem pour la troisième. C'est après que ça swingue !
On dit qu'un état E est consistant si son support ne contient aucun sous-intervalle[tex][\![s,t]\!][/tex] tel que :
- [tex]s \le t[/tex]
- [tex]x_s = 0[/tex]
- [tex]x_t = 0[/tex]
- [tex]\forall p \in ]\!]s,t[\![,\;x_p =1[/tex]
En clair, il n'y a pas de "trou noir" isolant un sous groupe de participants au reste de la table.
A l'instar des moments non centrés d'une distribution, définissons les trois fonctions réelles d'un état E :
- [tex]m_0(E)=\sum_{p \in Z} x_p[/tex]
- [tex]m_1(E)=\sum_{p \in Z} p\times x_p[/tex]
- [tex]m_2(E)=\sum_{p \in Z} p^2\times x_p[/tex]
On appelle [tex]T_p[/tex] l'opérateur défini sur l'espace des états et à valeurs dans l'espace des états, qui transforme E en F tel que le participant p a été choisi et a dû donner un coquillage à ses deux voisins immédiats.
On sait que l'opérateur existe si [tex]x_p \ge 2[/tex].
On a les résultats suivants :
1) [tex]m_0(E) = m_0\left(T_p(E)\right) = 2\times n[/tex] => invariance de la dotation initiale.
2) si [tex]T_p[/tex] existe, alors [tex]m_1\left(T_p(E)-m_1(E)\right) = (p-1)-2p+(p+1) =0[/tex] => pour tout état E, [tex]m_1(E)=0[/tex].
3) si [tex]T_p[/tex] existe, alors [tex]m_2\left(T_p(E)-m_2(E)\right) = (p-1)^2-2p^2+(p+1)^2 =2[/tex] => pour tout état E, [tex]m_2\left(T_p(E)\right)[/tex] augmente de 2 à chaque transformation.
Conclusion, le processus a pour effet d'augmenter de 2 la valeur de la mesure [tex]m_2[/tex] de E.
Montrons maintenant un résultat très intuitif : le support ne peut que s'élargir.
En effet, considérons [tex]S_E=[\![a,b]\!][/tex] et [tex]S\left(T_p(E)\right)=[\![a',b']\!][/tex].
Alors soit [tex]a<p<b[/tex] et donc [tex]a=a'[/tex] et [tex]b=b[/tex]',
soit [tex]p=a[/tex] et donc [tex]a' <a[/tex] et [tex]b=b'[/tex],
ou bien [tex]p=b[/tex] et donc [tex]a'=a[/tex] et [tex]b<b[/tex]'.
Donc pour tout état E, si [tex] T_p[/tex] existe alors [tex] S_E \subseteq S\left(T_p(E)\right)[/tex].
Définissons enfin la valuation de l'état E par la fonction réelle [tex]\rho[/tex] telle que :
[tex]\forall p \in S_E, \; \rho(E)=\sum_{i=a}^p x_i-(p-a)[/tex]
alors on a le résultat suivant :
si E est un état consistant, alors [tex]\forall p \in S_E, \; \rho(E) \ge 0[/tex] [R1]
Proof
La preuve est assez longue, quoique pas difficile, à établir. On la postera plus tard, et on se sert de ce résultat pour arriver au suivant :
si E est un état consistant de support [tex][\![a,b]\!][/tex], alors [tex]b-a=\sum_{i=a}^b x_i \le 2n[/tex] [R2]
Pour généraliser à tous les états issues des transformations [tex]T_p[/tex] quand elles existent, il suffit de montrer que si l'état E est consistant, alors[tex] F=T_p(E)[/tex] est aussi consistant.
On apportera la preuve de ce résultat plus tard, par contraposition.
On en déduit que, puisque l'état initial est consistant, alors tous les états suivants le sont aussi et l'amplitude de leur support est majorée par la dotation initiale [tex]2n[/tex].
Puisque on a montré plus haut que le support de chaque état ne peut que "s'élargir", on en déduit qu'il existe un nombre maximal d'opérations permettant à aboutir à l'état terminal [tex]E^*[/tex] de support [tex][\![\alpha,\omega]\!][/tex].
La dernière étape consiste à voir comment s'écrit l'état terminal [tex]E^*[/tex]. On montre qu'il ne peut s'écrire que d'une seule manière.
En effet, puisque l'état terminal est consistant, on a alors deux possibliités et deux seulement :
soit [tex]E_1^* = [\![\cdots,0,0,0,1,1,1,1,\cdots,1,1,1,0,0,0,\cdots]\!][/tex] avec un bloc de 1 ;
soit [tex]E_2^* = [\![\cdots, 0,0,1,1,1,1,0,1,1,1,1,1,0,0,\cdots]\!][/tex] avec un bloc de 1 interrompu une seule fois par un 0 pour des raisons de consistance.
Le premier état n'existe pas car sinon [tex]m_1(E_1^* )=0[/tex] donc [tex]\alpha=-\omega[/tex] donc [tex]m_0(E_1^* )=2n=2\omega-1[/tex] ce qui aboutit à une impossibilité (un nombre pair serait égal à un nombre impair).
Seul le second état existe. On en déduit que [tex]\omega = -\alpha=n[/tex] et par suite :
[tex]m_2(E_2^* )=2\times \frac{n(n+1)(2n+1)}{6}[/tex]
Récapitulons : chaque tirage augmente [tex]m_2(E)[/tex] de +2 et au départ, [tex]m_0(E) = 0[/tex], donc on en déduit que le nombre exact de transformations nécesssaires pour arriver à l'unique état terminal
[tex]E^*=\{1,1,1,\cdots,1,1,0,1,1,\cdots,1,1,1\}[/tex] est [tex]\frac{n(n+1)(2n+1)}{6}[/tex]
Ce qui signifie en particulier que l'unique état immédiatement précédent est de la forme :
[tex]E^*=\{1,1,1,\cdots,1,1,0,2,0,1,1,\cdots,1,1,1\}[/tex].
Si maintenant on pose n = 10, on voit que le messe est dite en 385 étapes, et qu'à la 384 ième étape, on avait la séquence [tex]\{1,1,1,1,1,1,1,1,1,0,2,0,1,1,1,1,1,1,1,1,1\}[/tex], d'où la réponse du texte.
PS : je félicite Fred et Yoshi pour la grande qualité de la mue du forum !
- freddy
- 23-09-2011 16:51:06
Salut,
j'ai joint mon code dans la rubrique "programmation".
Comme je disais, on voit bien comment les 20 coquillages se diffusent vers les autres joueurs.
On comprend que le jeu s'arrête dès que chaque joueur a au plus 1 coquillage.
On conçoit que cette situation est possible, mais on ne sait si ni quand elle peut se produire, à cause du processus stochastique sous jacent.
Et pourtant, on montre qu'en réalité, elle se réalise effectivement au bout de 385 étapes, et donc qu'à l'étape immédiatement précédente, il n'y a plus qu'une seule personne qui a deux coquillages en main, et ses deux voisins/voisines 0.
La démonstration s'inspire d'ailleurs des observations que l'on peut faire de la réalisation progressive des étapes.
A suivre ...
- totomm
- 16-09-2011 16:11:44
Bonjour,
Préliminaires : On peut montrer que l'ordre dans lequel s'effectuent les répartitions de 2 coquillages vers les positions voisines n'influe pas sur la situation finale
Chacun peut s'en persuader et le démontrer formellement
Chacun peut donc choisir un déroulement dans l'ordre qui convient à sa démonstration
12 à 6 heures, 4 à gauche et 4 à droite : Que ce soit cette situation de départ ou 20 à 6 heures, la situation finale (étape 385) sera la même !
Cordialement