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

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

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

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