Un trio d'enfer

[Flodelarab]

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.

[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 :triste: :triste: :triste:

[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. :hum:
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 [TEX]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

[Imod]

C'est ça alben :++: j'ai la même solution avec passage en binaire .

Imod

[Anonyme]

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!

[scelerat]

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

[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 , M étant la masse totale
78maths propose M=5425 donc A=23 324 et

[Patastronch]

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 , M étant la masse totale
78maths propose M=5425 donc A=23 324 et

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 :we:

[alben]

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 :we:

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 :zen:
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

[Patastronch]

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.