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