Il va falloir que tu détailles un peu plus parce que si je mets tous mes points au même endroit alors il y a une seule distance qui est 0 peut importe n. Et qu'est-ce que tu appelles une position différente? Car il y a une infinité de position pour chacun de mes points et donc une infinité de positions peut importe n.

Bonjour, il est écrit : "Des points distincts".
Les positions différentes concernent les différentes positions des points les uns par rapport aux autres.
Bonnes recherches

Hmm, je dois changer mes lunettes alors, je ne vois aucun "distincts" dans ton premier post

Avec ce distinct alors ça devient plus intéressant pour les distances, si on utilise des polygones réguliers alors le nombre de distances différentes devient . Il y a probablement moyen de faire mieux.

Par contre pour les positions, je ne vois toujours pas. Considérons par exemple les points (0;0), (0;1) et (x;0). Pour chaque valeur de x on a une position différente (même en enlevant les rotations et mise à l'échelle). On a donc une infinité de positions pour n plus grand ou égal à 3.

Bonjour!
Si je comprends bien et si je commence par n=4:

Si les distances mutuelles de 3 des points sont égales, ils forment un triangle équilatéral.
Il semble évident qu'on ne pourra placer le quatrième point à cette même distance de chacun des 3 premiers et que la réponse est donc 2.

Ai-je bien compris la première question?
Merci à Derny.

Si si LittleFox, le titre est bien "des points distincts".
Pour bien poser le problème :
Pour n=2, d=1, p=1

Pour n=3, d=1, p=1 (les 3 pts sont les sommets d'un triangle équilatéral)

Pour n=4, d=2, p=3

  p1)_ les 4 pts sont les sommets d'un carré, d=2 (côté du carré ou diagonale)

  p2)_ les 4 pts sont les sommets d'un losange, d=2

  p3)_ les 4 pts sont les sommets d'1 tr équi + 1 pt au centre, d=2  

Merci d'avance à Derny s'il me confirme que j'ai bien compris la première question!

Oui rogerd (voir p3)_ )

Je m'amuse à mettre des titres qui sont trompeurs (voir "Nombres complexes" : Nombres complexes) du coup je n'ai pas fait spécialement attention au titre. Désolé

OK, donc la question 2) est combien de positions différentes ont un nombre de distances minimal.

Bonjour
>Littlefox
C'est vrai que j'ai un complexe avec la complexité de tes nombres complexes

>derny
Ici n'est on pas en présence des diagonales d'un  polygone  soit  n+n(n-3)/2 ?

par exemple pour  n = 13   il y a  78 distances différentes.

@derny
J'ai au moins deux autres positions pour n=4 :
- 4 sommets d'un pentagone régulier.
- les sommets d'un triangle équilatéral plus un point sur la bissectrice d'un des angles à un distance égale au côté du triangle du sommet correspondant (donc juste en dehors du triangle).

@dpi
En général pour n points il y a n(n-1)/2 distances à vérifier entre eux.

Pour n=5, je ne trouve qu'une seule configuration avec d=2 : les sommets d'un pentagone régulier.

Pour n=6, d=3, p >= 6:
- les sommets d'un hexagone régulier
- les 4 sommets d'un carré plus les troisièmes sommets des triangles équilatéraux posés sur deux côtés adjacents du carré.
- les 3 sommets d'un triangle équilatéral plus les 3 points sur les bissectrices de ce triangle et à une distance du sommet correspondant égale au côté du triangle.
- 5 sommets d'un hexagone régulier plus son centre.
- les 5 sommets d'un pentagone régulier plus son centre.
- Les 3 sommets d'un triangle équilatéral et les 3 milieu des côtés.
(>370s de calcul et beaucoup plus de temps pour analyser les 48 solutions potentielles, je m'arrête là...)

Pour n=7, d=3, p>= 2:
- Les sommets d'un hexagone régulier et son centre.
- Les sommets d'un heptagone régulier.
(L'espace de recherche devient très très grand...)

Bonjour
Pas mal LittleFox. Pour n=4 cela porte le nombre de positions à 5. Pour n=5 pas mieux. Pour n=6 cela fait donc également 5 positions différentes. Par contre, je n'ai pas compris ta phrase entre parenthèses. Pour 7 pas mieux. Même si "l'espace de recherche devient très grand", le nombre de solutions ne l'est pas à mon avis.
Le cas n=12 est intéressant. Je laisse chercher.

Puis on pourrait étendre l'étude à l'espace.

Pour n=6, 6 positions différentes pas 5. A moins que l'une de celles que j'ai donnée soit redondante? Pour moi, j'en ai 6 différentes.

Les phrases en parenthèses sont des commentaires sur le fait que mon programme commence à prendre du temps. Parce que oui, évidemment j'ai écrit un programme pour m'aider

On pourrait étendre à l'espace à dimension m, ce ne serait qu'une complication de plus (comme si ce n'était pas déjà compliqué)

Mon programme a une complexité de O(e^nm+d), donc ça devient difficile très très vite

Oui c'est 6.
Pour ton programme quel en est l'esprit ? Comment cherche-t-il ?

J'utilise un langage par contrainte (Prolog -> ECLiPse CLP):

 Cliquez pour afficher

:- lib(ic).

model(N,L,P,D) :- length(P,N), length(D,L),
   P = [(0,0),(1,0)|P_], D = [1|_],
   D $:: 1..N,
   sorted(D),
   isDists(P,D),
   ordered(P_),
   true.

isDists([],_):-!.
isDists([_],_):-!.
isDists([P|P_],D) :- isDists(P,P_,D), isDists(P_,D),!.

isDists(_,[],_):-!.
isDists(P,[P2|P_],D) :- P = (X,Y), P2 = (X2,Y2), DP $= (X-X2)*(X-X2) + (Y-Y2)*(Y-Y2), element(_,D,DP), isDists(P,P_,D),!.

ordered([]).
ordered([P]):- P = (_,Y), Y $>= 0.
ordered([P1,P2|P_]):- P1 = (X1,Y1), P2 = (X2,Y2), X1 $=< X2, (X1 $= X2) => (Y1 $=< Y2), ordered([P2|P_]).

solve(N,L,P,D) :- model(N,L,P,D), flatten2(P,P_), append(D,P_,DP), locate(DP,P_,1e-4,lin).

flatten2([],[]).
flatten2([P|P_],[X,Y|F]) :- P = (X,Y), flatten2(P_,F).

sorted([]).
sorted([_]).
sorted([D1,D2|D_]):- D1 $=< D2, sorted([D2|D_]).

Bonsoir
Je ne connais pas le langage Prolog. J'essaye de comprendre la philosophie de ton approche mais j'ai du mal. Fais-tu un « balayage » de l'espace ? Et pourquoi les distances au carré ? En tous cas ta méthode semble bonne puisque tu trouves des solutions.
Personnellement j'ai simplement cherché par tâtonnements. Pour n=12 le dodécagone et l'hendécagone avec centre ont 6 distances différentes. On peut faire mieux. Je laisse encore chercher quelques temps avant de donner une solution à 5 distances.
Jusqu'à n=13 la formule suivante se vérifie :   d = [ n/2 ]  (partie entière).

C'est plutôt un découpage de l'espace qu'un balayage, on répond à chaque itération est-ce que c'est possible qu'il y ait une solution avec chaque point dans ce rectangle là et chaque distance entre ces bornes là. Si oui on redivise les domaines, sinon on rejette les domaines. Mais le nombre de combinaisons des domaines est évidemment exponentiel. Je n'ai pas implémenté cette recherche moi-même, elle fait partie des librairies du langage.

Pourquoi les carrés? Parce que calculer une racine carrée est couteux pour et que les distances sont différentes si et seulement si leurs carrés sont différents. Ça ne change rien au problème et c'est plus rapide à calculer.

Si tu me dis qu'il y a une solution avec n=12, d=5 alors la formule d = [n/2] (que j'avais donnée aussi dans mon 2eme post) ne tient pas pour n=12.

Bonjour LittleFox et tous les autres
Pour la formule que tu avais déjà donnée elle ne tient pas en effet. J'ai écrit trop vite. J'attendais ta réaction d'ailleurs. Pour la recherche informatique de ce problème, je ne pensais pas qu'elle fut possible. D'après ce que tu en dis on ne peut cependant pas aller très loin. Pour n=12 j'ai une solution de symétrie d'ordre 3 (c'est un indice).
Pour l'espace on trouve facilement des solutions jusqu'à n=5. Après je n'ai pas cherché.

Bonjour
Plus d'amateur …
Je donne une disposition pour 12 points (pas de polygone en vue).

Pas mal