Inscription / Connexion Nouveau Sujet

1 2 +


Niveau énigmes
Partager :

Trouver la maire

Posté par
Imod
08-08-18 à 18:19

Le titre est un clin d'œil à LittleFox

En fait c'est le problème qui a initié ceux des boucles et des triangles dans le carré . J'en ai encore plein d'autres du même genre , mais autant revenir à la source .

La maire habite au centre ( normal ) de sa commune qui est un carré de 20 km de côté , Elle veut réunir chez elle l'ensemble de ses habitants . Chacun  se déplace à 5 km/h et ne se déplace que lorsqu'il est au courant de la réunion . La maire part de chez elle et va prévenir un voisin qui lui même va se rendre chez la maire ou prévenir un nouveau voisin . Chacun ( maire compris ) continue ainsi sa balade jusqu'à ce que chacun se soit rendu chez la maire . En supposant que les habitants adoptent la meilleure stratégie mais qu'ils soient disposés de la pire des façons , combien de temps faudra -t-il attendre avant le début de la réunion ?

Pour le problème initial ( sur le site Diophante.fr ) il y avait 200 habitants , l'objectif me semble hors d'atteinte . Mais pour un petit nombre  d'habitants , ou un très grand nombre , il doit y avoir des choses à dire .

Allons-y

Imod  

Trouver la maire

Posté par
dpi
re : Trouver la maire 09-08-18 à 11:13

Bonjour,

Ton exercice est loin d'être un cadeau....
Pour la pire des façons ,j'ai pris mon exemple des fameux triangles.

 Cliquez pour afficher

Posté par
derny
re : Trouver la maire 09-08-18 à 11:43

Bonjour
Ne manquent-ils pas le nombre d'habitants ? Ou faut-il prendre ce nombre sur le schéma ?

Posté par
Imod
re : Trouver la maire 09-08-18 à 12:01

