Réunion à la maison

Olympiades mathématiques, énigmes et défis
Imod
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Réunion à la maison

par Imod » 01 Déc 2018, 18:56

Bonjour à tous :mrgreen:

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

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
Membre Relatif
Messages: 202
Enregistré le: 25 Aoû 2017, 02:07

Re: Réunion à la maison

par FLBP » 01 Déc 2018, 22:33

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
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Re: Réunion à la maison

par Imod » 02 Déc 2018, 11:45

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
Membre Naturel
Messages: 83
Enregistré le: 08 Mar 2016, 20:54

Re: Réunion à la maison

par ffback » 05 Déc 2018, 19:24

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
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Re: Réunion à la maison

par Imod » 07 Déc 2018, 18:37

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

Imod

ffback
Membre Naturel
Messages: 83
Enregistré le: 08 Mar 2016, 20:54

Re: Réunion à la maison

par ffback » 08 Déc 2018, 09:53

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
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Re: Réunion à la maison

par Imod » 08 Déc 2018, 11:06

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
Membre Naturel
Messages: 83
Enregistré le: 08 Mar 2016, 20:54

Re: Réunion à la maison

par ffback » 08 Déc 2018, 11:22

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
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Re: Réunion à la maison

par Imod » 08 Déc 2018, 12:23

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
Membre Naturel
Messages: 83
Enregistré le: 08 Mar 2016, 20:54

Re: Réunion à la maison

par ffback » 08 Déc 2018, 12:56

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
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Re: Réunion à la maison

par Imod » 08 Déc 2018, 13:46

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

Imod

PS : Merci de t'intéresser au problème qui n’attire vraiment pas grand monde ( trop difficile ? ) .
Modifié en dernier par Imod le 08 Déc 2018, 18:02, modifié 1 fois.

ffback
Membre Naturel
Messages: 83
Enregistré le: 08 Mar 2016, 20:54

Re: Réunion à la maison

par ffback » 08 Déc 2018, 15:51

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
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Re: Réunion à la maison

par Imod » 08 Déc 2018, 18:10

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
Membre Naturel
Messages: 83
Enregistré le: 08 Mar 2016, 20:54

Re: Réunion à la maison

par ffback » 08 Déc 2018, 19:05

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
Habitué(e)
Messages: 6401
Enregistré le: 12 Sep 2006, 12:00

Re: Réunion à la maison

par Imod » Hier, 10:47

Oui c'est bon et plutôt astucieux :idea: , bravo :frime1: . 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
Membre Naturel
Messages: 83
Enregistré le: 08 Mar 2016, 20:54

Re: Réunion à la maison

par ffback » Hier, 20:34

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 à ?

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite