En utilisant la stratégie: On s'occupe des habitants de haut en bas. Pour chaque habitant H, on prend comme messager l'habitant (ou la maire) M qui aura parcouru le moins de chemin en arrivant à H (les distances étant cumulées depuis le centre du cercle).

Calculée par ce petit programme :

 Cliquez pour afficher

from cmath import pi, exp

def solve(n):
   Hs = [exp(2*pi*1j*k/n) for k in range(n)]
   Hs.sort(key=lambda p:abs(1-p))
   
   Pos = [(0,0)]
   for j,h in enumerate(Hs,1):
      best=(0,2*pi+2)
      for i in range(len(Pos)):
         if Pos[i][0]+abs(h-Pos[i][1]) < best[1]:
            best = (i,Pos[i][0]+abs(h-Pos[i][1]))
      Pos.append((best[1],h))
      Pos[best[0]] = (best[1],h)
      print(str(best[0]) + " move to " + str(j) + ". Total :" + str(best[1]))
   return max(h[0]+abs(h[1]) for h in Pos)
      

Bonjour LittleFox

Si j'ai bien compris ta stratégie , on parcourt le cercle de voisin à voisin . Avec le rayon 1 on devrait aboutir à une distance et non : c'est la première idée qui vient à l'esprit . Après on se rend vite compte qu'en profitant de la mobilité de chaque habitant visité , on peut sauter certains points et gagner ainsi en durée de parcours . Je ne sais pas si on peut échapper à la limite  

Il me semble intéressant de chercher les distances minimales pour les petits nombres d'habitants , il y a peut-être un peu d'arithmétique là dessous .

Merci pour l'intérêt poté au problème

Imod

Oui, c'est bien . J'ai testé différentes équations et ce n'est pas la bonne qui est affichée . Mais bon est plus grand que 8. Donc ce n'est pas du tout la même limite que celle affichée . Mea culpa.

Je tenterai peut-être une recherche exhaustive pour les petits nombres d'habitants mais je suis plutôt convaincu que la stratégie proposée est plutôt bonne. (Mais bon j'étais convaincu qu'on pouvait pas mettre L+1 pièces dans un rectangle de longueur L ).

Comme pour le problème précédent , on va vite ne plus rien comprendre si on ne fixe pas les données

Le rayon est 1 , le nombre d'habitants n ( sans la maire ) et L(n) la distance parcourue  par la maire supposée arriver en dernier avec la meilleure stratégie possible .

Quelles sont les premières valeurs de L(N) ?

Imod

J'ai commencer à regarder en détail les premières valeurs de n ( Nombre d'habitants maire exclue ) . On voit très vite qu'on a deux sous-suites différentes pour n pair ou impair mais plus curieusement le plus grand parcours L semble borné par   et pourtant il n'y a plus de carré dans l'histoire

Je donne les 6 premières valeurs pour vérification , les suivantes viendront dans la journée .

Je n'ai représenté que le parcours de la maire , on devine aisément les autres .

Attention : pour simplification , je me suis placé dans un cercle de diamètre 1 , j'ai enlevé l'allez-retour au centre pour le calcul de L et j'ai noté .

Imod

La suite promise

Contrairement à ce que j'avais annoncé , le parcours limite de la maire semble égal à un quart de cercle augmenté de la diagonale d'un quadrant :



Imod

c'est quoi a1, a2, ... ?

an=180/n en degrés ( je l'avais précisé dans le message précédent ) .

Imod

Bonjour
Pour 12 il me semble à première vue qu'on peut faire mieux.

Bonjour Derny

Tu peux dire comment faire mieux avec 12 habitants ( donne simplement les numéros des points visités par la maire ) .

Imod

S'il n'y a pas d'erreur dans les premières configurations , on peut conjecturer la suite :

Imod, c'est sûrement simple mais je ne comprends pas ton tableau. A quoi correspondent les colonnes ?

Pour 12, 1_2_4_7 t'irait ?

Oui , ça me va très bien

Je trouvais bizarre de n'obtenir que des petites parts sauf une .

Les colonnes du tableau étaient censées indiquer le nombre de parts de taille 1 , 2 , ... mais je me suis complètement emmêlé les pinceaux ( c'est la première fois j'envoie un tableau ) . Voilà ce que donne les premières lignes ( j'ai corriger la dernière pour qu'elle cadre avec ta remarque ) :

Salut, j'ai fait un petit programme (j'ai déjà entendu ça ) qui teste tous les chemins possibles. Et s'il est d'accord avec le message de Imod du 19-08-18 à 16:35 jusqu'à n=7, après il trouve de meilleures solutions. Par exemple :

On a :



Je suspecte que ça marche encore avec 11 mais à un moment la longueur en noir à droite va être plus longue que la longueur en rouge et il faudra changer de stratégie. Mais au final la maire va toujours faire un saut de 1 puis le saut le plus long possible. Et donc on aura toujours la solution

Je postule donc que la limite sera 1 pour n allant vers l'infini.

Ok, j'ai testé avec n grand (20) et ça ne marche plus .

Il est très très sympa le message mais la référence que tu cites est déjà démodée

C'est l'intérêt et le désagrément des problèmes ouverts , on va d'une joie à une peine jusqu'à parfois , de temps en temps : la délivrance

Imod

Désolé de ne pas avoir fait mes devoir le weekend .

Tous tes messages qui suivent reprennent cet erreur donc ce n'est pas si démodé que ça. A moins que la correction que je propose sois fausse. Pour reprendre la notation que tu propose voici les solutions que je trouve, à partir de n=8 elles sont meilleures:

h=1  : 1.
h=2  : 1->2.
h=3  : 1->2.
h=4  : 1->2->3.
h=5  : 1->2->3.
h=6  : 1->2->3, 2->4.
h=7  : 1->2->3, 2->4.
h=8  : 1->2->3->4, 2->5.
h=9  : 1->2->3->4, 2->5.
h=10 : 1->2->4->5, 4->3, 2->6.
h=11 : 1->2->4->5, 4->3, 2->6.
h=12 : 1->2->3->4->5, 4->6, 2->7.
h=13 : 1->2->4->5, 4->6, 2 ->7.
h=14 : 1->2->4->6->7, 4->5->3, 2->8.
h=15 : 1->2->4->5->6, 4->7, 5->3,  2->8.
h=16 : 1->2->3->4->6->7, 3->5, 6->8, 2->9.
h=17 : 1->2->3->6->7, 3->5->4, 6->8, 2->9.

Correction:
*A partir de h=8 donc n=4 elles sont meilleures.

Correction bis:

h=13 : 1->2->4->5->6, 4->3, 2->7.

Bonjour,
j'ai manqué le coche c'était pas mal  bravo Littlefox

@LittleFox : j'ai simplement jeté un coup d'œil à ton tableau mais il me semble vraiment étrange

Tu as noté qu'il ne fallait pas se limiter à regarder les déplacements de la maire , il faut en effet vérifier que ses adjoints peuvent finir le travail .  Je suis complètement incompétent pour un traitement informatique de la chose , j'espère simplement qu'on peut deviner une règle simple dans les déplacements de la maire pour une explication qui soit dans mes cordes ( c'est pour cette raison que je me suis axé uniquement sur elle ) .

Il peut y avoir quelque chose de simple la-dessous

Imod



  

Après quelques essai, j'ai découvert que mes résultats plus haut étaient erronés pour h >= 14. Et j'obtiens la situation "simple" ci dessous :


Et donc la formule suivante avec tel que est maximum. est le nombre de mouvements le long du cercle avant de bifurquer.

Pour pair on obtient que est l'entier juste au dessous ou juste au dessus de .
Pour impair .


Pour grand, tend vers . Et tend vers . Ce qui correspond à faire 60° le long du cercle avant de bifurquer en face. Comme c'est beau .

Non LittleFox , ça ne va toujours pas , la maire peux avoir besoin d'effectuer plusieurs bonds supérieurs à 1 ( je rappelle que la maire est la dernière à retourner chez elle ). Un exemple critique relevé par Derny :

Imod

Oui, je n'exclus pas le cas de plusieurs bonds supérieurs à 1, simplement ma solution est meilleure sans

1->2->7
L = sin(a12) + sin(5*a12) = 1.225 < 1.466.

Tu peux vérifier que tous les autres chemins sont inférieurs ou égaux à celui de la maire :

1->2->3->6
2*sin(a12) + sin(3*a12) = 1.225
1->2->3->4->5
3*sin(a12) + sin(a12) = 1.035

Et tous les habitants ont étés avertis.

En effet , ça marche , bravo

En plus la stratégie de chacun est très simple et la limite complètement contre-intuitive .

Je suis toujours surpris par la richesse de ces petits exercices apparemment sans prétention . On verra si on peut trouver une suite intéressante .

Encore bravo !

Imod

Je n'aime pas trop demander aux autres de réaliser ce que je peux faire moi-même mais je suis vraiment une quiche en informatique

j'aimerais bien ( par simple curiosité ) voir les courbes L(h) pour h pair et impair .

Merci d'avance aux courageux

Imod

>imod

J'ai zappé celui-ci  ,par contre je pense que tu vas essayer la grille de derny qui
comme toi pose des exercices simples ,mais très astucieux.

Je suis déjà intervenu sur le fil en question , j'ai cherché , j'ai pas trouvé mieux que ce qui était déjà proposé , je suis passé à autre chose ...

Il y a des problèmes très chronophages , si on aime on ne compte pas mais comme j'ai une multitude d'autres choses sur le feu ...

En attendant je n'ai pas de réponse pour l'allure de L(h)

Imod

PS : ce n'est pas bien grave , je ferai ça à mes temps perdus .

Voici pour L(h) :



La courbe en vert est le maximum pour h pair, la jaune pour h impair. Et la courbe bleue est la limite pour h grand.

Pourquoi c'est si difficile de poster une image une fois qu'on en a déjà dans la conversation???

C'est bon , j'ai réussi à récupérer l'image et j'ai la réponse que je voulais , merci pour tes efforts contre les ( petites mais pénibles ) faiblesses du site

Imod