Alignements

Olympiades mathématiques, énigmes et défis
Vassillia
Membre Rationnel
Messages: 589
Enregistré le: 12 Jan 2021, 21:38

Alignements

par Vassillia » 04 Juin 2021, 23:33

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
Membre Relatif
Messages: 216
Enregistré le: 07 Mar 2021, 12:40

Re: Alignements

par catamat » 05 Juin 2021, 15:28

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

Image

Vassillia
Membre Rationnel
Messages: 589
Enregistré le: 12 Jan 2021, 21:38

Re: Alignements

par Vassillia » 05 Juin 2021, 17:06

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
Membre Relatif
Messages: 216
Enregistré le: 07 Mar 2021, 12:40

Re: Alignements

par catamat » 05 Juin 2021, 22:45

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

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

Image
Modifié en dernier par catamat le 06 Juin 2021, 11:34, modifié 1 fois.

Vassillia
Membre Rationnel
Messages: 589
Enregistré le: 12 Jan 2021, 21:38

Re: Alignements

par Vassillia » 06 Juin 2021, 03:21

Bien joué :super:
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
Habitué(e)
Messages: 4995
Enregistré le: 20 Aoû 2008, 13:07

Re: Alignements

par Doraki » 06 Juin 2021, 20:23

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
Habitué(e)
Messages: 4995
Enregistré le: 20 Aoû 2008, 13:07

Re: Alignements

par Doraki » 07 Juin 2021, 10:11

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
Modifié en dernier par Doraki le 07 Juin 2021, 14:28, modifié 3 fois.

LeJeu
Membre Irrationnel
Messages: 1134
Enregistré le: 24 Jan 2010, 23:52

Re: Alignements

par LeJeu » 07 Juin 2021, 11:36

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
Membre Relatif
Messages: 216
Enregistré le: 07 Mar 2021, 12:40

Re: Alignements

par catamat » 07 Juin 2021, 13:06

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.

Image

Vassillia
Membre Rationnel
Messages: 589
Enregistré le: 12 Jan 2021, 21:38

Re: Alignements

par Vassillia » 07 Juin 2021, 13:17

Ravie que ce défi vous intéresse :D

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

Image

Edit : je n'avais pas vu le code de Doraki initialement, je laisse quand même le mien maintenant qu'il est écrit
Modifié en dernier par Vassillia le 07 Juin 2021, 15:34, modifié 2 fois.

LeJeu
Membre Irrationnel
Messages: 1134
Enregistré le: 24 Jan 2010, 23:52

Re: Alignements

par LeJeu » 07 Juin 2021, 13:52

Merci Vassillia

c'est aussi un plaisir que de te lire!

beagle
Habitué(e)
Messages: 8505
Enregistré le: 08 Sep 2009, 16:14

Re: Alignements

par beagle » 07 Juin 2021, 14:28

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
Membre Rationnel
Messages: 589
Enregistré le: 12 Jan 2021, 21:38

Re: Alignements

par Vassillia » 11 Juin 2021, 00:41

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.

Image
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

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite