Sur une tige (que l'on assimilera à un segment) se trouvent plusieurs fourmis (que l'on assimilera à des points). - Les fourmis se déplacent à vitesse constante.
- Il faut une minute à une fourmi pour aller d'un bout à l'autre de la tige.
- Lorsque deux fourmis se croisent, elles changent de sens.
- A chaque fois qu'une fourmi arrive à l'extrémité de la tige, elle tombe.
1 ) Dans le pire des cas, combien de temps faut-il attendre pour que toutes les fourmis tombent de la tige ?
2 ) Même question avec des fourmis se déplaçant à des vitesses constantes mais différentes...
salut, je te propose une tentative de résolution:
RépondreSupprimersi on a une fourmi qui se déplace à une vitesse v sur une tige de longueur L, au pire, il faut attendre un temps t=L/v, cad le temps qui lui faut pour parcourir la tige.
Si on a deux fourmis, le temps maximal est lorsque les deux fourmis partent chacune à une extrémité et se rencontrent au milieu de la tige Au final, une fourmi aura parcouru la même distance sur la tige donc aura mis le même temps.
(réflexion après relecture, en fait le temps maximal est atteint dans plusieurs cas mais une fourmi ne peut parcourir une distance plus grande que la longueur de la tige)
Pour trois fourmis, j'imagine que le temps maximal va être donné par la 3ème fourmi. C'est elle qui doit rester le plus longtemps sur la tige. je pense que le temps est maximal lorsque on une fourmi à chaque extrémité et la troisième à 1/3 de la tige et se dirigeant vers les 2/3 restant. Dans ce cas, cette fourmi rencontre celle qui lui fait face lorsque elle aura parcouru la distance L/3 (la moitié de la distance séparant les fourmis au départ). Les fourmi se retournent, celle du milieu fait maintenant face à la troisième. celle ci aussi a parcouru L/3. la distance séparant les fourmi est donc L/3. Elles se percutent au milieu de la tige. Chacune a parcouru la distance L/2-L/3= L/6. Les deux fourmis vont donc tomber en même temps (et auront donc parcouru les même distances. Au final, le temps va être le même que pour les cas d'avant. petite conclusion : le temps ne dépend pas uniquement de la position de la 3ème fourmi (ou en tous cas, la 3ème fourmi n'est pas la seul qui aura parcouru le plus long chemin
Conclusion générale: Puisque le temps est le même pour n=1,2 et 3, il est le même pour n'importe quel nombre de fourmi : le temps ne dépend pas du nombre de fourmis mais de la longueur de la tige. Bon,
C'est un raisonnement de physicien mais je ne saurais pas le démontrer uniquement avec des maths (on fait pas des récurrences tout les jours en physique non plus!)
Voila bien une réponse de physicien en effet :)
RépondreSupprimerNon seulement tu as traité que n=1,2 et 3 mais en plus tu n'as pas expliqué en quoi pour n=3 ton cas était le pire...
En réalité la solution dans le cas général ne peut se faire avec une récurrence et une courte explication suffit à résoudre ce problème.
ben en fait, pour n=3, je ne saurais pas prouver que j'ai pris le cas dans le pire des cas. Je l'ai fait au feeling. Par contre en relisant, je suis en train de me dire qu'il n'y a pas un cas unique ou le temps est maximal. Si l'on garde les deux fourmis aux extrémités, qu'importe la position de la troisième fourmi, elle tombera en même temps que celle dont elle était le plus proche au départ, non?
RépondreSupprimerSinon j'ai pas vraiment d'idée sur l'explication. est ce que c'est mathématique?
On peut donner le résultat sans n'avoir aucun calcul à faire. Il s'agit de raisonnement pur.
RépondreSupprimerJe propose la solution suivante.
Supprimer1) Imaginons que chaque fourmi soit munie d'un petit bâton de témoin (comme dans une course de relais) et que, chaque fois qu'une fourmi en croise une autre, elle échange son bâton avec elle. Ainsi, à tout instant, chaque fourmi tient un bâton et chaque bâton est tenu par une fourmi. Quand une fourmi tombe, son bâton tombe avec elle : donc l'instant où la dernière fourmi tombera est aussi l'instant où le dernier bâton tombera.
Plutôt que m'intéresser aux trajectoires des fourmis, je m'intéresse à celle des bâtons. Quand deux fourmis se croisent, elles échangent leurs bâtons en même temps que leurs directions : donc les bâtons eux-mêmes ne changent jamais de direction : ils se déplacent toujours dans le même sens, à vitesse constante. Chaque bâton mettra donc au plus une minute à tomber, et ce maximum sera atteint si et seulement s'il y a, dans la situation initiale, un bâton à une extrémité de la tige qui est dirigé vers l'autre extrémité.
Conclusion : le temps maximal pour que toutes les fourmis tombent est de une minute. Ce maximum est atteint si et seulement si, dans la situation initiale, il y a au moins une fourmi qui est à une extrémité de la tige et qui se dirige vers l'autre extrémité.
2) On imagine le même passage de témoin qu'à la première question. La nouveauté ici, c'est que les bâtons ne se déplacent pas à vitesse constante, mais à la vitesse propre des fourmis qui les transportent.
Considérons v la vitesse minimale parmi celles des fourmis, et L la longueur de la tige. Alors, se déplaçant toujours à la vitesse v au moins, chaque bâton aura parcouru la tige entière en un temps inférieur ou égal à L/v.
Pour que ce maximum soit atteint, il suffit que toutes les fourmis se déplacent à la vitesse v et qu'une fourmi se trouve initialement à une extrémité de la tige en se dirigeant vers l'autre.