Tous chez le maire
Bonjour à tous
Un problème trouvé sur un site ami qui fait penser à celui du voyageur de commerce et que je trouve particulièrement intéressant.
On a $n$ points dans un carré, chacun représentant un habitant d'un village, l’un d’entre eux est le maire. Le maire doit réunir tout le monde chez lui et pour cela il va prévenir un voisin qui se rendra chez le maire ou ira prévenir un nouveau voisin. Le maire et chaque voisin informé continue la ronde jusqu’à ce que tout le monde soit réuni chez le maire.
On suppose que chacun se déplace à la même vitesse et utilise la meilleure stratégie. Quel temps faut-il prévoir pour réunir tout le monde chez le maire dans la pire des dispositions possible des habitants dans le carré.
Dans le problème initial il y a 200 habitants et le maire est au centre du carré .
J’ai commencé à regarder avec 2,3,4 ,… points : ça devient vite très compliqué et j’ai l’impression qu’à partir d’un certain seuil, ajouter des points avance l’heure de la réunion.
Merci d’avance à ceux qui s'intéresseront au problème.
Domi.
Un problème trouvé sur un site ami qui fait penser à celui du voyageur de commerce et que je trouve particulièrement intéressant.
On a $n$ points dans un carré, chacun représentant un habitant d'un village, l’un d’entre eux est le maire. Le maire doit réunir tout le monde chez lui et pour cela il va prévenir un voisin qui se rendra chez le maire ou ira prévenir un nouveau voisin. Le maire et chaque voisin informé continue la ronde jusqu’à ce que tout le monde soit réuni chez le maire.
On suppose que chacun se déplace à la même vitesse et utilise la meilleure stratégie. Quel temps faut-il prévoir pour réunir tout le monde chez le maire dans la pire des dispositions possible des habitants dans le carré.
Dans le problème initial il y a 200 habitants et le maire est au centre du carré .
J’ai commencé à regarder avec 2,3,4 ,… points : ça devient vite très compliqué et j’ai l’impression qu’à partir d’un certain seuil, ajouter des points avance l’heure de la réunion.
Merci d’avance à ceux qui s'intéresseront au problème.
Domi.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Le problème ressemble beaucoup à celui du voyageur de commerce avec la particularité que chaque voisin visité devient un voyageur potentiel .
Dans un carré de côté 1 ou les $n$ villageois se déplacent à la vitesse 1 , il faut prévoir sauf erreur :
$n=2 : t=\sqrt{2}$
$n=3 : t= 2\sqrt{2}$
$n=4 : t=2\sqrt{2}$
$n=5 : t=?$
Le problème original est vraiment intéressant mais il ouvre surtout des questions annexes passionnantes . Par exemple si on augmente le nombre de villageois , il me semble qu'on ne va augmenter indéfiniment le temps de parcours : au contraire . Quel est le temps limite que l'on peut atteindre et pour combien de villageois ?
Merci pour ta réponse :-)
Domi
PS : pour les durées proposées , le maire est supposé au centre du carré , on doit pouvoir faire pire sans cette condition .
content de te retrouver :-)
Il y a sûrement un truc que je n'ai pas vu car pour n=4, si le maire est au centre et chacun des 3 autres dans un coin je trouve $\sqrt 2 + 1$:
Le carré est ABCD de centre O. les individus O, A, B, C: le maire va de O à B (= $\sqrt 2/2$) puis, dans le même temps, d'une part le maire passe par C puis termine (accompagné par C) en O (=1+$\sqrt 2/2$) , d'autre part B passe par A puis termine (accompagné par A) en O.
Peut-être qu'il y a pire disposition, tout simplement!
A te lire
Amicalement
Paul
Dans le cas $n=4$ , on peut placer deux points très proches d'un des sommets du carré et le dernier sur le sommet opposé , on arrive bien au $2\sqrt{2}$ annoncé .
Amicalement
Domi
comment obtiens-tu moins de $2\sqrt 2$ si le maire et ses administrés sont chacun sur un coin du carré ?
Cordialement.
Le maire est au centre .
Je suis par ailleurs de plus en plus convaincu que cette contrainte biaise le problème , laisser le maire occuper n'importe quelle place rend le problème plus symétrique car alors chacun est un maire potentiel .
Cordialement
Domi
Une variante probabiliste : on tire uniformément au hasard la position des $n-1$ villageois. Montrer que le temps minimal pour regrouper tout le monde chez le maire converge en probabilité vers $\sqrt 2$ lorsque $n\to\infty$.
Et si la position du maire aussi est tirée au hasard ? dans ce cas il y a convergence en loi et l'espérance du temps minimal tend vers
$$
\int_1^2\int_1^2 \sqrt{x^2+y^2}\,dxdy \approx {2,\!14089}.
$$
Le problème original avec les 200 villageois semble vraiment trop complexe ( avec ou sans le maire centré ) , mais j'aimerais bien savoir à partir de combien d'habitants on peut commencer à avancer la réunion du maire ( dans le pire des cas ) .
Domi
Sans tenir compte de la distance l'algorithme est simple : le maire (ou un premier habitant quelconque) se déplace et prévient un autre habitant. Ensuite chaque habitant avisé se déplace et prévient un autre habitant et ainsi de suite jusqu'à que les N habitants soient tous prévenus qu'il y a une réunion.
à l'étape 0 le maire (ou l'habitant de départ) est avisé (1 seul averti)
à l'étape 1 le maire avise un habitant (2 avertis)
à l'étape 2 le maire avise un habitant et le précédent avisé avise un autre (4 avertis)
à l'étape 3 (...) (7 avertis)
à l'étape 4 (...) (10 avertis)
En dessinant l'arbre on voit de suite qu'à l'étape n on a : n(n+1)/2 + 1 habitants qui sont avertis
Et donc pour avertir N habitants il suffit de $\sqrt{N}$ étapes.
Evidemment ce n'est pas forcément la stratégie optimale puisqu'on néglige les distances.
Pour avoir la stratégie optimale il faudrait inventer des règles comme par exemple : chaque habitant considère ses plus proches voisins, ou bien chaque habitant compare la distance à la mairie et la distance au voisinage le moins exploré ...
Soit dit en passant on ne sait pas si c'est un jeu à information parfaite, si chaque habitant dispose de toutes les informations sur la situation globale du jeu à l'instant t (positions des habitants, distances, nombre des habitants à prévenir ...)
Parce que si chaque habitant n'a qu'une vision limitée du jeu (vue "locale) forcément ca change les stratégies utilisables.
Mais c'est vrai que j'ai raisonné comme si les habitants sont des machines appliquant une stratégie optimale (enfin on le suppose) pour trouver les plus courts déplacements vers leur regroupement ...
Soit $k$ le plus grand entier tel que $k^4 \leq n$. On découpe le village en $k^2$ parcelles carrées de côté $\frac 1k$. Quelle que soit la disposition des villageois, il y a au moins une de ces parcelles qui contient $k^2$ villageois (ou plus). Le maire en fait ses adjoints et il attribue une parcelle à chacun.
1. Le maire va dans la parcelle des adjoints. Temps inférieur à $\sqrt 2/2$.
2. Le maire fait prévenir tous les adjoints. Temps inférieur à $O(\frac1k)$.
3. Chaque adjoint va vers la parcelle dont il est responsable. Temps inférieur à $\sqrt 2$.
4. Dans chaque parcelle, l'adjoint fait prévenir tout le monde. Temps inférieur à $O(\frac1k)$.
5. Tout le monde va chez le maire. Temps inférieur à $\sqrt 2/2$.
Il reste à justifier les deux $O(\frac1k)$, mais ceci résulte du changement d'échelle des distances et du fait que le temps nécessaire pour prévenir en cascade tous les villageois d'un carré de côté 1, est majoré indépendamment du nombre de villageois (procéder récursivement).
@Siméon : Merci , j'avais aussi pensé au maillage , chaque adjoint prenant son quartier en charge . Il est clair que si on entasse les habitants dans deux coins opposés du carré , on s'éloigne très vite de cette moyenne .
Domi
A priori ca ressemble un peu "au pire des cas".
En prenant un cercle c'est plus facile de faire les calculs de distance. (R le rayon, P le périmètre = 2 Pi x R)
Si on adopte la stratégie la plus simple : le maire part du centre et rejoint un habitant du périmètre, puis il fait le tour du cercle.
Les N habitants parcourent exactement NxR unités de distance
Le maire parcourt exactement P unités de distance + 2
Donc la distance totale c'est juste : D = NxR + 2xPi x R + 2
Le maire pourrait être plus malin et employer des "messagers", mais il semble que ça ne diminue pas le parcours total ?
Ou alors en calculant des chemins sur des cordes du cercle plutôt que strictement sur le périmètre ?
PS. Si je devais écrire un programme de simulation, il faudrait sans doute que je représente le jeu par un graphe complet. Ce qui change du voyageur de commerce ou seulement certaines routes sont autorisées.
On ne peut aller plus vite que l'écho, donc le temps est forcément plus grand que $\frac{2d_m}{v}$, avec $d_m$ la distance entre le maire et le voisin le plus éloigné.
Cordialement.
Domi
On peut y croire :-D
Bon courage à ceux qui cherchent .
Domi
Je suis maintenant convaincu que la réponse au problème est simple c'est à dire que quelle que soit la position du maire dans sa commune carrée, il ne devra jamais parcourir plus de $2+\sqrt{2}$ et qu'à partir d'un nombre très faible d'habitants (disons $1+4$), il ne parcourra pas plus de $2\sqrt{2}$ .
Il y a sûrement une preuve pas trop compliquée de ce résultat mais je n'en vois pas le début :-S
Merci d'avance pour vos réponses .
Domi
On a tous du mal à lâcher un problème qui nous a passionné un bon moment, surtout quand il y manque une conclusion apparemment accessible Avis aux amateurs.
Domi.
Quelle que que soit la fonction.
Quels que soient les nombres.
Quelles que soient les droites.
J’ai toujours fait beaucoup de fautes d’orthographe mais je n’ai pas d’ambition littéraire, j’essaie simplement d’éviter les grosses bourdes par respect pour le lecteur. Les leçons du professeur Chaurien ne m’intéressent que lorsqu’elles font progresser le problème vers sa solution.
Domi.
Je rate sans doute une astuce mais je ne vois pas comment réunir tout le monde en mairie en le temps $2 + \sqrt 2$ dans le cas où on a quatre habitants plus le maire, les quatre sommets $A,B,C,D$ étant habités et le maire demeurant hors des côtés et des diagonales.
Si, pour tout couple $(I,J)$ de sommets distincts du carré $ABCD$ , $\Delta IJ:= MI+MJ-IJ$ (qui est positif), je trouve que le temps minimal est $2 + \sqrt 2 +$ inf des $\Delta IJ$. Or l'inf des $\Delta IJ$ n'est nul que si $M$ est sur une diagonale ou un côté.
A te lire et bien sûr merci pour tes problèmes
Amicalement
Paul
Tu as raison Paul, il est clair que le problème est vraiment complexe et la position du maire un point « central ». J’ai toujours tendance à croire sans certitude que le cas du maire + 4 habitants reste un cap sans pouvoir l’expliquer. J’ai aussi commencé à regarder des variantes plus simples en plaçant par exemple les points sur un quadrillage sans conclure pour le moment. Je te tiens au courant si certaines pistes m’inspirent un peu plus et j’attends les tiennes bien sûr 😊
Merci de t'intéresser au problème.
Domi.
Pour compléter le message d’hier soir, quelques autres pistes à explorer si tu n’es pas sujet au vertige
J’avais proposé sur un autre site une variante dans laquelle les habitants étaient situés au sommets d’un polygone régulier et le maire au centre. Le résultat n’est pas complètement évident avec une dichotomie selon la parité du nombre d’habitants : https://www.ilemaths.net/sujet-la-tournee-de-la-maire-789409.html. Une autre variante possible que je n’ai pas encore testée serait de placer le maire sur un des sommets du polygone. Il me semble en tout cas que le problème proposé initialement est trop complexe pour être abordé d’emblée dans sa totalité.
Domi
PS. Si ça t’intéresse, l’exercice original et ses "solutions" : http://www.diophante.fr/problemes-par-themes/i-trajets-optimaux/3776-i130-la-reunion-du-maire
j'espère que j'aurai le courage de lire tes documents.
J'ai calculé le pire des cas dans la configuration dont je m'occupe: $5$ points, $ABCD$ convexe, $M$ dans $ABCD$.
Je trouve une horreur:
$(2+\sqrt 2) +\delta$ où
$\delta= \sqrt{ \dfrac { 9-3\sqrt { 2} - 2 \sqrt{ 10-6 \sqrt {2}}} { 2} } -1$.
A bientôt
Paul
Si je comprends bien, il existe trois états possibles pour chaque villageois : chez lui, en mission d’information, chez le maire. Tous les villageois savent où habitent tous les villageois et peuvent déterminer en se rendant au domicile d’un villageois s’il est chez lui ou pas. Un villageois peut dire à un autre qu’il va chez le maire ou part en mission d’information avec éventuellement des précisions stratégiques. Lorsque deux villageois se rencontrent ils peuvent partager toutes les informations qu’ils ont. C’est un problème sacrément complexe ! Ou j’ai mal compris le problème, chaque village a un plan d’information optimal et on cherche la pire configuration de village.
"chaque village a un plan d’information optimal et on cherche la pire configuration de village" : c'est bien ainsi que j’interprète le problème.
En effet Paul et Philou, comme je le disais dans le message précédent le problème est vraiment complexe et le site Diophante a proposé l’exercice un peu légèrement. Toujours est-il qu’il y a des variantes vraiment intéressantes, j’en ai déjà proposées deux et Paul s’est intéressé au cas de quatre habitants plus un maire non centré (je n’ai pas encore vérifié sa solution). On peut bien sûr proposer d’autres variantes plus faciles à résoudre qui pourraient débroussailler le problème.
Une question bête : si on échange la position du maire avec l’un des habitants, la durée du parcours minimal est-elle la même ?
Domi
PS : merci pour la participation
A propos de la "question bête":
j'intuite, sans l'ombre d'une preuve, que si l'on parle du cas le pire, alors la durée du parcours minimal ne dépend pas de qui est le maire.
En revanche, en général, la durée du parcours minimal dépend de qui est le maire:
Exemple à $4$ habitants $A,B,C,D$ dont le maire:
$ABC$ équilatéral de centre $O$, $B'$ milieu de $[AC]$, $D$ à l'intérieur de $AOB'$;
Si le maire est $A$ ou $D$, alors la durée du parcours minimal est le périmètre de $ABD$;
Si le maire est $B$ ou $C$, alors la durée du parcours minimal est le périmètre de $BCD$.
Or le périmètre de $BCD$ excède strictement celui de $ABD$.
A plus
Paul
PS: le $\delta$ de mon précédent message est trop laid! Soit il est simplifiable, soit il est faux. Je m'occupe de lui!
Le pire des cas est réalisé quand la plus courte des lignes rouges et bleues est maximale.
Ce n'est pas facile a priori
Domi
Dans le pire des cas, $M$ est sur une médiane du carré (pour des raisons de symétrie), ni trop près d'un côté ni trop près d'une diagonale des diagonales.
Il y a un seul "pire $M$" dans $AOB$ ($O$ := centre du carré): c'est le $M$ qui réalise $MA+MB-AB=MA+MC-AC=MB+MD-BD\ \ (=\delta)$.
C'est lui qui maximise le min de mes $\Delta IJ$.
La valeur que j'ai donnée de $\delta$ est bien fausse! La nouvelle, à peine moins laide, est environ $0,07142$. Pas grand chose comparé à $2+\sqrt 2$ !
Je rappelle que le cas Maire+4 a été résolu.
Pour le cas Maire+5, plusieurs configurations ont été données (et perdues) qui montraient que dans le pire des cas, la borne $2+/sqrt 2$ était dépassée mais le pire n'était pas précisé.
J'espère l'avoir trouvé, mais ...Domi et Marco ont l'art de défaire mes croyances!
Notations:
$ABCD$ est dans le premier quadrant et $A$ est l'origine.
$F$ est le symétrique de $E$ par rapport à $(AC)$
$XYZT$ est le périmètre du quadrilatère $XYZT$
Je pense que $E$ réalise le pire des cas lorsque $ADEB=ACEF=ACED$ (**).
Géogèbra me dit qu'alors ces trois nombres sont $3,47331049...$ (tandis que $AECD=3,5200...$) et que les solutions de (**) sont au nombre de quatre. L'une d'elles - $E_1$ - est $(0,445329..; 0,8265..)$. Les autres sont les sommets du rectangle dont un sommet est $E_1$ et dont les axes de symétrie sont les diagonales de $ABCD$.
Quant au cas Maire+6, je verrais bien le(s) même(s) $E$ (et $F$) avec deux habitants en $C$.
Au moins, je relance le schmilblick.
Amicalement
Paul
Domi
@i.zitoussi: tu galèjes! Crois-tu que si je vise quelqu'un de précis je vais donner son nom (ou pseudo) en pâture sur le forum? Au mieux je vais chez les flics et leur dis mes soupçons. A ce propos, pour qui l'ignorerait, on ne risque rien (en principe) à raconter aux flics des soupçons, serait-on un total affabulateur. En revanche, devant la justice -heureusement- on ne peut dire n'importe quoi sans risquer de sanction.
Mon message est clair: c'est une conjecture, ni plus, ni moins, d'où le point d'interrogation. Chacun sait que le cercle familial n'est jamais, a priori, exclu de tout soupçon et nous sommes peu ou prou une grande famille. Je souhaite évidemment que soit infirmée ma conjecture. Peut-être, dès que j'aurai posté, je vais me faire reprocher de n'avoir pas lu tel ou tel message qui démontre l'ineptie de ma conjecture. Il est vrai que je ne suis pas tous les fils!
@Domi: Ravi de te retrouver
Cordialement
Paul