Réunion à la maison

[Imod]

Bonjour à tous

Un problème que j'ai déjà posé sous plusieurs formes à divers sites et qui continue à m'intriguer

Mes amis et moi habitons dans le même carré de côté 1 et j'aimerais réunir tout le monde chez-moi dans un temps record . Je pars donc prévenir un voisin qui peut rejoindre mon domicile ou prévenir un autre voisin et je fais de même . On continue ainsi en admettant que chaque personne prévenue agit instantanément de la même façon et se déplace à une vitesse constante égale à 1 .

On suppose en plus que mes amis et moi-même sommes disposés dans la pire des positions .

Combien de temps faudra-t-il attendre avant que tout le monde soit réuni chez moi

Sauf erreur la réponse est très simple et quasi indépendante du nombre d’amis mais la justification est loin d'être aussi simple .

Imod

[FLBP]

Salut,
je trouve ,
C'est assez étonnant, on dirait que ce problème offre un temps minimum constant (sous certaines conditions)
Je voir si j'ai une idée démo ...

[Imod]

Peut-on trouver une disposition où il faut attendre plus de avant le début de la réunion ?

Imod

PS : il y a une variante au problème où je suis au centre du carré .

[ffback]

Salut,

Je suis pas convaincu par le
C'est effectivement ce qu'on obtient avec une maison à chaque coin, mais le parcours à faire me semble un peu trop "au poil de c.." pour que ça marche, et en rajoutant par exemple une 5eme maison proche du coin opposé au coin initial, mais pas sur le parcours (cad pas sur la diagonale ou un côté), sauf erreur on va être obligé de faire un petit détour et donc obtenir un peu plus que .

Par contre, je suis convaincu qu'on peut effectivement borner le temps max indépendemment du nombre de maisons, avec la stratégie basique suivante: on recrute 3 collegues (si ya plus de 3 maisons), puis les 4 gus vont au centre du carré: si on est pas fin du tout, tout ceci se fait en un temps . A partir de là, on découpe le carré en 4, et chacun refait la stratégie dans l'un des carrés 2 fois plus petit, donc ira 2 fois plus vite. Le pouvoir des séries géométrique permettra donc de visiter toutes les maisons en un temps . Puis on rentre à la maison initiale, ce qui fait un temps total

J'imagine que maintenant, faut optimiser le bousin.

[Imod]

Bon en effet avec 1+4 habitants on dépasse et sûrement avec 1+5 , ça devient moins sûr avec 1+x et x plus grand que 5 . Je suis pratiquement convaincu que la longueur limite est
et qu'elle est atteinte rapidement ( pas asymptotiquement ) .

Je ne sais pas si le problème avec ma position au centre est plus simple mais la limite semble atteinte définitivement à partir de 1+5 habitants .

Je propose les deux problèmes car ils sont certainement liés et je ne sais pas lequel est le plus simple à aborder .

Les deux sont à coup sûr de sérieux casse-têtes

Imod

[ffback]

Je ne crois pas que le soit atteint, même avec beaucoup de maisons. Si on reprend mon exemple précédent, avec une maison à chaque coin, mais au lieu de rajouter juste une maison proche du coin opposé, je rajoute une suite de maisons, chacune étant beaucoup plus proche du coin que la précédente. (de sorte que pour passer par 2 de ces maisons et un des deux coins restants, on dépasse ). Alors il me semble que ça fournit un contre-exemple.

[Imod]

Je ne suis pas convaincu par ton contre-exemple car la multiplication des points multiplie les trajectoires .
Par exemple avec deux points C1 et C2 proches de C dans le carré ABCD :

A->C1->D->A
C1->C2->B->A
C2->C->A

Il faudrait préciser la position des points C1 et C2 pour qu'une des trajectoires soit supérieure à

Imod

[ffback]

La position de C1 n'est pas très importante je crois (tant qu'on n'est pas sur un coté/diagonale.

Pour C2:
si on prend ton exemple, un des trajets obtenus (en faisant des "relais") avec ton parcours est
A->C1->C2->B->A
Si C2 est très proche de C, la longueur du trajet est presque celle de A->C1->C->B->A, qui est strictement plus grand que .

[Imod]

Je vois très bien ce que tu veux dire mais il faut faire extrêmement attention aux multiples variantes .

On pourrait choisir :

A->C2->B->A
C2->C1->D->A
C1->C->A

Il est fort possible qu'il y ait une disposition des Ci évitant la limite mais ce n'est pas complètement évident .

Imod

[ffback]

Dans ce cas là, le gros trajet serait A->C2->C1->D->A, presque egal à A->C1->C->B->A.

Si je dis pas de bétise, avec plus de points Ci:
1)soit il existe un trajet passant par les deux coins B et D et au moins un des Ci (cas facile, plus grand que )
2)soit il existe un trajet passant par 2 points Ci et un des deux coins B ou D (pas forcément dans cet ordre)

On construit les Ci par récurrence:
pour construire Cn, on veut que tous les trajets passant par B ou D, Cn et un point Ck pour k<n aient tous longueur . Si on prenait idéalement Cn=C, ce serait bien le cas. Et vu qu'il y a qu'un nombre fini de tels trajets, ça reste bon si on prend Cn différent de C mais suffisamment proche.

[Imod]

Je n'arrive pas à comprendre pourquoi avec un bon choix des Ci il y aurait forcément un A->Ci->Ck->B( ou D ) ->A strictement supérieur à . Je ne suis pas sûr qu'on puisse résoudre le problème sans mettre un peu les mains dans le cambouis .

Avec 1+4 points c'est clair mais il faudrait un exemple concret avec 1+5 .

Je ne suis pas sûr que ce soit complètement évident

Imod

PS : Merci de t'intéresser au problème qui n’attire vraiment pas grand monde ( trop difficile ? ) .

[ffback]

Un exemple concret à 6 points qui devrait marcher :
A(0,0) départ
B(0,1)
D(1,0)
C(1,1)
C1(1/2,3/4)
C2(0.998,0.999)

(réponse au PS: je ne pense pas que c'est le problème le plus difficile que tu aies posé^^)

[Imod]

OK , ça marche FF mais on voit bien que la construction de la suite Cn est loin d'être triviale même si la limite semble acquise .

Imod

[ffback]

Voici une preuve que si le nombre de maisons devient grand, le temps de parcours optimal tend vers .

J'utilise deux choses
-dans le carré, tout triangle a un périmètre inferieur à . Je n'ai pas vérifié le calcul, mais ça me semble vrai.
-qu'il existe un temps tel qu'il est possible de visiter toutes les maisons d'un carré de coté 1 en un temps , quelque soit la configuration ( ce que j'ai obtenu dans un post précédent avec des majorations grossières, ). Et donc que si on prend un carré de coté , on peut en visiter toutes les maisons en un temps inférieur à .

Maintenant divisons le carré de coté 1 en un grand nombre de petits carrés de côté . Si le nombre de maisons est suffisamment grand, on peut trouver au moins un petit carré contenant plus de maisons. Alors la stratégie:
-on va dans ce petit carré en un temps
-on visite toutes les maisons du carré en un temps , et on recrute ainsi personnes, 1 par carré
-chacune des personnes va dans un carré différent, en un temps (qui dépend de la personne)
-chacun visite son carré en un temps
-tout le monde rentre au bercail en un temps (qui dépend de la personne)

Puique , le temps total est inférieur à

[Imod]

Oui c'est bon et plutôt astucieux , bravo . Il reste à voir si on peut trouver une répartition avec autant de maisons que l'on veut et un temps de parcours strictement supérieur à .

Imod

PS : il y a aussi le cas avec ma maison au centre du carré qui doit pouvoir se ramener à l'étude précédente .

[ffback]

Pour rajouter des points, on peut continuer suivant le même principe. Donc depuis l'exemple précédent, pour le point suivant, on rajoute avec n suffisamment grand, disons n=100 et je pense qu'on est safe^^

Je reste intéressé par la question initiale qui consiste à trouver le pire cas possible. Puisque on tend vers quand le nombre de maisons tend vers l'infini, le pire cas est bien atteint pour un certain nombre fini de maisons. J'aurai envie de dire que c'est pour 5 maisons, mais ça reste à prouver. Et il faut aussi trouver alors la pire configuration à 5 maisons et le temps correspondant.

PS: quelqu'un sait prouver facilement que tout triangle inclus dans le carré unité un diamètre inférieur à ?

[Imod]

Bonsoir FF

Pour le lemme du triangle , on peut considérer que les sommets du triangle sont sur trois côtés différents du carré , après c'est géométriquement évident où il faut rentrer dans les inégalités "machin-chose" qui cadrent assez mal avec mes loisirs préférés

Je crois aussi au 5 comme pire des cas , on ne trouvera sans doute jamais de preuve mais la recherche d'une position extrémale est un beau challenge . Je n'oublie pas non plus le cas d'une maison centrée qui n'est pas forcément un copié-collé du problème initial .

Encore merci de l'intérêt que tu portes au problème

Imod