Tous chez le maire

Domi · May 2017

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.

Champ-Pot-Lion · May 2017

Salut

Si je comprends bien, il s'agit de trouver un arbre couvrant minimal ? Est-ce de ça dont il s'agit : https://en.wikipedia.org/wiki/Steiner_tree_problem ?

edit : Non, ce n'est pas ça, mais ça me semble lié.

Domi · May 2017

Il y a de ça , on peut aussi penser aux diagrammes de Voronoï ou à la triangulation de Delaunay , ...

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 .

depasse · May 2017

Bonjour Domi,

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

Domi · May 2017

Bonjour 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

gerard0 · May 2017

Domi,

comment obtiens-tu moins de $2\sqrt 2$ si le maire et ses administrés sont chacun sur un coin du carré ?

Cordialement.

Domi · May 2017

@Gérard

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

Siméon · May 2017

On montre assez facilement que dans le pire des cas, le temps minimal pour regrouper les $n$ villageois est $2\sqrt 2 + O(n^{-1/4})$, ce qui donne déjà la limite $2\sqrt 2$ quand $n\to\infty$.

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}.
$$

gerard0 · May 2017

Ah, je n'avais relu que ton énoncé en italique.

Domi · May 2017

@Simeon : j'ai du mal à voir comment caractériser la pire des situations même si la limite $2\sqrt{2}$ semble parfaitement crédible ( c'est vraiment simple ? ) . Je laisse les variantes probabilistes aux amateurs ( j'aime bien lire les solutions ) .

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

v13000 · May 2017

Je ne sais pas si ca aide beaucoup, mais j'ai essayé d'imaginer l'algorithme pour prévenir chaque habitant dans le temps le plus court.

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

Siméon · May 2017

@Domi, il n'est pas nécessaire de caractériser le pire des cas. Il suffit de trouver un algorithme qui donne le temps annoncé dans tous les cas.

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

Domi · May 2017

@V13000 : J'avais aussi commencé à regarder dans ce sens en cherchant la pire des dispositions pour une boucle de 9 points correspondant au parcours du maire ( pour les 200 points du problème initial ) en espérant que les adjoints visités finissent le travail correctement . Mais ce problème est loin d'être évident : quelles dispositions de 8 points dans un carré ( plus le maire au centre ) rendent maximale la plus petite des boucles passant par tous ces points ? On y perd vite son latin mais c'est vraiment intéressant . On admet bien sûr que chaque habitant a toutes les données et agit au mieux .
@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

v13000 · May 2017

J'ai aussi exploré le cas des habitants équidistribués sur le périmètre d'un cercle, ou même d'un carré.

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.

pourexemple · May 2017

Salut,

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 · May 2017

@V13000 : il me semble que si on répartit les villageois sur le bord du carré on ne peut pas dépasser une durée totale de $2+\sqrt{2}\approx3,41$ . Sur un cercle de diamètre $1$ c'est encore moins performant , on atteint au mieux $1+\frac{\pi}{2}\approx 2,57$ . Dans les deux cas on ne ne fait pas mieux que le maximum déjà atteint avec quatre personnes placés aux quatre coins du carré : $2+\sqrt{2}$ . Est-ce vraiment le maximum absolu ?

Domi

Domi · May 2017

Je n'ai pas l’intention de monologuer mais ce $2+\sqrt{2}$ me semble une bonne limite . On peut considérer par exemple que le parcours du maire est supérieur ou égal à celui de n'importe quel autre villageois . Il me semble ( je n'ai pas vérifié ) que si on ajoute un point dans l'enveloppe convexe des points visités par le maire on peut réduire la durée de son parcours . Bien sûr il peut y avoir des villageois à l'extérieur de l'enveloppe et il faudra alors considérer d'autre choses ( des symétries ? ) . Bref ce problème n'est sûrement pas facile mais il y a peut-être une solution simple .

On peut y croire :-D

Bon courage à ceux qui cherchent .

Domi

Domi · November 2018

Désolé de revenir sur cette vieille question.

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

Domi · July 2023

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.

Chaurien · July 2023

Quel que soit le polynôme.
Quelle que que soit la fonction.
Quels que soient les nombres.
Quelles que soient les droites.

Dom · July 2023

En DEUG 1, la (géniale !) prof de probabilités avait écrit quatre phrases du même genre. Cela a été la clef pour moi (j’espère ne plus avoir commis l’erreur…).

Domi · July 2023

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.

depasse · July 2023

@Domi ,

tu me reprends la tête.

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

Domi · July 2023

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.

Domi · August 2023

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

depasse · August 2023

Merci Domi,
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

philou22 · August 2023

Juste une petite idée de résolution algorithmique. Ce problème ressemble un peu au problème du voyageur de commerce. L’algorithme classiquement utilisé pour en trouver une bonne solution est un algorithme de recuit. Cependant ce qu’on cherche ici n’est pas une séquence mais une stratégie donc cela risque de ne pas faire avancer le problème.
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.

depasse · August 2023

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

Domi · August 2023

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

depasse · August 2023

Bonjour
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!

Domi · August 2023

J'ai jeté un coup d'œil au problème à 4 +1 habitants. Sauf erreur on peut résumer le problème au dessin suivant :

Image: https://les-mathematiques.net/vanilla/uploads/editor/nq/824qln60r6hm.png

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

depasse · August 2023

Je dirais même plus: il faut que les chemins rouge et bleu aient la même longueur pour être dans le pire des cas.
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$ !

depasse · October 2023

Bonjour à tous les participants de ce fil particulièrement endommagé par quelqu'abruti (un éconduit pour son arrogance?), et à tous.

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

i.zitoussi · October 2023

Peut-on savoir à quel abruti et à quel éconduit tu penses ? Ton dernier message n'est pas clair.

Domi · October 2023

Je pense que l'abruti en question est tout simplement celui qui nous a privé du forum pendant un bon moment en détruisant certains messages au passage .

Domi

depasse · October 2023

Bonsoir
@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

Tous chez le maire

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 12