J'ai fait exprès de ne pas donner le nombre d'habitants . On peut en prendre 8 comme sur le dessin ou 200 comme pour le problème initial ( il me semble qu'on n'aura pas de réponse définitive dans un cas comme dans l'autre ) .

Ce qui m'intéresse dans l'exercice c'est qu'on voit bien qu'il y a un seuil ( pour la densité en habitants ) au delà duquel le temps va commencer à diminuer pour tendre vers une limite . En bref il semble amusant de traiter les premiers cas : 1 , 2 , ... habitants puis trouver le point d'inflexion et si possible la limite .

Je sais , ça fait beaucoup de questions .

Une remarque qui simplifie la rédaction , on peut supposer que le maire est le dernier rendu et chercher la longueur de son parcours ( dans un carré de côté 1 par exemple ) plutôt que la durée de son périple .

Ce ne sont que des suggestions , chacun peut apporter sa pierre à l'édifice

Imod

PS : je ne pense pas que le blankage soit indispensable  .  

Posté par
carpediem
re : Trouver la maire 09-08-18 à 13:35

salut

deux remarques :

si on suppose la vitesse des habitants constante et identique alors on se ramène à simple pb de distance ... puisqu'alors la durée sera proportionnelle à la distance ...

et si on commençait déjà avec ton graphique : quel est le trajet minimal pour que tous soient prévenus et soient rendu à la mairie au plus tôt ?

car il me semple qu'il y a "plus court" et simplement pour tenter de dégager une stratégie ...

Posté par
dpi
re : Trouver la maire 09-08-18 à 14:27

Bonjour à tous,

Je propose qu'on garde 6  habitants (et non 8 ) disposés dans le cas
le plus compliqué  suivant et qu'on donne le meilleur circuit.

Trouver la maire

Posté par
dpi
re : Trouver la maire 09-08-18 à 16:58

Pour le moment
1 =5h40
2=11h20
3=11h20
4=13h 40 ???
5=11h10
6=11h10
Rien de très observable

Posté par
carpediem
re : Trouver la maire 09-08-18 à 17:05

et le trajet du maire ?

je ne comprends pas tes temps ... et comme je l'ai dit à vitesse constante et identique alors en notant M le maire je propose le trajet suivant :

M prévient 1 puis 3 et rentre à la mairie

1 prévient 4 et vont à la mairie en prévenant 5

3 prévient 2 et vont à la mairie en prévenant 6


enfin pourquoi ne pas s'emmerder avec un carré unité plutôt qu'avec tout autre carré ?

donc autant prendre un carré unité et une vitesse de 1 et alors ce n'est qu'un pb de trajet minimal ...

Posté par
Imod
re : Trouver la maire 09-08-18 à 17:08

Ne grillons pas les étapes , 6 c'est déjà beaucoup .

Et fixons bien le vocabulaire , je compte le maire parmi les habitants , il y en a donc 7 sur ton dessin .

Plus prudemment en notant n le nombre d'habitant ( maire compris ) et L la pire distance distance qu'il aura à parcourir ( dans un carré de côté 1 ) :

n=1 \rightarrow L=0

n=2 \rightarrow L=\sqrt{2}

n=3 \rightarrow L=2\sqrt{2}

n=4 \rightarrow L=1+\sqrt{2}

Je ne suis même pas sûr du dernier résultat

Imod

Posté par
dpi
re : Trouver la maire 09-08-18 à 17:28

>carpediem
je répondais à l'idée de Imod de trouver une "loi" en fonction de nombre d'habitants;
Ainsi pour 1  le temps est 5h40
Ensuite 2,3,  etc...Bien sûr c'est le temps le plus long qui est retenu car il masque les autres.

Posté par
dpi
re : Trouver la maire 09-08-18 à 17:32

A noter aussi que certains habitants préviennent leur "voisin" pendant que le maire continue son périple.
Effectivement on travaillera mieux en unités

Posté par
Imod
re : Trouver la maire 09-08-18 à 17:33

Il y a pas mal de croisements

Il y a pas mal de fautes de frappe dans mon précédent message qui répondait à celui de Dpi ( 14.27 ) . J'espère qu'il est quand même compréhensible .

Imod

Posté par
carpediem
re : Trouver la maire 09-08-18 à 17:56

sans vouloir être pénible (désolé) je conseillerai de ne pas "compter" le maire dans les habitants ... car avec ta liste je suis toujours en train de soustraire pour avoir les habitants  mais bon ...

et enfin (re désolé) il peut être intéressant pour le plaisir d'avoir le temps minimal comme tu nous le demandais

car par exemple avec l'exemple de dpi et ma réponse la maire retourne à la mairie  avant que tous n'y soient et la réunion ne peut toujours pas commencer

Citation :
n = 1 \rightarrow L=\sqrt{2} et la réunion peut commencer

n = 2 \rightarrow L = 2\sqrt{2} et la réunion peut commencer

n=3 \rightarrow L = 1 + \sqrt{2} et la réunion peut commencer


pour ce dernier cas je ne vis pas comment tu peux ne pas en être sur fort humblement ...

Posté par
LittleFox
re : Trouver la maire 09-08-18 à 18:15


Je suis pour ne pas compter la maire non plus.

Pour le n=3 -> L = 1+\sqrt{2}, j'ai testé différentes positions sans réussir à faire pire ... ce qui n'est pas une preuve .

Ensuite n=4 -> 2+\sqrt{2}?

Posté par
Imod
re : Trouver la maire 09-08-18 à 18:25

On peut supprimer la maire de l'ensemble des habitants , pas de problème il suffit de se mettre d'accord

On peut toujours supposer que le parcours de la maire est le plus long . En effet si l'un des administré avait un parcours plus long , il suffirait que la maire prenne sa place au cas où elle l'aurait prévenu directement sinon par induction , la place de celui qui l'a prévenu , ........

Pour n=3 , j'ai vraiment un doute mais je doute de tout

Imod

Posté par
carpediem
re : Trouver la maire 09-08-18 à 18:35

à noter que pour n = 3 (+ la maire) on peut trouver un trajet plus court :

Trouver la maire

la maire M prévient E puis A et ils retournent à la mairie

et E prévient C et ils retournent à la mairie


... mais il faut attendre le retour de E et C avant de commencer la réunion

le trajet M-E-A-M est 1 + \dfrac {\sqrt 2} 2 mais le trajet M = E-A-M est \dfrac {1 + \sqrt 2} 2 et le trajet E-C-M est \dfrac {\sqrt 5 + \sqrt 2 } 2

Posté par
Imod
re : Trouver la maire 09-08-18 à 18:36

@LittleFox : je suis sur le même résultat pour n=4 mais on voit très vite que la situation se complique . On continue à augmenter la longueur du parcours mais de moins en moins : va-ton finir par décroitre ????

Imod

Posté par
dpi
re : Trouver la maire 10-08-18 à 08:43

Bonjour,

Pour mon type de difficulté (voir 5 et 6 ) j'arrive à cela:
Les parcours  plus courts sont masqués par le plus long.

Trouver la maire

Posté par
Imod
re : Trouver la maire 10-08-18 à 09:53

@Dpi : pour n=3 sur ton dessin on peut faire 1+\sqrt{2} , le pion 3 choisissant de prévenir 2 plutôt que de rejoindre la mairie .  Par contre , sur le même dessin , si on met 3 avec 2 alors on retrouve un trajet de la maire égal à 2\sqrt{2} ( j'avais raison de douter )  .

Imod

Posté par
Imod
re : Trouver la maire 10-08-18 à 10:03

D'ailleurs pour n quelconque , peut-on trouver une configuration où le parcours de la maire est supérieure à 2\sqrt{2} ?

Imod

Posté par
dpi
re : Trouver la maire 10-08-18 à 10:27

Suite
Il semble que la multiplication des habitants et le bouche à oreille limite à 22

Posté par
LittleFox
re : Trouver la maire 10-08-18 à 10:33

@ dpi
Pour n = 3, il y a un parcours plus court si la maire va d'abord vers l'habitant 3.
Pour n=4 j'ai la même situation.
Pour n > 4, je n'ai pas encore cherché .

Posté par
LittleFox
re : Trouver la maire 10-08-18 à 10:37

Ah oui tiens, pour n >= 2, si on groupe les habitants en 2 groupes alors on obtient 2\sqrt{2}.
Pour n=4 il semble que le parcours soit plus long. Mais on perds cet avantage s'il y a plusieurs habitants dans un des coins.

Posté par
dpi
re : Trouver la maire 10-08-18 à 11:04

>Littlefox
Pour 3  le maire a trois parcours possibles :
Si il débute par 3 il laisse 3 avertir 1 (ou 2)  pendant qu'il va prévenir 2 (ou 1)
On a  M =2/2+1+2/2 soit 1+2
l'habitant n'à que 1+2/2 mais il a attendu le maire 2/2
Les deux parcours sont égaux donc pour 3  nous avons 1+2

Posté par
Imod
re : Trouver la maire 10-08-18 à 11:10

Correctif : pour n=4 la pire situation donne bien 2+\sqrt{2} .

Peut-on faire encore pire en augmentant n ?

Imod

Posté par
dpi
re : Trouver la maire 10-08-18 à 11:15

>Imod
Voir mon avis de 10h27

Posté par
Imod
re : Trouver la maire 10-08-18 à 11:35

Oui , je crois qu'on peut admettre sans problème :

n=1 \rightarrow L=\sqrt{2}

n=2 \rightarrow L=2\sqrt{2}

n=3 \rightarrow L=2\sqrt{2}

n=4 \rightarrow L=2+\sqrt{2}

Pour n=5 , peut-on faire pire que 2+\sqrt{2} ?

Imod

Posté par
dpi
re : Trouver la maire 10-08-18 à 12:20

A noter que pour 3 (remarque de Littlefox)  on trouve 1+2

Posté par
Imod
re : Trouver la maire 10-08-18 à 12:27

La réponse est oui

Une question intermédiaire : on met 4 habitants dans les coins , où placer le cinquième pour retarder au maximum la réunion ( aux symétries près ) ?

Imod

Posté par
Imod
re : Trouver la maire 10-08-18 à 12:30

@Dpi : relis le message de LittleFox ( 10H37 ) .

Imod

Posté par
dpi
re : Trouver la maire 10-08-18 à 12:34

Pour vérifier que pour 7 on reste dans 22
Je reste dans la configuration de 6 et je fais faire à 2 (ou à 3 )un détour de 0.5+0.5.
au lieu de 2/2 (parcours vert +bleu )  .
Si mon nouvel habitant était positionné dans un autre quart c'est un autre habitant qui
aurait fait le même détour le parcours les plus long reste 22

Posté par
Imod
re : Trouver la maire 10-08-18 à 13:39

Je pense aussi que 2\sqrt{2} est la limite mais on ne l'atteindra pas si facilement . Par exemple avec 8 habitants placés par groupe de 2 dans chaque coin , il me semble qu'on ne fait pas mieux que 2+\sqrt{2} .

Imod

Posté par
dpi
re : Trouver la maire 10-08-18 à 14:39

Merci Imod
En me posant cette question tu m'as fait aussi améliorer pour  4 : 22
pour 8 voici par exemple:

Trouver la maire

Posté par
LittleFox
re : Trouver la maire 10-08-18 à 15:06


Pour n=8, je suis d'accord avec dpi.
Par contre pour n=4, 2+\sqrt{2} > 2\sqrt{2}.

Posté par
dpi
re : Trouver la maire 10-08-18 à 15:42

Je disais que pour 4 on reste aussi à 22

Trouver la maire

Posté par
dpi
re : Trouver la maire 10-08-18 à 15:45

mon bleu est mal orienté

Trouver la maire

Posté par
dpi
re : Trouver la maire 10-08-18 à 15:47

Donc  on est mal...

Posté par
dpi
re : Trouver la maire 10-08-18 à 15:52

on reste sur 8 h43  

Posté par
Imod
re : Trouver la maire 10-08-18 à 16:03

J'ai l'impression que ton 1 part dans deux directions différentes

Imod

Posté par
carpediem
re : Trouver la maire 10-08-18 à 19:46

bon je vois que les neurones ont cogité !!

moi c'est les muscles qui ont fumé : j'ai joint le plus rapidement possible du mélange à du ciment et de l'eau pour faire du béton

et ne voyant pas de réaction à mon msg de 18h35 j'en déduis que vous en êtes restés au parcourt le plus pessimiste du maire indépendamment du début de la réunion ...

en tout cas pour tous ces résultats ...

Posté par
dpi
re : Trouver la maire 11-08-18 à 07:48

Bon week end (prolongé ou normal)

Il y a même un constatation qui permet d'extrapoler:
Ma confusion entre 4 et 8 donne le fil....
Pourquoi le parcours de 8 soit 2 2 est-il plus court que celui de 4 soit 2+2 ?
Tout simplement par le "bouche à oreille" ; dans le cas de 4 ,le maire ne dispose que
de deux rapporteurs alors que pour  8 ,il dispose au moins d'un de plus.
On pourrait même dire que pour un plus grand nombre on aurait une "explosion"
en chaîne . Mais ici de vitesse V=1 d'où   2V2

Posté par
Imod
re : Trouver la maire 11-08-18 à 12:47

Je suis complètement convaincu que la distance limite 2\sqrt{2} va être atteinte .

Il reste quand même deux questions :

1°) A partir de combien d'habitants la distance commence-t-elle  à diminuer ?

2°) Avec combien d'habitants  atteint-on enfin la borne  indépassable de  2\sqrt{2} ?

Imod

Posté par
dpi
re : Trouver la maire 11-08-18 à 15:26

Le cas le plus défavorable* est 4 habitants aux 4 coins  par la suite on reste figé à 22 ce qui est "logique" car quel que soit le nombre d'habitant  ,et le nombre de messager(s) , il faudra bien couvrir couvrir les deux diagonales.

nous avons donc  2,2,2,2+2,22....................2

* la courbe est  perturbée  pour ce cas

Posté par
dpi
re : Trouver la maire 11-08-18 à 15:30

mauvais clics:
1             2             3          4            5.................... n
2  22   22  2+2   22..........................22

Posté par
Imod
re : Trouver la maire 11-08-18 à 19:04

Ce n'est pas si simple Dpi

Déjà le cas n=5 commence à être compliqué , je ne suis pas tout à fait sûr que l'on puisse faire pire que 2+\sqrt{2} mais il est clair qu'on peut dépasser 2\sqrt{2} .

Imod

Trouver la maire

Posté par
dpi
re : Trouver la maire 12-08-18 à 08:18

Pourtant,

Dans ton cas il suffit de dérouter mon cas 5 d'hier:
Maire 0.25 +0,559+1+0.707 =2.5161
1            0.25+0.559+1+0.707 = 2.5161
2            0.25+0.901+0.707 =1.858
3            0.25+0.559+1+0.707 =2.5161
4            0.25+0.559+1+0.707= 2.5161
5           0.25 +0.901+0.707 =2.151
Tous ces parcours inférieurs à 22

Trouver la maire

Posté par
dpi
re : Trouver la maire 12-08-18 à 08:23

Pour le 5 c'est encore plus court : 0.25+0.901+0.707 = 1.858 (comme 2 puisque c'est lui
qui est chargé de la convoc...)

Posté par
Imod
re : Trouver la maire 12-08-18 à 09:47

En effet c'est bon

Je n'arrive pas à me convaincre que ça va marcher dans tous les cas avec 5 habitants : il manque un argument

Imod

Posté par
carpediem
re : Trouver la maire 12-08-18 à 14:28

je comprends pas les calculs de dpi de 8h18 ...

par exemple pour 1 sur son graphique : je vois 1 +r(2)

que signifie 0,25 + 0,559 + 1 + 0,707 ?

Posté par
dpi
re : Trouver la maire 12-08-18 à 15:18

>carpediem

J'aurai pu donner les calculs mais cela se résume à :

M-->5    0.25   (1/4)
5--->1     \sqrt{0.25²+0.5² = 0.559
1--->3       1
3----M    2/2 =0.707


autre  cote:  2-->M      \sqrt{0.35²+0.25²}

1 2 +


Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !