salut
*
quelle est la différence avec Diamètre d'un ensemble varié  ?

Dans l'exercice précédent on interdisait les distances égales entre deux points quelconques , ici les distances sont prises entre deux paires de points partageant un sommet .

Il est vrai que la nuance est subtile

Imod

Bonjour,
J'ai mis à jour ma solution qui peut-être répond à ton nouveau fil

J'ai amélioré c(4)=9 avec les points (0,0) , (1,1) , (1,2) et (3,0) .
Je propose c(5)=17 et c(6)=20 , qui dit mieux ?
Imod

Je donne une illustration pour motiver les troupes :

On remarquera que j'ai gagné un point pour c(5)
Imod

A mon tour de ne pas tout comprendre:

*sur c(5) et c(6)  il y a deux fois  la distance 1.

*la taille de la grille est-elle limitée à 2 en hauteur?

salut

dpi : l'important n'est pas d'avoir une même distance mais d'avoir de ne pas avoir les mêmes distances à partir d'un même point !! ou encore qu'un (même) point soit équidistant de deux autres.

C'est pour ça qu'il est important de bien poser la question . Dans ton fil , si tu refuses deux distances identiques , tu ne feras jamais mieux que l'exemple que j'ai proposé avec neuf segments . Le cadre imposé ici et que je pensais aussi être le tien est qu'un point de l'ensemble ne peut jamais être à la même distance de deux points de ce même ensemble . En fait c'est ce que j'ai répondu à Carpediem qui se posait un peu la même question . Sinon la grille est supposée illimitée , il me semble qu'une forme proche de celle d'un carré devient très vite un bon candidat .
Imod  

damned !! j'ai oublié d'effacer la figure : elle ne marche pas à cause du point le plus haut qui est équidistant de deux points ...

ça donne un contre-exemple pour dpi au moins ...

Avec Carpediem nous avons croisé nos réponses

Sur sa figure le point tout en haut n'est pas acceptable .

Imod

Il y a encore eu un croisement qui offre un contre-exemple , pas à cause du 2 ou du 9 mais du 13
Imod

Comme personne n'a émis de réserve pour les premières valeurs de c(n) , j'ai cherché c(7) et j'ai trouvé c(7)=36 :



S'il n'y a pas d'erreur cela nous fait sept valeurs et j'ai regardé du côté de l'OEIS et j'ai eu un retour unique  

Le calcul de c(n) se ferait simplement avec la formule où d(k) est le nombre de diviseurs de k . A priori je ne vois pas de rapport direct entre notre problème et cette formule . D'autre part je pensais qu'en ajoutant des points , le champs d'action allait s'approcher d'un carré ce qui ne semble pas vraiment être le cas . Dans tous les cas si la suite de l'OEIS est la bonne , on ne pourra pas mettre plus de 20 points dans la grille de Dpi pour son problème mais comme la forme carrée ne semble pas s'imposer , ça risque d'être bien moins .

Il y a encore du grain à moudre

Imod

Pour mon problème la grille de 10x10 est imposée et le concours est ouvert pour dépasser 10

Il me semble qu'on avait déjà compris

Quelques remarques : ta solution avec 11 points ne fonctionne pas à cause du point D et du point I donc globalement on retrouve une solution à 9 comme celle que j'ai proposé avec des contraintes bien plus fortes . Je n'ai pas essayé de faire mieux pour le moment car je préfère essayer de grimper la colline qui mène à ma boulangerie avant d'attaquer l'Everest . Sinon pour mon problème , la formule de l'OEIS ne peut pas être la bonne car de nombreuses valeurs de la liste ne sont pas sommes de deux carrés . Comme je disais , il y a encore du grain à moudre ici et sans doute là bas .

Imod

Qu'est ce qui empêche c(4)=5?
(0,0), (0,1), (2,0),(2,1)

En effet , rien ne l'empêche

En fait j'avais un doute sur l'ensemble des figures . Il ne faut pas hésiter à remettre en cause toutes les propositions car les fausses certitudes dans les cas simples perturbent énormément la suite des recherches .

Je pense que tu viens de lever un point de blocage

Imod

>BonjourLittlefox

Ton aide est toujours efficace.
Je galère depuis 10 jours sur ma grille 10x10.
Quel  est le maximum   de segments  de longueur  différente que l'on peut tracer entre deux noeuds  du quadrillage avec  la contrainte supplémentaire  que tout autre segment traçable  entre points retenus soit aussi de longueur différente.

@dpi
Désolé mais j'ai vu ce problème en premier et il me semblait plus générique. J'irai voir le tien plus tard, si j'ai encore le temps ^^

J'ai sorti mon Python et fait une recherche exhaustive mais intelligente pour ne pas dépenser du calcul inutilement ^^

J'ai amélioré toutes les solutions après n=4

Sans plus attendre voici mes résultats:

 Cliquez pour afficher

n=1
0 [(0, 0)]
n=2
1 [(0, 0), (1, 0)]
n=3
5 [(0, 0), (1, 0), (-1, -1)]
n=4
10 [(0, 0), (1, 0), (-1, -1), (-2, -1)]
8 [(0, 0), (1, 0), (-1, -1), (-1, -2)]
5 [(0, 0), (1, 0), (0, -2), (1, -2)]
n=5
13 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2)]
n=6
29 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0)]
18 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (-2, 3)]
17 [(0, 0), (1, 0), (-1, -1), (-1, -2), (-2, 2), (-3, 1)]
n=7
40 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0)]
26 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (-2, 3), (-1, 4)]
25 [(0, 0), (1, 0), (-1, -1), (1, 2), (-2, 2), (-2, 3), (-1, 4)]
n=8
65 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1)]
45 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (1, -4)]
37 [(0, 0), (1, 0), (-1, -1), (-2, -1), (3, 0), (-1, 3), (4, 0), (1, 4)]
34 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-1, 3), (-2, 3), (0, 4), (1, 4)]
32 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-1, 3), (-2, 3), (0, 4), (-3, 4)]
29 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 3), (0, 4), (-1, 4), (-3, 3)]
26 [(0, 0), (1, 0), (-1, -1), (-1, -2), (-2, 2), (-3, 1), (-2, 3), (-4, 1)]
25 [(0, 0), (1, 0), (-1, -1), (2, 1), (-2, 2), (-3, 1), (-2, 3), (-1, 4)]
n=9
68 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2)]
65 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (0, 6)]
53 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (1, -4), (5, 1)]
52 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (-3, 3), (4, 3), (-1, 6)]
50 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (-4, 1), (-4, 2), (1, 5), (-1, 6)]
41 [(0, 0), (1, 0), (-1, -1), (-2, -1), (3, 0), (1, 3), (1, 4), (0, 5), (-1, 5)]
37 [(0, 0), (1, 0), (-1, -1), (-2, -1), (1, 3), (0, 4), (-4, 1), (-3, 4), (-2, 5)]
n=10
90 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (5, -1)]
82 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (5, 1)]
68 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (0, 6)]
65 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (0, 6), (-1, 6)]
58 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (1, -4), (5, 1), (5, 2)]
53 [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (-4, 1), (-4, 2), (0, 6), (-1, 6)]
50 [(0, 0), (1, 0), (-1, -1), (-2, -1), (3, 0), (0, 4), (1, 4), (3, 4), (-1, 5), (-2, 5)]
41 [(0, 0), (1, 0), (-1, -1), (-2, -1), (1, 3), (-4, 1), (-3, 4), (-1, 5), (-2, 5), (-4, 4)]

Et voici mon code:

 Cliquez pour afficher

from bisect import bisect
from math import ceil


def dist2(p, q):
    return sum((px - qx) ** 2 for px, qx in zip(p, q))


def get_points(max_radius_2: int):
    max_radius = ceil(max_radius_2**0.5)
    points = [
        (x, y)
        for x in range(-max_radius, max_radius + 1)
        for y in range(-max_radius, max_radius + 1)
    ]
    points.sort(key=lambda p: dist2((0, 0), p))
    n = bisect(points, max_radius_2, key=lambda p: dist2((0, 0), p))
    return points[:n]


