Mathématiques - Un trio d'enfer

Un trio d'enfer
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: Imod

Un peu de pseudo-biologie

Trois bactéries sévissent dans un tube , elles passent leur temps à se heurter et à chaque choc , la plus légère prélève à la plus lourde de quoi doubler son propre poids . Au départ chaque bactérie à une masse égale à un nombre entier d'unités de masse . Peut-on espérer que quelque soit les masses de départ , après suffisamment de chocs , il ne reste plus que deux bactéries ? Une seule ?

Imod

Posted by: AL-kashi23

Bonjour,

Que se passe-t-il en cas de choc de bactéries de même masse ?

(j'avais mis poids mais bon je l'ai retiré vite fait bien fait au cas où un physicien se perde dans les travées de cette rubrique et

au mot "poids"

)

Posted by: Imod

Citation:

Posté par AL-kashi23

Que se passe-t-il en cas de choc de bactéries de même masse ?

Disons qu'alors l'une des deux absorbe l'autre .

Imod

Posted by: bruce.ml

J'immagine que si une bactérie arrive à une masse nulle, ce n'est pas elle qui doublera son poids au choc suivant ?

Posted by: Imod

Citation:

Posté par bruce.ml

J'immagine que si une bactérie arrive à une masse nulle, ce n'est pas elle qui doublera son poids au choc suivant ?

Faisons simple , une bactérie de masse nulle n'existe pas : si deux bactéries de même masse se rencontrent l'une double sa masse et l'autre disparaît

Imod

Posted by: Rain'

Une question bête, quand il y a un choc, seulement deux des trois se cognent?

Donc on peut imaginer par exemple que ce seraient toujours les deux mêmes qui se cognent ou pas ?

Posted by: Imod

Citation:

Posté par Rain'

Une question bête, quand il y a un choc, seulement deux des trois se cognent?

Restons classique pas de triangles chez les bactéries

Citation:

Posté par Rain'

Donc on peut imaginer par exemple que ce seraient toujours les deux mêmes qui se cognent ou pas ?

Sauf exceptions ( faciles à caractérisées ) les chocs répétés entre les deux même bactéries ne font disparaître auncune des deux . Disons que tous les chocs sont équiprobables et que la possibilité que les deux mêmes bactéries se heurtent à l'infini n'est pas réalisable ( probabilité nulle ) .

Imod

Posted by: Rain'

Quoiqu'il en soit c'est facile de trouver une combinaison de poids qui empêche qu'il ne reste qu'une seule bactérie.

Reste à voir pour n'en faire disparaitre qu'une seule

Posted by: bruce.ml

Je crois qu'il y a une petite imprécision dans l'énoncé que je m'en vais éclaircir par cette question : sont-ce forcément la plus lourde et la plus légère du bocal qui se rencontrent, ou bien le choc est aléatoire et le transfert a lieu entre ces deux là ?

Posted by: Rain'

Aléatoire je pense sinon c'est un peu trop facile.

Posted by: scelerat

Citation:

Posté par Imod

Peut-on espérer que quelque soit les masses de départ , après suffisamment de chocs , il ne reste plus que deux bactéries ? Une seule ?

Deux, on peut esperer. Ou alors, il faut trouver un ensemble de jeux de 3 entiers, 2 pairs differents et un impair (on peut facilement montrer qu'en faisant se rencontrer deux eventuelles bacteries de masse impaire, et/ou en divisant par deux toutes les masses si elles sont toutes paires, on s'y ramene) qui soit stable dans les collisions. Pas evident !

Par contre, une seule, c'est facile, il suffit de prendre une somme des masses impaire pour etre sur que jamais les deux dernieres ne seront de meme masse et qu'elles subsisteront donc indefiniment.

Posted by: Imod

Pour être plus précis , les bactéries ne peuvent être que détruites ( pas de création ) . Peut-on en connaissant la masse totale des 3 bactéries , prévoir le nombre de bactéries à la fin ?

Par exemple avec une masse totale de 8 restera-t-il forcément une seule bactéries après suffisamment d'échanges ?

Imod

Posted by: Patastronch

La seule chose que j'arrive a prouver c'est que,si on est dans une configuration a 2 bacteries (indispensable pour arriver a une config a une seule bacterie) alors si au bout de n chocs on detruit une bacterie c'est que la masse totale etait un multiple de 2^n.

Mais j'ai la certitude qu'une masse totale de 2^n mene a la destruction de la derniere bacterie en au plus n chocs a partir d'une configuration a 2 bacteries.

Posted by: alben

Bonsoir,
Avec une masse totale égale à une puissance de 2, il ne restera finalement qu'une seule bactérie après un temps très long.
1 Avec seulement deux bactéries, masse totale $= 2^n$ et soit p la plus grande puissance de deux divisant la masse de l'une d'elle. p est inférieur à n et l'on montre que la masse de l'autre bactérie est également divisible par 2^p.
A chaque rencontre, l'une des bactérie double sa masse et p augmente de 1. Tant que p reste inférieur à n, il est égal pour les deux bactéries et augmente de 1 à chaque rencontre... une des bactéries disparait donc en au plus n-1 étapes.
2 avec 3 bactéries : notons p1,p2,p3 les puissances de 2 divisant la masse de chaque bactérie. supposons $p_1\leq p_2 \leq p_3<br />$ Alors p1=p2 et p3>p2 (on s'en assure facilement).
Tant que p1 et p2 ne se rencontrent pas, la situation reste identique, pmax peut changer mais les deux mini restent identiques.
Mais au bout d'un temps indéterminé, ils se rencontreront et le mini augmentera d'une unité. Finalement après un temps moyen de 3(n-p) (p est la valeur du p mini au départ), il ne restera qu'une bactérie.
Donc la réponse à la dernière question d'Imod est oui, mais pour 10 ?

Posted by: nuage

Salut, et bonne année 2008.
Pour finir, comme le remarque scelerat le seul cas possible pour avoir 3 bactéries à l'infini est le cas (pair, pair, impair). Ce qui montre que le cas d'une somme des masses paire n'est pas à considérer : d'une somme égale à 10 on peut toujours arriver (avec une proba non nulle, donc avec certitude à l'infini) à la somme de trois nombres pairs et se ramener à une somme égale à 5. Ce qui fait 2 bactéries à la fin.
Mais dans le cas (pair, pair, impair) il y a toujours un chemin qui mène à l'égalité des deux nombres pairs (ça c'est une intuition non démontré, mais je suis prêt à parier cher dessus). Et on fini donc avec 2 bactéries si la somme des masses n'est pas une puissance de 2.

[modification]
pour étayer mon affirmation : il me semble que l'on peut toujours choisir un chemin qui fait décroître la différence entre les deux nombres pairs.

Posted by: alben

D'accord avec Nuage, on a donc deux situations :
la masse totale est une puissance de 2->on finit avec une bactérie (en un temps fini)
la masse totale n'est pas une puissance de 2 : on finit avec 2 bactéries.
pour démontrer la dernière, il suffit de prouver que la configuration stable (pair, pair, impair) conduit à l'égalité des pairs avec une proba non nulle, autrement dit qu'il n'existe pas de cycle sans égalité.
Ca semble intuitivement vrai, mais pour le prouver ?

Posted by: Patastronch

Citation:

Posté par alben

autrement dit qu'il n'existe pas de cycle sans égalité.

Non, qu'il existe toujours au moins un cycle avec égalité.

Pour le fait qu'il soit toujours possible de passer a 2 bacteries quelque soit la masse totale, il faut reussir a prouver qu'il existe toujours un cchemin qui mene aux masse m1, m2 et m3 tel que m1+m2 (ou n'importe quelle somme de 2 masses) est une puissance de 2.

Apres on tombera dans un cas connu pseudo démontré par Alben.

Posted by: nuage

Citation:

Posté par alben

...
la masse totale n'est pas une puissance de 2 : on finit avec 2 bactéries.
pour démontrer la dernière, il suffit de prouver que la configuration stable (pair, pair, impair) conduit à l'égalité des pairs avec une proba non nulle, autrement dit qu'il n'existe pas de cycle sans égalité.
Ca semble intuitivement vrai, mais pour le prouver ?

Soit $p_1$ , $p_2$ et $i$ les trois nombres, avec $p_1$ et $p_2$ pairs, $i$ impair, $p_1<p_2$ .
Si $p_1\,<\,2\, p_2$ une rencontre $(p_1\, ;\,p_2)$ diminue la différence entre les deux pairs.
Si $p_1\,<\,i\,<\,p_2\,<\,2 p_1$ la rencontre $(p_1\, i)$ diminue la différence entre les deux pairs.
Si $p_1\,<\,p_2\,<\,2 p_1\,<\,i$ la rencontre $(p_1\, i)$ diminue la différence entre les deux pairs.
Ce qui, sauf erreur de ma part, suffit pour conclure.

Posted by: Patastronch

Citation:

Posté par nuage

1/ p1 forcement plus petit que 2p2 par definition t'as du te tromper. Surtout que c'est faux, ca diminue pas forcément la difference.

2/Contre exemple :p1=6 p2=8 et i=7. La rencontre entre p1 et i donne : p1=12 p2=8 et i=1. On a pas diminué la dif entre les 2 pairs.

3/ Contre exemple : p1=6 p2=8 i=301. La rencontre entre p1 et i donne :
p1=12 p2=8 et i=295. On a pas diminué la dif entre les 2 pairs.

Posted by: nuage

Salut, et bonne année 2008.
sur le point 1 je pense que tu n'as pas bien compris.
Sur les points 2 et 3 je me suis trompé. Merci de ta critique.
Je vais essayer de préciser ça (si j'y arrive) à une heure plus décente.

A+
nuage :

Posted by: Patastronch

Citation:

Posté par nuage

Salut, et bonne année 2008.
sur le point 1 je pense que tu n'as pas bien compris.
Sur les points 2 et 3 je me suis trompé. Merci de ta critique.
Je vais essayer de préciser ça (si j'y arrive) à une heure plus décente.

A+
nuage :

Non le point 1 est tout aussi faux.
Contre exemple : p1=6 p2=8, apres rencontre on a p1=12 et p2=2. On a pas reduit la dif entre les pairs.

C'est pour ca que j'ai cru que tu t'étais trompée et que tu voulais dire (5/2 * p1<p2 comme condition)

De toute facon ce genre demo poura etre valable que si tu prouves que quelques soit l'état des 3 particules il existe au moins une rencontre (ou une suite de rencontres prédéfinie) qui reduit STRICTEMENT la dif des pairs. Ce qui me parait compliqué a faire puisque le chemin menant a 2 bacteries n'est pas strictement monotone forcement, ce qui pousse a prevoir des combinaisons de chocs pour y arriver. Ce qui peut vite devenir une litanie de cas.

Posted by: scelerat

Apres quelques reflexions nocturnes, il me semble qu'un point important est que le pgcd des masses ne peut pas decroitre dans une collision.
Si on restreint les collisions a deux bacteries, on va decrire toutes les configurations {(n-i)p,ip} ou p est le pgcd des masses initiales et n-i et i premiers entre eux si n est impair (meme si je n'ai pas encore reussi a le prouver), passer par {(n/2)p,(n/2)p} et voir l'une des bacteries disparaitre si n est pair.

A trois bacteries, si les deux de masse paire ne peuvent se detruire entre elles, une collision avec celle de masse impaire doit forcement faire sortir du cycle...

Posted by: scelerat

Citation:

Posté par alben

Donc la réponse à la dernière question d'Imod est oui, mais pour 10 ?

Pour n=10, c'est facile. En une collision au plus, on se ramene a des masses toutes paires, donc on divise toutes les masses par 2 et n=5. Et a n= 5, on est forcement dans la configuration ou deux masses sont egales... Donc on n'a plus que 2 bacteries de parites differentes, 4 et 1 ou 2 et 3, et on alterne indefiniment entre ces deux configurations.
On peut donc subodorer que seules les puissances de deux permettent de finir avec une seule bacterie, et que dans tous les autres cas on termine avec 2.

Posted by: Flodelarab

Citation:

Un peu de pseudo-biologie

Trois bactéries sévissent dans un tube , elles passent leur temps à se heurter et à chaque choc , la plus légère prélève à la plus lourde de quoi doubler son propre poids . Au départ chaque bactérie à une masse égale à un nombre entier d'unités de masse . Peut-on espérer que quelque soit les masses de départ , après suffisamment de chocs , il ne reste plus que deux bactéries ? Une seule ?

Imod

Un peu de pseudo-ludologie

Trois joueurs de poker sévissent dans une salle, ils passent leur temps à faire tapis et à chaque rencontre, le tapis le plus petit prélève au plus gros de quoi doubler sa propre pile de jetons. Au départ, chaque pile de jetons a un nombre entier de jetons. Peut-on espérer que quelque soient les piles de départ, après suffisamment de rencontres, il ne reste plus que deux joueurs ? un seul gagnant ?

Imod, arrêtes de passer tes nuits dans les tripots.
Tu ne trompes personne.

Posted by: Imod

Bonsoir à tous , beaucoup de progrès !

Semble acquis : s'il ne reste que deux bactéries dont la masse totale est une puissance de deux , après quelques échanges il ne restera plus qu'une bactérie .

Une autre certitude mais qui n'est pas encore établie : partant de trois bactéries de masses quelconques et en choisissant convenablement les échanges on peut aboutir à deux bactéries .

Si cette dernière propriété est démontrée il est très facile d'établir le nombre de bactéries au final en fonction de la masse totale initiale .

Imod

PS : Certains semblent douter de l'intérêt scientifique du problème , j'avoue ne pas comprendre une telle défiance

Posted by: alben

Bonne journée,

On a donc 3 bactéries et il s'agit de montrer que l'une disparaitra.
Petite précision pour Patastronch : qu'il n'existe pas de cycle qui ne contienne pas l'égalité ou qu'il existe un chemin la contenant.

Supposons qu'il existe un tel cycle, c'est à dire une famille de configurations dont on ne puisse pas sortir et qui ne contienne pas (0,x,y).
Soit alors m la masse minimale atteinte et (m,x,y) avec $m<x< y$ une des config correspondant. Les inégalités sont strictes sinon on pourrait atteindre zéro en une seule étape.
Ecrivons $Ent(\frac xm)=\sum_{i=0}^k\; a_i2^i$ , les ai étant égaux à 0 ou 1;ak=1 (écriture de ent(x/m) en binaire)
On va doubler m (k+1) fois en prelevant dans x ou dans y selon ai :

si $a_i=0$ on prélève dans y
si $a_i=1$ , on prélève dans x

On aura donc prélevé dans x : $m\sum_{i=0}^k\; a_i2^i=m.ent(\frac xm)$
et dans y $m(2^{k+1}-1-ent(\frac xm))$
On peut vérifier que ces deux quantités sont inféreures à x (et donc à y) et que ce qui reste dans x vérifie 0 < (reste en x) < m.
On a donc trouvé un chemin de proba non nulle tel que l'on obtienne un mini inférieur à m -> contradiction
Donc il ne peut exister de cycle ne comprenant pas zéro et toute config à trois bactéries se réduira à 2. Ensuite, si la masse totale n'est pas une puissance de 2, on reste à 2, sinon il ne reste qu'une bactérie

Posted by: Imod

C'est ça alben

j'ai la même solution avec passage en binaire .

Imod

Posted by: 78maths

La question est bien de savoir si l'on peut espérer qu'après un nombre suffisant de chocs, il ne restera plus qu'une ou deux bactéries?
On peut toujours espérer.
Bon sinon, il est établi qu'à deux, il faut une puissance de 2, on passe à 1.Cependant, pour passer à 2 avec des chocs aléatoires et des masses aléatoires, je vois pas très bien.(avoir la chance de tomber sur des puissances de 2 est théoriquement très faible)Car pour détruire une bactérie, il faut une masse égale.
Est-ce possible?Je ne pense pas , mais sinon expliquez-moi ça!
Avec une bactérie de 4395, une de 43 et une de 987.
Vous avez le droit à une infinité de choc.

Il faudrait que vous en fassiez des puissances de 2!

BONNE CHANCE!

Posted by: scelerat

Citation:

Posté par 78maths

avoir la chance de tomber sur des puissances de 2 est théoriquement très faible

On parle de la somme des masses des bacteries au depart. Cette somme reste constante dans les collisions, donc il n'est pas question de "chance de tomber sur des puissances de 2".

Posted by: alben

Bonjour,

dans mes tentatives, j'avais fait un petit programme de simulation. Avec les valeurs proposées par 78maths, sur 120 simulations, 116 arrivent à zéro en moins de 23 600 chocs et 4 dépassent (j'ai limité le nombre d'essais). La moyenne est de 7 600
ces 120 essais se distribuent ainsi

20 % entre 100 et 1000 chocs
55 % entre 1000 et 10 000 chocs
15 % entre 10 000 et 20 000 chocs
10 % au delà

La distribution a une allure plus ou moins lognormale
je m'étais posé la question de savoir si l'espérance du nombre de chocs ne pouvait pas être infinie comme ça arrive parfois dans ce genre de phénomène mais j'ai pu majorer celle-ci par $\frac A2.3^A \;avec \;A=\frac{MlnM}{2}$ , M étant la masse totale
78maths propose M=5425 donc A=23 324 et $E< 10^{11133}$

Posted by: Patastronch

Citation:

Posté par alben

Bonjour,

dans mes tentatives, j'avais fait un petit programme de simulation. Avec les valeurs proposées par 78maths, sur 120 simulations, 116 arrivent à zéro en moins de 23 600 chocs et 4 dépassent (j'ai limité le nombre d'essais). La moyenne est de 7 600
ces 120 essais se distribuent ainsi

20 % entre 100 et 1000 chocs
55 % entre 1000 et 10 000 chocs
15 % entre 10 000 et 20 000 chocs
10 % au delà

Je comprends pas ce que ca veut dire "arrivent a zero".
Les valeurs données par 78maths sont toutes impairs donc somme totale impair ce qui implique qu'il peut pas rester moins de 2 bacteries. Pas besoin de simulation pour dire qu'il y apas de combinaison de collision possible qui arrive a 1 bacterie

Posted by: alben

Citation:

Posté par Patastronch

arrive à zéro=disparition d'une bactérie sur 3 initiales
Le message de 78maths évoquait assez clairement le passage de 3 à 2 bactéries. Son histoire de puissances de 2 dans ce cadre est plus confuse mais la réponse de scelerat est suffisante.
Il n'empêche qu'il reste une question de savoir combien de temps peut prendre le passage de 3 à 2 bactéries. Peut-on envisager la possibilité que cela puisse exceptionnellement prendre un temps infini ?
J'ai cru comprendre que tu étais informaticien, ce genre de questions devrait de préoccuper

En fait, mes calculs et simulations montrent que cela n'est pas le cas mais que l'on a quand même une espérance très élevée, c'est à dire qu'avec une masse globale assez conséquente (de l'ordre du million), une simulation informatique risque de durer plus longtemps que la machine sur laquelle on la fait

Posted by: Patastronch

Citation:

Posté par alben

Il n'empêche qu'il reste une question de savoir combien de temps peut prendre le passage de 3 à 2 bactéries. Peut-on envisager la possibilité que cela puisse exceptionnellement prendre un temps infini ?

Oui puisqu'il est possible de tomber dans des cycles. Par exemple une bacterie pese m et l'autre 2m et ne cessent de ce choquer entre elle indéfiniment. La probabilité est tres faible de rester coincé indéfiniment dans un cycle ou dans une série de cycle mais elle est pas nulle :)

Si tu interdit les cycles en interdisant un choc qui menerait a une situation deja vu, dans ce cas la ca deviens plus compliqué car il est alors possible qu'aucun des 3 chocs possible ne deviennent alors tolérés et l'algorithme sera alors bloqué si on a pas prévu un systeme pour revenir en arriere et interdire le choc précédant l'impasse. Un tel algorithme aurait la possibilité de renvoyer une combinaison sans cycle possible des chocs qui mene a 2 bactéries. Il est meme possible de renvoyer la plus courte de ces combinaisons de chocs en modifiant legerment le principe pour le transofrmer en Branch and Bound. C'est a dire qu'une fois qu'il a trouvé un chemin possible il le considere comme une impasse et stock sa longueur comme valeur optimale trouvée. Puis se remet a parcourir les autres chemins en arretant la recherche lorsque le chemin qu'on parcourt depasse la valeur optimale trouvée. Et a chaque fois qu'on toruve un chemin "arrivant a zero:) " plus court on met a jour notre longueur optimale. Mais bon, la on tombe dans un probleme d'optimisation et non de décision :) (probleme de décision = tous probleme dont la réponse est soit oui ou non, par exemple ici : existe t il une combinaison de choc menant a 2 bacteries avec les valeurs m1,m2 et m3 comme masse initiale).

Mais vu ta démo, il me parait assez evident que si on interdit les cycles alors on finit toujours en un nombre fini de choc avec 2 bacteries puisqu'il existe toujours un chemin y menant et que l'interdiction des cycles ainsi que la discretisation des masses et des transferts de masses rendent fini le nombre d'états possible et donc rend fini le nombre de chemin entre ces états.