Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-05-2017 18:09:31

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

Tous cehz le Maire !

Bonjour à tous smile

Un problème proposé sur un site de jeux mathématiques qui me tracasse depuis un bon moment . Il  y a sûrement une façon astucieuse d'aborder la chose mais elle m'échappe complètement sad

Voilà le problème :  Le maire habite au centre de sa commune qui a la forme d'un carré de côté 1 . Il veut réunir tous les habitants chez lui ( 200 en tout ) . Chacun se déplace à la vitesse 1 et se met en mouvement dès qu'il est prévenu de la réunion . Le maire part de chez lui et va voir un voisin qui va se rendre chez le maire ou prévenir un autre voisin , le maire continue sa balade comme tous les habitants avertis . En supposant que chaque habitant agit au mieux dans la pire des configurations , combien de temps faudra-t-il attendre avant le début de la réunion ?

http://www.prise2tete.fr/upload/Vasimolo-maire.png

J'ai bien quelques pistes mais comme elles n'aboutissent pas , je laisse chacun s'exprimer librement .

Bon amusement smile

Vasimolo

  • |
  • Répondre

#0 Pub

 #2 - 15-05-2017 21:49:05

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Tous chez le Mair !

ca m'a l'air difficile, la complexité du calcul semble augmenter à chaque villageois rajouté.
Voici les pires cas que je trouve pour les premières valeurs (Ils ne sont absolument pas démontré, je raisonne juste sur mon intuition...)
n = 1 villageois:
Spoiler : [Afficher le message] on place le villageois dans un coin, t = sqrt(2)
Ca ça va...


n = 2
Spoiler : [Afficher le message] on place les villageois dans les coins opposés. Il faut visiter les deux, t = 2*sqrt(2)

n = 3
Spoiler : [Afficher le message] On place deux habitants dans des coins opposés et le troisième n'importe où.
En allant voir le villageois du coin le plus proche du troisième, puis le deuxième coin tandis que le premier villageois va chercher le troisième, on trouve t = 2*sqrt(2) dans le pire des cas



n=4
Spoiler : [Afficher le message] On place chaque habitant dans un coin
t = 2 +sqrt(2)


n=5
Spoiler : [Afficher le message] La ça devient sacrément complexe, et j'ai bien l'impression que t diminue.
Le pire cas que j'ai trouvé est:
1 villageaois dans chaque coin
1 villageois sur un bord situé à  0.30599 d'un coin
Je trouve alors t = 2.9374339761 > 2sqrt(2)
On trouve ce chemin en placant le villageois 5 tel que:
le chemin en commençant par lui puis en revenant de chaque côté et le chemin commençant par le coin le plus proche, puis par le villageois 5 puis le coin à l'autre bout soient de même longueur
Edit:
J'ai l'impression que décaler légèrement le coin le plus proche du villageois 5 ne fait qu'empirer la situation...


Je n'ai pas eu le courage d'aborder n=6...

 #3 - 15-05-2017 22:24:57

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

Tous cchez le Maire !

Personnellement  je n'ai pas trouvé mieux que [latex]2+\sqrt{2}[/latex] quel que soit le nombre d'habitants mais sans aucune idée de démonstration .

Vasimolo

 #4 - 15-05-2017 22:42:26

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Tous chez le Maaire !

Peux tu donner un exemple de répartition à 5 villageois qui donne 2 +  sqrt(2)?

 #5 - 15-05-2017 22:52:51

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

Tous chez le Maier !

Je ne prétends pas atteindre ce maximum avec 5 habitants ou plus , je me demande si on peut le dépasser .

Un exemple ?

Vasimolo

 #6 - 15-05-2017 23:23:36

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

tois chez le maire !

Non, avec 5 habitants, on peut toujours faire moins que ça.
Spoiler : [Afficher le message] Découpons le carré en 4 sous carrés. Supposons que chaque carré contienne au moins un villageois (il y en a donc un qui en contient 2)
- Le Maire va voir dans le carré avec deux villageois celui le plus près.
- Ce villageois va avertir le villageois du carré opposé. Dans le pire des cas, on a 2V2
Le Maire va voir le deuxième villageois du carré, chacun va chercher les deux derniers villageois des carrés restants.
Le pire des cas est 1/2 + V2/2 (aller chercher les deux premiers villageois) + V(1+1/4) + V2/2 (aller chercher le villageois le plus loin du deuxième récupéré et revenir).
Ce qui donne au pire 3.0322 < 2 + v2 = 3.41421

 #7 - 16-05-2017 08:25:33

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

Tous cehz le Maire !

diophante.fr

 #8 - 16-05-2017 09:36:48

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

tous vhez le maire !

Il me semble que quand n augmente, le résultat tend vers 2V2
Spoiler : [Afficher le message] Découpons notre carré en 16 rectangle. Il existe au moins un rectangle contenant 13 villageois, dans le pire des cas situé dans un coin.
Le maire va vers ce carré, déclenche un chaine d'avertissements dans ce rectangle, puis chacun des 14 va dans un carré (il y en a un qui devra en faire 2, en avertissant sur son chemin un autre carré). plus le nombre de villageois augmente, plus il est rapide d'avertir tout un petit carré très peuplé. on en déduit alors la limite....

 #9 - 16-05-2017 17:10:56

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

Tous chez lee Maire !

Je suis d'accord avec cette limite qui est clairement indépassable ( par en dessous ) car en disposant tous les villageois dans deux coins opposés on atteint les [latex]2\sqrt{2}[/latex] . Maintenant j'ai l'impression qu'on doit atteindre la limite assez vite ( avec une poignée d'habitants ) mais je n'ai pas d'argument .

Trouver la limite exacte pour 5 ou 6 habitants est aussi intéressant même si c'est difficile ( il y a pas mal de cas mad ) .

Merci pour la participation smile

Vasimolo

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete