Voisins / Voisines

freddy · 13-09-2011 22:47:40

Salute a tutti,

problème pioché sur la toile et grand respect à son concepteur (arrière petit fils d'un célèbre animateur TV ...)

Vingt et une personnes, dont Paul et Virginie, du club Med' de Peysey Nancroix, sont assises autour d'une table circulaire pour participer à un jeu "step by step".

Une étape consiste à choisir au hasard une personne qui a au moins deux coquillages ; celle-ci doit alors donner un coquillage à chacun de ses deux voisins (voisines).

Au départ du jeu, une personne a 20 coquillages, les autres n'ont rien.

A l'issue de 384 étapes, Virginie a deux coquillages de plus que Paul.

Combien ont ils respectivement ?

totomm · 14-09-2011 02:44:42

Bonjour,

certainement 2 et 0, et ensuite chacun(e) aura 1 coquillage sauf un(e).

Cordialement

freddy · 14-09-2011 10:25:45

Salut tomtom

Ah, trop fort le tomtom, trop fort, mais es tu sûr de ton résultat ?

Peux tu le prouver ? C'est important de le prouver, sinon, il y a toujours un doute, et la rigueur commande de ne laisser aucun doute planer.

Allez, on you my dear !

totomm · 14-09-2011 12:08:31

Bonjour,

Assez d'humour friddyesque, j'ai au moins 3 façons d'arriver au résultat ! (je peux les envoyer par Courriel avant de les publier sur ce Forum si vous aviez un doute)
Mais laissons le plaisir de trouver à d'autres internautes....

Cordialement

freddy · 14-09-2011 13:28:25

Re,

OK par MP pour les 3 façons, j'ai une adresse e mail à laquelle tu peux m'écrire. Je serai sans complaisance.

Promis, je laisserai les autres réfléchir !

Salut !

Dernière modification par freddy (14-09-2011 13:28:46)

totomm · 14-09-2011 15:23:10

re, Courriel envoyé à Freddy qui pourra le publier à son gré.

jpp · 14-09-2011 19:03:00

Bonsoir.

si Paul possède ces 20 coquilles et qu'il se situe à 6 h autour de la table. il va distribuer ses coquilles
2 par 2 ( une à gauche et une à droite ) alors 10 partent dans le sens horaire ou rétrograde et 10 dans le sens
trigo ou sens direct.
après c'est comme une vague qui perd de son amplitude au fur et à mesure que les coquilles sont distribuées.
car le voisin de gauche de paul ne pourra pas se débarasser de son dernier coquillage comme son voisin de gauche ;
d'ailleurs , ayant toujours un nombre pair de coquilles il s'en débarassera toujours une à gauche une à droite.
meme sort pour le second voisin de gauche et le second voisin de droite. ainsi de suite..
aussi, comme ils sont 21 ils sont donc 2 à midi . il y a sans doute Virginie qui a effectué l'avant dernier échange
son voisin en avait 3, le veinard , et en derner échange il en a donné une à sa voisine qui en possède 2 et une à son autre voisin qui lui n'avait rien ( le pauvre) il doit y en avoir un autre aussi qui a les mains vides.
en conséquence 18 avec une coquille , un avec 2 coquilles et 2 sans rien. car il y a un nombre pair d'échanges.
quant à 384 échanges je ne vois pas . c'est presqu'un nombre pyramidal moins un.

On se demande quand meme qui porte la culotte.

à plus.

Dernière modification par jpp (14-09-2011 19:33:38)

freddy · 15-09-2011 10:48:27

Salut les gars,

j'ai bien reçu les trois idées de démo de tomtom, sauf que je ne considère pas la preuve par python comme acceptable, comme d'hab.

Quant aux deux autres, c'est du ressort de "j'ai l'intuition que c'est comme ça", mais il faut ensuite le démontrer. J'ai bien aimé la suite S(n), et si l'ami tomtom pouvait développer ici, je lui ensaurais gré.

Certes, on subodore bien que c'est comme vous dites, mais il faut le démontrer rigoureusement.

C'est tout l'art du mathématicien qui ne peut en faire l'économie car le diable peut parfois se cacher dans le détail qui fout tout par terre.

La preuve ? Prenons pas exemple la somme de la série de terme général 1/n. L'intuition suggère fortement que la série est convergente, donc que la somme existe, et on démontre pourtant que non.

Convaincus ? j'ai d'autres exemples dans mon sac si vous le souhaitez.

On you !

Dernière modification par freddy (15-09-2011 10:59:11)

totomm · 16-09-2011 00:37:02

Bonjour,

"l'intuition que c'est comme ça", c'est l'utilisation implicite des connaissances pour voir les implications du problème et comment s'orienter vers une solution...

Je n'ai jamais dit "j'ai l'intuition que..." sans avoir une bonne vision d'une démonstration.

Voici donc, sur invite de freddy qui ne manquera pas de publier une version plus "formalisée", ce que mon intuition m'avait laissé entrevoir :

Soit D(n) une position de départ comportant (2n+1) positions contiguës notées de –n à +n avec 2n coquillages en position 0.
Soit S(k) une situation où les positions de -k à -1 et de 1 à k sont garnies de 1 seul coquillage et où restent 2(n-k) coquillages en position 0.
La règle veut que 2 coquillages en position i soient distribués en positions (i-1) et (i+1)

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).
Ainsi on peut raisonner sur le nombre d'étapes nécessaires pour évoluer de D(n) vers les S(k), k variant de 1 à n. On notera E(k) le nombre d'étapes pour passer de S(k-1) à S(k).
Vu la symétrie, on ne considérera que les positions 0 et positives, et on comptera 1 étape quand 2 coquillages seront répartis depuis la position 0, et 2 étapes ils le seront depuis les positions 1 à (n-1).
Le bouclage circulaire de n vers –n ne sera jamais utilisé.

De D(n) vers S(1) : E(1) = 1 étape de façon évidente ( D(n) est assimilé à S(0) )

De S(1) vers S(2) : il faut 1 étape pour avoir 2 coquillages en position 1, puis 1 étape (qui compte double) pour avoir 0 coquillage en position 1 et 1 coquillage en position 2. il suffit alors d'une étape pour passer un coquillage de la position 0 vers la position 1.
D'où E(2) =1+2+1=4= 2²
…..
De S(k-1) vers S(k) pour 2<k<=n : il faut k étapes, dont (k-1) comptées doubles pour apporter 1 coquillage en position k, 0 coquillage en (k-1) et 1 coquillage des positions 1 à (k-2),
Soit k+(k-1) = 2k-1 étapes pour avoir 1 coquillage en position k et 0 coquillage en (k-1).
Ensuite, pour i décroissant de (k-1) à 1, on doit refaire les étapes pour apporter 1 coquillage en position i, soit successivement 2(k-1)-1, ….., 2x2-1=3, 1.

Ainsi E(k) = Somme des k premiers nombres impairs = k²
On en déduit la récurrence : S(n) = somme des n premiers carrés = n(n+1)(2n+1)/6
S(10) = 10x11x21/6 = 5x11x7 = 35x11 =385
Après S(10)-1 = 384 étapes Virginie en position 0 a 2 coquillages, et Paul en a 0 en position 1

Cordialement

yoshi · 16-09-2011 08:54:52

Bonjour,

Une fois n'est pas coutume, je suis en désaccord avec freddy, je trouve que là, a priori, il pousse le "purisme" à l'extrême :

(...) sauf que je ne considère pas la preuve par python comme acceptable, comme d'hab.

Il se trouve que lors de notre débat sur les démos via ordinateur, j'avais envisagé ce cas.
Nous nous trouvons ici dans une situation parfaitement dénombrable :

A l'issue de 384 étapes, Virginie a deux coquillages de plus que Paul.

IL y a 2 façons de faire une démonstration "calculatoire" :
* Soit on fait une démonstration générale,
* Soit on étudie tous les cas sans exception.
Ainsi, on voit vite que la 2e méthode est inenvisageable si on veut qu'elle puisse être générique...

Mais dans le cas présent, si par son programme Python, totomm a réussi à faire un tour exhaustif de la question, sa "démonstration" est recevable pour le cas soumis : 384 étapes et ce cas seulement.
J'avais dit que bien, une démo via programmation n'était envisageable qui si elle ne faisait que reproduire ce qu'aurait pu faire plus lentement, avec beaucoup plus de corrections de petites fautes de calcul, à la main, un matheux ou une équipe de matheux....

Maintenant pour juger véritablement, il faudrait voir ce programme Python, et voir s'il fait bien le tour de de la question en 384 étapes...

Et pour moi, l'intuition, c'est le flair du matheux, c'est la capacité de son subconscient à établir des connexions supplémentaires, des rapprochements entre des données stockées quelque part dans notre "boîte à idées" sans directives précises conscientes donc...
L'intuition, c'est fondamental ; sans intuition, le matheux ou le programmeur n'iront pas bien loin...

@+

totomm · 16-09-2011 10:52:57

Bonjour,