def solve(n, points, max_dist=float("inf"), placed=None, distance=None, distances=None):
    if placed is None:
        placed = [0]
        distances = [[dist2(points[p], points[q]) for q in placed] for p in placed]
        distance = max(max(row) for row in distances)

    m = len(placed)
    if m == n:
        yield distance, [points[p] for p in placed]
        return

    for p in range(placed[-1] + 1, len(points)):
        if m == 1:
            x, y = points[p]
            if y < 0 or x < y:
                continue

        new_distances = [dist2(points[p], points[q]) for q in placed]
        if new_distances[0] >= max_dist:
            return

        new_distance = max(max(new_distances), distance)
        if new_distance >= max_dist:
            continue

        if len(set(new_distances)) != m:
            continue

        if any(d in row for d, row in zip(new_distances, distances)):
            continue

        placed.append(p)
        for d, row in zip(new_distances, distances):
            row.append(d)

        new_distances.append(0)
        distances.append(new_distances)

        for max_dist, solution in solve(
            n,
            points,
            max_dist=max_dist,
            placed=placed,
            distance=new_distance,
            distances=distances,
        ):
            yield max_dist, solution

        distances.pop()
        for row in distances:
            row.pop()
        placed.pop()


def main():
    points = get_points(100**2)
    for n in range(1, 11):
        print(f"{n=}")
        for distance, solution in solve(n, points):
            print(distance, solution)


if __name__ == "__main__":
    main()

J'ai fait une proposition sur l'oeis A386493

Tout cela me dépasse un peu beaucoup , il est vrai que l'exercice est un peu tarabiscoté mais l'OEIS est habitué à bien pire

Imod  

@LittleFox

En représentant les solutions que tu as obtenues jusqu'à n=10 , j'ai noté une certaine régularité dans la disposition des points . Il y a des symétries , des rotations et il semble que les points tendent à se disposer au voisinage d'un cercle . Je ne sais pas si ton programme peut aisément produire des résultats après n=10 , si c'est le cas je suis preneur .

Merci d'avance

Imod

Je viens de voir que tu avais ajouté n=11 et n=12 . On approche d'un cadre carré mais les points ne sont pas toujours aux abords d'un cercle .
Imod

Mon programme trouve facilement des solutions au delà de n=12 mais ça devient très lent de parcourir toutes les solutions pour garantir la minimum.

Il n'y a pas de garantie que les points se comportent bien.
Pour n=8 et n=10, le minimum est unique et les points forment une figure avec plusieurs symétries. On dirait un cercle déformé.
Pour les autres n, ce n'est pas le cas, il y a plusieurs solutions avec des points plus intérieurs.

