Nombres de droites dans un "carré"

[Anonyme]

Bonjour,

Mon problème est de trouver le nombre de droites passant par deux points
distincts dans un "carré" de n points de coté(donc n^2 points avec n
points sur chaque lignes est colonnes).

Par exemple pour n=2 nous avons un carré constitué de 4 points dont le
nombres de lignes serait ici égal à 6 (les 4 cotés +les 2 diagonales).

Si l'on augmente n à 3 (il y a maintenant un point centrale entouré de 8
points) cela devient plus compliqué, il y a toujours les 4 cotés et les 2
diagonales, mais aussi une crois centrale,les diagonales des 4 "petits
carrés" ... ce qui porte le total a environ 20 si mes comptes sont bon

tentative de shéma :
__ __
|__|__|
|__|__|
pour n=3 avec juste les cotés et la croix centrale.

Je recherche une méthode générale pour calculer le nombre de droites en
fonction de n.
Merci.

[Anonyme]

"Nicolas N." a écrit dans le message de news:
41ffe9c3$0$25777$8fcfb975@news.wanadoo.fr...
> Bonjour,
>
> Mon problème est de trouver le nombre de droites passant par deux points
> distincts dans un "carré" de n points de coté(donc n^2 points avec n
> points sur chaque lignes est colonnes).
>
> Par exemple pour n=2 nous avons un carré constitué de 4 points dont le
> nombres de lignes serait ici égal à 6 (les 4 cotés +les 2 diagonales).
>
> Si l'on augmente n à 3 (il y a maintenant un point centrale entouré de 8
> points) cela devient plus compliqué, il y a toujours les 4 cotés et les 2
> diagonales, mais aussi une crois centrale,les diagonales des 4 "petits
> carrés" ... ce qui porte le total a environ 20 si mes comptes sont bon
>
> tentative de shéma :
> __ __
> |__|__|
> |__|__|
> pour n=3 avec juste les cotés et la croix centrale.
>
> Je recherche une méthode générale pour calculer le nombre de droites en
> fonction de n.
> Merci.

Il y a n^2*(n^2-1)/2 couples de points distincts dans ton carré, donc autant
de segments. Mais si tu veux compter les droites, il faut éliminer celles
qu'on compte plusieurs fois, et c'est plus compliqué.

[Anonyme]

> Il y a n^2*(n^2-1)/2 couples de points distincts dans ton carré, donc
> autant de segments. Mais si tu veux compter les droites, il faut éliminer
> celles qu'on compte plusieurs fois, et c'est plus compliqué.

Ca doit être jouable quand n est premier (désolé, ce soir je suis trop
fatigué pour chercher plus).

--
Mû

[Anonyme]

"µ" a écrit dans le message de news:
41ffecbf$0$2178$8fcfb975@news.wanadoo.fr...[color=green]
>> Il y a n^2*(n^2-1)/2 couples de points distincts dans ton carré, donc
>> autant de segments. Mais si tu veux compter les droites, il faut éliminer
>> celles qu'on compte plusieurs fois, et c'est plus compliqué.
>
> Ca doit être jouable quand n est premier (désolé, ce soir je suis trop
> fatigué pour chercher plus).
>[/color]

Je ne suis pas sûr que ça simplifie tant que ça le problème.
Sinon, on peut peut-être essayer par récurence...

[Anonyme]

>> Ca doit être jouable quand n est premier (désolé, ce soir je suis trop[color=green]
>> fatigué pour chercher plus).
>>
>
> Je ne suis pas sûr que ça simplifie tant que ça le problème.
> Sinon, on peut peut-être essayer par récurence...[/color]

En effet, je me suis peut-être un peu emballé.
Mais il me semble qu'une droite "oblique" mais pas "à 45 degrés" ne passera
que par deux points.

--
Mû

[Anonyme]

"µ" a écrit dans le message de news:
4200709b$0$18866$8fcfb975@news.wanadoo.fr...
> En effet, je me suis peut-être un peu emballé.
> Mais il me semble qu'une droite "oblique" mais pas "à 45 degrés" ne
> passera que par deux points.

Ben, pour n=5, la droite passant par le couple (1,1) et (2,3) passe par
(3,5). De toutes façons, vu la formulation de la question ("Si l'on augmente
n à 3, [...] cela devient plus compliqué, il y a toujours les 4 cotés et les
2 diagonales, mais aussi une crois centrale,les diagonales des 4 "petits
carrés" ... ce qui porte le total a environ 20 si mes comptes sont bon"), on
dirait que Nicolas N. cherche en fait le nombre de segments...!

[Anonyme]

Cyberchand a écrit :
> "µ" a écrit dans le message de news:
> 4200709b$0$18866$8fcfb975@news.wanadoo.fr...[color=green]
>> En effet, je me suis peut-être un peu emballé.
>> Mais il me semble qu'une droite "oblique" mais pas "à 45 degrés" ne passera
>> que par deux points.
>
> Ben, pour n=5, la droite passant par le couple (1,1) et (2,3) passe par
> (3,5).[/color]

Et effectivement, le fait que n soit premier n'arrange pas vraiment
car il faut prendre en compte des droites passant par des points
*intérieurs*, soit tous les De toutes façons, vu la formulation de la question ("Si l'on augmente
> n à 3, [...] cela devient plus compliqué, il y a toujours les 4 cotés et les
> 2 diagonales, mais aussi une crois centrale,les diagonales des 4 "petits
> carrés" ... ce qui porte le total a environ 20 si mes comptes sont bon"), on
> dirait que Nicolas N. cherche en fait le nombre de segments...![/color]

Qui sait...
Mais je confirme que pour n=3 il y a bien 20 *droites*

droites horizontales : 3
droites verticales : 3
droite à + 45° : 3
droites à -45° : 3
droites à arctan(1/2) : 2
droites à -arctan(1/2): 2
droites à arctan(2) : 2
droites à -arctan(2) : 2
" ==
total 20

La même méthode donne pour n=4, D(n) = 62, sauf erreur :

droites 0/90° : 2n = 8
droite à +/- 45° : 2(2n-3) = 10
droites à +/-arctan(1/2) et arctan(2) : 4*6
droites à +/-arctan(1/3) et arctan(3) : 4*3
droites à +/-arctan(2/3)et arctan(3/2): 4*2


Début de méthode de comptage ?

droites horizontales/verticales : 2n
droites à +/- 45° : 2(2n-3)
droites à +/-arctan(p/q), +/-arctan(q/p) = 4*(???)
pour toutes les valeurs de p<q de 2 à n-1 avec PGCD(p,q)=1

Le OEIS donne alors avec 0,6,20,62 :

ID Number: A018808
URL: http://www.research.att.com/projects/OEIS?Anum=A018808
Sequence: 0,0,6,20,62,140,306,536,938,1492,2306,3296...
Name: Number of lines through at least 2 points of an
n X n grid of points.
Formula: 1/2 (f(n, 1) - f(n, 2)) where
f(n, k) = Sum ((n - |x|)(n - |y|));
-n<x<n, -n<y<n, (x,y)=k.

reste à vérifier que la définition du OEIS est bien ce que l'on cherche
et vérifier les premières valeurs à la main.
(jai déjà eu des surprises...)
qui se dévoue pour n=5 D(n) = 140 ?

Amicalement.

--
philippe
(chephip at free dot fr)

[Anonyme]

(supersedes )

Cyberchand a écrit :
> "µ" a écrit dans le message de news:
> 4200709b$0$18866$8fcfb975@news.wanadoo.fr...[color=green]
>> En effet, je me suis peut-être un peu emballé.
>> Mais il me semble qu'une droite "oblique" mais pas "à 45 degrés" ne
>> passera que par deux points.
>
> Ben, pour n=5, la droite passant par le couple (1,1) et (2,3) passe par
> (3,5).[/color]

Et effectivement, le fait que n soit premier n'arrange pas vraiment
car il faut prendre en compte des droites passant par des points
*intérieurs*, soit tous les De toutes façons, vu la formulation de la question ("Si l'on augmente n à
> 3, [...] cela devient plus compliqué, il y a toujours les 4 cotés et les 2
> diagonales, mais aussi une crois centrale,les diagonales des 4 "petits
> carrés" ... ce qui porte le total a environ 20 si mes comptes sont bon"),
> on dirait que Nicolas N. cherche en fait le nombre de segments...![/color]

Qui sait...
Mais je confirme que pour n=3 il y a bien 20 *droites*

droites horizontales : 3
droites verticales : 3
droite à + 45° : 3
droites à -45° : 3
droites à arctan(1/2) : 2
droites à -arctan(1/2): 2
droites à arctan(2) : 2
droites à -arctan(2) : 2
" ==
total 20

La même méthode donne pour n=4, D(n) = 62, sauf erreur :

droites 0/90° : 2n = 8
droite à +/- 45° : 2(2n-3) = 10
droites à +/-arctan(1/2) et arctan(2) : 4*6
droites à +/-arctan(1/3) et arctan(3) : 4*3
droites à +/-arctan(2/3)et arctan(3/2): 4*2


Début de méthode de comptage ?

droites horizontales/verticales : 2n
droites à +/- 45° : 2(2n-3)
droites à +/-arctan(p/q), +/-arctan(q/p) = 4*(???)
pour toutes les valeurs de p<q de 2 à n-1 avec PGCD(p,q)=1
[errata : 1 à n-1 bien sur]

Le OEIS donne alors avec 0,6,20,62 :

ID Number: A018808
URL: http://www.research.att.com/projects/OEIS?Anum=A018808
Sequence: 0,0,6,20,62,140,306,536,938,1492,2306,3296...
Name: Number of lines through at least 2 points of an
n X n grid of points.
Formula: 1/2 (f(n, 1) - f(n, 2)) where
f(n, k) = Sum ((n - |x|)(n - |y|));
-n<x<n, -n<y<n, (x,y)=k.

reste à vérifier que la définition du OEIS est bien ce que l'on cherche
et vérifier les premières valeurs à la main.
(jai déjà eu des surprises...)
qui se dévoue pour n=5 D(n) = 140 ?

Amicalement.

--
philippe
(chephip at free dot fr)

[Anonyme]

>> En effet, je me suis peut-être un peu emballé.[color=green]
>> Mais il me semble qu'une droite "oblique" mais pas "à 45 degrés" ne
>> passera que par deux points.
>
> Ben, pour n=5, la droite passant par le couple (1,1) et (2,3) passe par
> (3,5). De toutes façons, vu la formulation de la question ("Si l'on
> augmente n à 3, [...] cela devient plus compliqué, il y a toujours les 4
> cotés et les 2 diagonales, mais aussi une crois centrale,les diagonales
> des 4 "petits
> carrés" ... ce qui porte le total a environ 20 si mes comptes sont bon"),
> on dirait que Nicolas N. cherche en fait le nombre de segments...![/color]

Euh oui, en effet, c'était pas mon jour...
Ceci dit, la question me plaît bien, j'y réfléchirai...

--
Mû

[Anonyme]

[color=green]
>> De toutes façons, vu la formulation de la question ("Si l'on augmente n à
>> 3, [...] cela devient plus compliqué, il y a toujours les 4 cotés et les
>> 2 diagonales, mais aussi une crois centrale,les diagonales des 4 "petits
>> carrés" ... ce qui porte le total a environ 20 si mes comptes sont bon"),
>> on dirait que Nicolas N. cherche en fait le nombre de segments...!
>
> Qui sait...[/color]
Je confirme que je cherche bien le nombre de droites, mais il est vrai que
ma formulation était quelque peu confuse.
> Mais je confirme que pour n=3 il y a bien 20 *droites*
>
> droites horizontales : 3
> droites verticales : 3
> droite à + 45° : 3
> droites à -45° : 3
> droites à arctan(1/2) : 2
> droites à -arctan(1/2): 2
> droites à arctan(2) : 2
> droites à -arctan(2) : 2
> " ==
> total 20
>
> La même méthode donne pour n=4, D(n) = 62, sauf erreur :
>
> droites 0/90° : 2n = 8
> droite à +/- 45° : 2(2n-3) = 10
> droites à +/-arctan(1/2) et arctan(2) : 4*6
> droites à +/-arctan(1/3) et arctan(3) : 4*3
> droites à +/-arctan(2/3)et arctan(3/2): 4*2
Je tombe aussi sur le même résultat.
>
> Début de méthode de comptage ?
>
> droites horizontales/verticales : 2n
> droites à +/- 45° : 2(2n-3)
> droites à +/-arctan(p/q), +/-arctan(q/p) = 4*(???)
> pour toutes les valeurs de p [errata : 1 à n-1 bien sur]
>
> Le OEIS donne alors avec 0,6,20,62 :
>
> ID Number: A018808
> URL: http://www.research.att.com/projects/OEIS?Anum=A018808
> Sequence: 0,0,6,20,62,140,306,536,938,1492,2306,3296...
> Name: Number of lines through at least 2 points of an
> n X n grid of points.
> Formula: 1/2 (f(n, 1) - f(n, 2)) where
> f(n, k) = Sum ((n - |x|)(n - |y|));
> -n
> reste à vérifier que la définition du OEIS est bien ce que l'on cherche
> et vérifier les premières valeurs à la main.
A premiere vu c'était bien la question posés.

> (jai déjà eu des surprises...)
> qui se dévoue pour n=5 D(n) = 140 ?
Pour n=5 avec sans doute des erreur
droites 0/90:2*5=10
droites +/- 45:14
droites à +/-arctan(1/2) et arctan(2) :38??? sans doute une erreur
droites à +/-arctan(1/3) et arctan(3) :32=4*8
droites à +/-arctan(1/4) et arctan(4) :16=4*4
droites à +/-arctan(2/3) et arctan(3/2) :24=4*6
droites à +/-arctan(3/4)1 et arctan(4/3) :12=4*3
total:146?? on est loin des 140

[Anonyme]

Nicolas N. a écrit :
> Je confirme que je cherche bien le nombre de droites, mais il est vrai que
> ma formulation était quelque peu confuse.
....[color=green]
>>
>> Début de méthode de comptage ?
>>
>> droites horizontales/verticales : 2n
>> droites à +/- 45° : 2(2n-3)
>> droites à +/-arctan(p/q), +/-arctan(q/p) = 4*(???)
>> pour toutes les valeurs de p>
>> Le OEIS donne alors avec 0,6,20,62 :
>>
>> ID Number: A018808
>> URL: http://www.research.att.com/projects/OEIS?Anum=A018808
>> Sequence: 0,0,6,20,62,140,306,536,938,1492,2306,3296...
>> Name: Number of lines through at least 2 points of an
>> n X n grid of points.
>> Formula: 1/2 (f(n, 1) - f(n, 2)) where
>> f(n, k) = Sum ((n - |x|)(n - |y|));
>> -n>
>> reste à vérifier que la définition du OEIS est bien ce que l'on cherche
>> et vérifier les premières valeurs à la main.
> A premiere vu c'était bien la question posés.
>
> Pour n=5 avec sans doute des erreur
> droites 0/90:2*5=10 ok
> droites +/- 45:14 ok
> droites à +/-arctan(1/2) et arctan(2) :38??? sans doute une erreur[/color]

oui. je trouve 4*9 = 36
à part les k*45°, il suffit de compter juste les droites de pente p/q
et de multiplier par 4 (symétries du carré) pour avoir les pentes +/- p/q, et +/- q/p.
soit ici 9 droites de pente +1/2

> droites à +/-arctan(1/3) et arctan(3) :32=4*8 ok
> droites à +/-arctan(1/4) et arctan(4) :16=4*4 ok
> droites à +/-arctan(2/3) et arctan(3/2) :24=4*6 ok
> droites à +/-arctan(3/4)1 et arctan(4/3) :12=4*3

et une autre là : je trouve 4*2 = 8

> total:146?? on est loin des 140

ce qui me donne bien 140

Reste à décortiquer la formule donnée...
qui ne semble pas correspondre à ma méthode de comptage.

--
philippe
(chephip at free dot fr)

[Anonyme]

>>[color=green]
>> Pour n=5 avec sans doute des erreur
>> droites 0/90:2*5=10 ok
>> droites +/- 45:14 ok
>> droites à +/-arctan(1/2) et arctan(2) :38??? sans doute une erreur
>
> oui. je trouve 4*9 = 36[/color]
Exacte, j'avais bien compter deux droites de plus
> à part les k*45°, il suffit de compter juste les droites de pente p/q
> et de multiplier par 4 (symétries du carré) pour avoir les pentes +/- p/q,
> et +/- q/p. soit ici 9 droites de pente +1/2
>[color=green]
>> droites à +/-arctan(1/3) et arctan(3) :32=4*8 ok
>> droites à +/-arctan(1/4) et arctan(4) :16=4*4 ok
>> droites à +/-arctan(2/3) et arctan(3/2) :24=4*6 ok
>> droites à +/-arctan(3/4)1 et arctan(4/3) :12=4*3
>
> et une autre là : je trouve 4*2 = 8[/color]
Encore exacte, une grosse étourderie de ma part.[color=green]
>> total:146?? on est loin des 140
>
> ce qui me donne bien 140
>
> Reste à décortiquer la formule donnée...
> qui ne semble pas correspondre à ma méthode de comptage.
>[/color]
Pourriez vous m'expliquez ce que signifie le "(x,y)=k"
dans f(n, k) = Sum ((n - |x|)(n - |y|));
-n<x<n, -n<y<n, (x,y)=k.
~~~~~~~~

[Anonyme]

Nicolas N. a écrit :
....[color=green]
>>
>> Reste à décortiquer la formule donnée...
>> qui ne semble pas correspondre à ma méthode de comptage.
>>
>> Formula: 1/2 (f(n, 1) - f(n, 2)) where
>> f(n, k) = Sum ((n - |x|)(n - |y|));
>> -n Pourriez vous m'expliquez ce que signifie le "(x,y)=k"
> dans f(n, k) = Sum ((n - |x|)(n - |y|));
> -n ~~~~~~~~

c'est PGCD(x,y)

par exemple avec n=4 ça donne
f(4,1) = Sum pour (x,y) = (0,+/-1), (+/-1,+/-1), (+/-1,+/-2), (+/-1,+/-3), (+/-2,+/-3)
f(4,2) = Sum pour (x,y) = (0,+/-2)

et avec n=5, f(5,2) = Sum pour (x,y) = (0,+/-2), (+/-2,+/-4)

Mais je n'ai pas trouvé d'où ça sort...

--
philippe
(chephip at free dot fr)

[Anonyme]

Nicolas N., dans un fervent élan, a postillonné :

>[SLIP]..

[HS]
Haha, l'est vache le prof qu'a posé ça en colle !!
[/HS)

--
'L'humour noir, c'est la politesse du désespoir.'
(Achille Chavée)

[Anonyme]

Nicolas N., dans un fervent élan, a postillonné :

>[SLIP]

[HS]
Tu quotes comme un goret nico !!
[/HS]

--
'L'humour noir, c'est la politesse du désespoir.'
(Achille Chavée)