Alignements

[Vassillia]

Bonjour à tous,

Dans l'idéal, si vous le voulez bien, on va essayer de dénombrer pour une grille rectangulaire de points le nombre de droites qui passe par exactement points.
Mais comme c'est un peu ambitieux et pour que tout le monde puisse participer, on peut commencer par un carré de taille réduite et par un nombre de point limité. Par exemple, on va tracer toutes les droites qui passent par exactement 3 points pour un carré 3x3 puis 4x4 puis 5x5... et on devrait avoir de jolis dessins (on aime tous les jolis dessins )

source : article de Seppo Mustonen qui dénombre les points intersections de toutes les droites que l'on peut tracer à partir d'une grille rectangulaire

[catamat]

Bon si j'ai bien compris le truc pour une grille 5x5 cela donne 16 alignements.

Il y en a 4 qui sont des diagonales de carrés (2,2) et 12 qui sont des diagonales de rectangles (1,2).

[Vassillia]

C'est exactement cela, tu as tout compris et merci pour ton joli dessin, je savais que je pouvais compter dessus
On peut laisser les carrés 3x3 et 4x4 à ceux qui découvrent le problème. Il te reste à donner le carré 6×6 et plus si affinités.
Il y en a pour tous les goûts, du trivial pour le cas 3x3 jusqu'à la formule générale dans une grille rectangulaire.

[catamat]

Bon le 6x6... mais pour la suite je pense qu'il faut plutôt raisonner où alors demander un rv à son ophtalmo

J'en ai trouvé 32 (diagonales 1x2) et toujours 4 (diagonales 2x2 ) donc 36 alignements en tout.

[Vassillia]

Bien joué
Comme tu dis, maintenant, il va falloir raisonner (oui c'est facile à dire pour moi comme j'ai découvert le problème en même temps que la solution, j'ai aucun mérite)
Dites moi si/quand vous voulez des indices ou carrément la démonstration de la formule générale mais peut-être que quelqu'un connait ou va trouver.
En tout cas merci de jouer le jeu catamat

[Doraki]

J'ai peut-être un truc mais je crains que ça donne un résultat très très moche (après je suis pas allé jusqu'au bout)

On peut compter les suites de j points espacés de manière régulière, en
choisissant séparément leurs abscisses et leur ordonnées.
Et choisir j points régulièrement espacés parmi n points, c'est pas trop dur je pense,
pour j > 1, il y en a f(j,n) = (n-(j-1)) + (n-2(j-1)) + ... + (n-k(j-1)) = nk-(j-1)k(k+1)/2, où k = [(n-1)/(j-1)]

Pour avoir le nombre de suites dans un rectangle, il y a en a de 3 sortes, celles complètement horizontales,
n * f(j,m) ; celles horizontales, m * f(j,n), et celles qui vont en diagonale, f(j,n) *f(j,m) *2, pour un total de
g(j,n,m) = 2*f(j,n)*f(j,m) + n*f(j,m) + m*f(k,n) = 2 * (f(j,n)+n/2) * (f(j,m)+m/2) - mn/2 (tout ceci est assez moche je trouve).

Pour avoir le nombre de droites contenant exactement j points, il faut ensuite compter pour chaque paire j'<=j, combien de suites de j' points régulièrement espacés sont dans une suite de j points (bah en fait c'est f(j,j')). On prend la matrice triangulaire des f(j,j'), on l'inverse, et on l'applique au vecteur des g(j',n,m).

J'ai pas du tout regardé ce qu'on obtient au final. J'ai un peu peur qu'on se retrouve avec une floppée de parties entières, mais peut-être que ça se simplifie miraculeusement je sais pas.


Il serait peut-être plus simple de compter les suites de points régulièrement espacés mais maximales.... d'un côté ou deux...

[Doraki]

si je me suis pas gourré, pour j=3 et n,m <= 10, on obtient la table suivante
(en tout cas on retrouve 16 pour 5x5 et 36 pour 6x6)

Code: Tout sélectionner

\n| 2   3   4   5   6   7   8   9  10
m\|
--+ ---------------------------------
2 | 0   2   0   0   0   0   0   0   0 
3 | 2   8   8  13  18  25  32  41  50
4 | 0   8   4   8  12  16  20  28  32
5 | 0  13   8  16  24  32  40  56  64
6 | 0  18  12  24  36  48  60  84  96
7 | 0  25  16  32  48  64  80 114 128
8 | 0  32  20  40  60  80 100 144 160
9 | 0  41  28  56  84 114 144 204 228
10| 0  50  32  64  96 128 160 228 252


avec le code

Code: Tout sélectionner

let f j n = let k = (n-1)/(j-1) in n*k-(j-1)*k*(k+1)/2

let g n m =
 let n,m = min n m, max n m in
 let t = Array.init (m+1)
   (fun j -> if j<2 then 0 else 2*f j n * f j m + n * f j m + m * f j n) in
 for i=m downto 2 do for j=i-1 downto 2 do t.(j) <- t.(j) - t.(i) * f j i done done;
 t

[LeJeu]

Bonjour Doraki,

Toujours un plaisir de te lire et toujours pas facile à suivre ( pour moi)

Peut être une petite erreur de calcul dans ta matrice avec la case 9*9 que l'on attendait plutôt comme un carré ( 144)?

Mais je ne sais pas refaire les calculs !

[catamat]

Bonjour,

J'ai voulu vérifier par dessin la valeur 64 donnée par Doraki pour la grille (7,7)

Bon j'ai épuré la figure en tenant compte des symétries, pour les droites qui sont diagonales de rectangles il suffit de compter celles dont la pente est comprise entre 0 et 1 puis multiplier par 4 pour avoir les autres (pente supérieur à 1, pente comprise entre 0 et -1, pente inférieure à -1)

D'autre part à partir de n égal à 4 il n' y a que 4 diagonales de carrés, il faut donc les ajouter ensuite.

Donc voici la figure (7,7) avec en rouge les droites de pente 1/2, en vert celles de pente 1/3 et en bleu celles de pente 2/3. Il y en a 7+5+3 donc 15.

En tout 15*4+4= 64 on trouve bien le résultat de Doraki.

[Vassillia]

Ravie que ce défi vous intéresse

Tu as tout à fait raison Doraki, tu ne t'es pas trompé, la formule que je connais (n'est pas spécialement jolie mais pas si moche non plus).
Un petit code qui calcule directement si vous voulez vérifier vos valeurs. J'ai choisi python comme je pense que ce sera le plus lisible pour la majorité (spoiler dans le code forcément)

Code: Tout sélectionner


def pgcd(a,b):
    if b==0:
        return a
    else:
        r=a%b
        return pgcd(b,r)


def f(m,n,k) :
    somme = 0
    x = 0
    while (k*x<n):
        y=1
        while (k*y<m):
            if pgcd(x,y)==1: somme += (n-k*x)*(m-k*y)
            y+=1
        x+=1

    y = 0
    while (k*y<m):
        x=1
        while (k*x<n):
            if pgcd(x,y)==1: somme += (n-k*x)*(m-k*y)
            x+=1
        y+=1
    return somme


def D(j,m,n) :
    nb=(f(m,n,j+1)-2*f(m,n,j)+f(m,n,j-1))
    return nb

@LeJeu Je comprends ce que tu veux dire, on pourrait croire sur les premiers termes que mais ce n'est valable que si .
Pour preuve le cas que l'on peut compléter par symétrie comme l'a si bien expliqué Catamat.
J’espère que vous n'aurez pas besoin de rdv chez un ophtalmo par ma faute.



Edit : je n'avais pas vu le code de Doraki initialement, je laisse quand même le mien maintenant qu'il est écrit

[LeJeu]

Merci Vassillia

c'est aussi un plaisir que de te lire!

[beagle]

Salut LeJeu,
si tu peux passer mettre juste une phrase sur le fil de discussion Netflix.
Que je sache si je dois rester sur ta "conclusion"
J'effacerai le message sur ce fil de discussion

[Vassillia]

Je vais quand même essayer d’expliquer pourquoi pour
Avec

Cela revient exactement à l’idée de Doraki.

Soit et tel que
On va s’intéresser uniquement aux droites parallèles de la grille où les points successifs sont séparés par un décalage de sur l’axe des abscisses et sur l’axe des ordonnées. On dira que la distance entre deux points sur une droite de ce type est si le décalage entre eux est de sur l’axe des abscisses et sur l’axe des ordonnées.

Pour une ligne qui contient points, on note le nombre de couple de points à distance et
-si alors la distance max est donc et
-si alors la distance max est donc ; et
-si alors la distance max est donc car on peut prendre le premier et l’avant dernier ou le deuxième et le dernier ; ; et
-si alors la distance max est donc car on peut prendre tous les points sauf les derniers qui n’auront plus de successeurs à la bonne distance ; ; et
Au final ne vaut 1 que lorsque donc uniquement lorsqu’il y a points sur la ligne et c’est ce qui nous intéresse !

Dans la grille, le nombre total de couple de points à distance est si et ; sinon. On peut en déduire que le nombre de droites passant par exactement points et vérifiant le décalage vaut .

Finalement on s'intéresse aux autres droites en sommant tous les décalages possibles pour retrouver la formule voulue. Comme pour chaque couple on aura le couple il faut diviser par 2.


Exemple avec et
On trouve bien couples de points avec aucun point entre eux
couples de points séparés par un point
couples de points séparés par 2 points

Le nombre de droites passant par exactement
2 points est
3 points est
4 points est

Voilà, j’espère que c’était à peu prés clair, j’ai essayé de faire au mieux