Sans garantie que ce soit le minimum, voici des solutions pour n > 12 (j'ai laissé n=20 tourner un peu plus longtemps):

 Cliquez pour afficher

c(13) <=  72: [(0, 0), (1, 0), (-1, -1), (-2, -1), (3, 0), (4, 0), (-2, -4), (5, -1), (5, -4), (0, -7), (1, -7), (3, -7), (4, -7)]
c(14) <=  97: [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (-2, 3), (4, 0), (-1, 4), (5, 0), (6, -1), (6, -2), (6, 4), (7, 2), (7, 3)]
c(15) <= 104: [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (1, -3), (3, -2), (0, 6), (1, 6), (6, 2), (5, 4), (5, 5), (7, 2), (3, 7), (8, 0)]
c(16) <= 122: [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (5, 1), (5, 2), (-6, 1), (-1, 8), (-2, 8), (0, 9), (1, 9)]
c(17) <= 136: [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (5, 1), (5, 2), (-1, 8), (-2, 8), (0, 9), (1, 9), (6, 7), (3, 9)]
c(18) <= 136: [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (5, 1), (5, 2), (-1, 8), (-2, 8), (0, 9), (1, 9), (6, 7), (3, 9), (4, 9)]
c(19) <= 173: [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (5, 1), (5, 2), (-1, 8), (0, 9), (1, 9), (6, 7), (9, 3), (4, 9), (-1, 11), (0, 12)]
c(20) <= 178: [(0, 0), (1, 0), (-1, -1), (-2, -1), (-2, 2), (3, 0), (4, 0), (-4, 1), (-4, 2), (5, 2), (5, 3), (7, 2), (4, 8), (0, 9), (4, 9), (0, 10), (7, 8), (5, 10), (0, 12), (1, 12)]

 Cliquez pour afficher

c(1) = 0
{(0, 0)}
c(2) = 1
{(0, 0), (0, 1)}
c(3) = 5
{(0, 0), (0, 1), (1, 2)}
{(0, 0), (0, 1), (2, 0)}
c(4) = 5
{(0, 0), (0, 1), (2, 0), (2, 1)}
c(5) = 13
{(0, 0), (0, 1), (1, 2), (1, 3), (3, 0)}
{(0, 0), (0, 1), (2, 0), (2, 3), (3, 1)}
{(0, 0), (0, 1), (2, 2), (2, 3), (3, 1)}
{(0, 0), (0, 2), (1, 2), (2, 3), (3, 0)}
c(6) = 17
{(0, 1), (1, 2), (1, 3), (2, 4), (3, 0), (4, 2)}
{(0, 1), (1, 1), (1, 4), (2, 0), (3, 3), (4, 2)}
{(0, 0), (0, 1), (1, 2), (3, 2), (4, 0), (4, 1)}
{(0, 1), (0, 3), (1, 0), (1, 3), (2, 4), (3, 1)}
{(0, 1), (1, 0), (1, 3), (2, 4), (3, 1), (4, 2)}
{(0, 1), (0, 2), (1, 0), (1, 3), (4, 1), (4, 2)}
{(0, 1), (1, 0), (2, 3), (2, 4), (3, 2), (4, 2)}
{(0, 1), (1, 1), (1, 4), (2, 0), (2, 3), (3, 3)}
c(7) = 25
{(0, 1), (0, 2), (1, 0), (1, 5), (2, 4), (3, 4), (4, 3)}
{(0, 2), (1, 1), (3, 0), (3, 3), (3, 5), (4, 3), (5, 2)}
{(0, 1), (0, 3), (1, 1), (2, 0), (2, 5), (3, 4), (4, 4)}
{(0, 0), (0, 1), (0, 4), (2, 0), (2, 3), (2, 4), (4, 3)}
{(0, 2), (1, 1), (2, 1), (3, 0), (3, 5), (4, 3), (5, 2)}
{(0, 0), (0, 1), (0, 4), (2, 0), (2, 1), (2, 4), (4, 3)}
{(0, 2), (1, 1), (2, 1), (2, 4), (3, 0), (4, 3), (5, 2)}
{(0, 0), (0, 1), (0, 4), (1, 3), (3, 3), (4, 1), (4, 3)}
{(0, 2), (1, 1), (2, 1), (3, 0), (3, 5), (4, 4), (5, 2)}
{(0, 1), (1, 1), (2, 0), (2, 5), (3, 3), (3, 4), (4, 2)}
{(0, 1), (0, 2), (1, 0), (1, 5), (2, 4), (3, 2), (3, 4)}
c(8) = 25
{(0, 2), (1, 1), (2, 1), (3, 0), (3, 5), (4, 3), (4, 4), (5, 2)}
c(9) = 37
{(0, 1), (0, 4), (1, 1), (1, 5), (2, 0), (3, 0), (3, 6), (4, 5), (5, 2)}
{(0, 1), (0, 4), (1, 1), (2, 0), (2, 6), (3, 0), (3, 6), (4, 5), (5, 2)}
c(10) = 41
{(0, 1), (0, 4), (1, 1), (2, 0), (2, 6), (3, 0), (3, 6), (4, 5), (5, 2), (5, 5)}

Au moins ce sujet est résolu ,nous serions heureux si tu résolvais les "segments tortueux" sur une grille  10x10

En attendant un peu plus, j'ai l'ensemble des solutions pour n=11 et 12 :

 Cliquez pour afficher

c(11) = 52
{(0, 1), (1, 1), (2, 0), (3, 0), (3, 6), (3, 7), (5, 2), (5, 5), (5, 6), (6, 2), (7, 1)}
c(12) = 53
{(0, 2), (0, 4), (1, 1), (1, 5), (2, 1), (3, 0), (3, 7), (5, 7), (6, 5), (6, 6), (7, 2), (7, 4)}
{(0, 2), (0, 3), (1, 5), (2, 0), (2, 1), (3, 7), (4, 7), (5, 0), (5, 1), (6, 5), (7, 2), (7, 3)}
{(0, 2), (0, 4), (1, 1), (2, 1), (3, 0), (3, 7), (5, 0), (5, 7), (6, 5), (6, 6), (7, 2), (7, 4)}
{(0, 2), (0, 4), (1, 1), (2, 1), (2, 6), (3, 0), (5, 0), (5, 7), (6, 5), (6, 6), (7, 2), (7, 4)}
{(0, 2), (0, 4), (1, 5), (1, 6), (2, 0), (2, 7), (4, 0), (5, 1), (5, 6), (6, 1), (6, 5), (7, 2)}

@dpi
Le problème pour "segments tortueux" ne semble pas bien défini. En tout cas Imod semble y perdre ses cheveux
Désolé dpi, je ne suis pas tenté pour l'instant. Je suis les updates sur l'autre sujet. Pas besoin de "notifications" ici

J'ai eu du mal à lire tes longues listes sur mon petit écran mais j'y suis arrivé

J'ai tout de même remarqué plusieurs choses .

En effet les valeurs ne vont pas s'agglutiner sur un cercle mais elle s'éloigne tout de même du "centre" pour se placer dans une couronne .

Autre chose qui vient peut-être de la façon dont tu as conçu ton programme , il semble qu'à partir d'un moment certaines valeurs ne changent plus . Un peu comme des électrons qui viendraient progressivement remplir les niveaux les plus bas , les autres gardant pour un temps une certaine liberté .

Imod

Oui, ça vient de la façon dont j'ai construit mon programme. Je place en premier sommet, puis le second, puis le troisième, etc et si je ne trouve pas de sommet je reviens sur le sommet précédent.

C'est du "backtracking". Ce n'est pas que les valeurs ne changeront plus, c'est que je vais tester toutes les possibilités avec ce préfixe avant de passer au préfixe suivant.

C'est plutôt comme si tu comptais tous les nombres de 000000 à 999999. Tous les chiffres vont apparaître mais l'ordre dans lequel tu compte fais que le chiffre des unités va changer beaucoup plus que le chiffre des milliers.

D'accord , ça fait penser à la loi de Benford mais ça reste troublant . D'autres idées me sont venues , tu en feras ce que tu voudras

J'ai d'abord regarder en détail ton c(20) dont les points sont disposés de manière plutôt anarchique . Il y a tout de même une concentration des points dans une couronne . Il faut en fait éviter que les 190 médiatrices rencontrent les points de l'ensemble . Notamment en limitant leur nombre .

Autre chose qui mettrait de côté le tracas des différentes décompositions en carrés . On pourrait poser le même problème avec la distance Manhattan au lieu de la distance classique qui n'a aucune raison de s'imposer sur un quadrillage .

Imod

Bonjour. LittleFox toujours aussi efficace. Bravo. Comme je l'ai déjà dit dans plusieurs problèmes de ce type, au-delà de quelques points, seule une solution informatique peut résoudre ces problèmes. Dans "Points à distances entières", en 1991 on n'avait pas trouvé mieux que 6 points. Peut-être qu'aujourd'hui on pourrait faire mieux avec un bon programme à la LittleFox.

@derny
Woaw, tu ressors des vieux dossiers En 1991 je n'avais pas 2 ans

Tu as un lien?

@Imod
Mon programme peut être facilement modifié pour la distance de Manhattan. Mais c'est ce que tu proposes dans Manhattan robot. Non?

@LittleFox : c'est bien le même problème , quand un exercice  part dans un peu dans tous les sens il est parfois bon de repartir de zéro  
Imod

Yeaaah, la série est publiée dans l'oeis

Ma première série publiée

Bravo , ça ne m'étonne pas plus que ça
Il y en aura sûrement d'autres
Imod