le code de mon programme est dans le sous-forum "Programmation"
ainsi que des commentaires sur le code des 32 5-combinaisons sélectionnant les 220 3-combinaisons. (même freddy peut lire ces commentaires)

Cordialement

jpp · 16-09-2011 13:04:10

Salut à tous.

en gardant la meme stratégie . c'est l'histoire du moniteur de colonie de vacances qui part en pique-nique
avec ses momes. c'est le moment du quatre heures.
il a le premier jour 2 momes avec lui. et 2 oranges . ils s'assoient tous les 3 sur un banc , lui au milieu.
il a les oranges dans la main. 0 - 2 - 0 de chaque coté 1 mome
premier transfert 1 - 0 - 1 premier transfert et c'est fini
- le 2ème jour il a 4 momes 0 - 0 - 4 - 0 - 0
premier transfert 0 - 1 - 2 - 1 - 0
second transfert 0 - 2 -0 - 2 - 0
troisième transfert 1 - 0 -1 - 2 - 0
quatrième transfert 1 - 0 - 2 - 0 - 1
cinquieme transfert 1 - 1 - 0 - 1 - 1 et c'est fini

3ème jour il a 6 momes ---> 14 transferts et c'est fini
n ième jour il a 2n momes et 2n oranges ---> 1 + 4 + 9 + 16 + 25 +...+ n² et c'est fini.

il lui reste donc 2 oranges à 4 + 9 + 16 +.. + n²

freddy · 16-09-2011 14:06:38

Re,

je vais faire simple pour tomtom :

position 6 heures, le gars qui en a 20.

Il est choisi au hasard 4 fois, il lui en reste donc 12, à sa droite il y en a 4 et à sa gauche autant.

Maintenant, comment poursuit-on ?

Où est passé le tirage aléatoire du petit problème ?

totomm · 16-09-2011 16:11:44

Bonjour,

totomm a écrit :

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

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 ...

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 !

Dernière modification par freddy (28-09-2011 17:26:51)

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+-*/

Dernière modification par karlun (25-09-2011 12:00:36)

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 m₀(E) par m₁(E) et m₂(E)

Cordialement.

freddy · 25-09-2011 23:13:21

totomm a écrit :

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 m₀(E) par m₁(E) et m₂(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 · 26-09-2011 14:28:26

Bonjour

freddy a écrit :

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 · 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.

Dernière modification par freddy (27-09-2011 11:05:03)

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

totomm post #9 a écrit :

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

Dernière modification par totomm (27-09-2011 07:50:20)

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 !

Dernière modification par freddy (27-09-2011 17:27:17)

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

Dernière modification par freddy (29-09-2011 17:03:35)

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 :

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

Forum de mathématiques - Bibm@th.net

#1 13-09-2011 22:47:40

Voisins / Voisines

#2 14-09-2011 02:44:42

Re : Voisins / Voisines

#3 14-09-2011 10:25:45

Re : Voisins / Voisines

#4 14-09-2011 12:08:31

Re : Voisins / Voisines

#5 14-09-2011 13:28:25

Re : Voisins / Voisines

#6 14-09-2011 15:23:10

Re : Voisins / Voisines

#7 14-09-2011 19:03:00

Re : Voisins / Voisines

#8 15-09-2011 10:48:27

Re : Voisins / Voisines

#9 16-09-2011 00:37:02

Re : Voisins / Voisines

#10 16-09-2011 08:54:52

Re : Voisins / Voisines

#11 16-09-2011 10:52:57

Re : Voisins / Voisines

#12 16-09-2011 13:04:10

Re : Voisins / Voisines

#13 16-09-2011 14:06:38

Re : Voisins / Voisines

#14 16-09-2011 16:11:44

Re : Voisins / Voisines

#15 23-09-2011 16:51:06

Re : Voisins / Voisines

#16 25-09-2011 11:26:20

Re : Voisins / Voisines

#17 25-09-2011 11:42:26

Re : Voisins / Voisines

#18 25-09-2011 19:43:17

Re : Voisins / Voisines

#19 25-09-2011 23:13:21

Re : Voisins / Voisines

#20 26-09-2011 14:28:26

Re : Voisins / Voisines

#21 26-09-2011 17:12:47

Re : Voisins / Voisines

#22 27-09-2011 07:36:28

Re : Voisins / Voisines

#23 27-09-2011 17:26:00

Re : Voisins / Voisines

#24 27-09-2011 19:12:47

Re : Voisins / Voisines

#25 27-09-2011 19:37:39

Re : Voisins / Voisines

Réponse rapide

Pied de page des forums