Dénombrement

jeremyjeff

Bonjour,

Je cherche une méthode (démonstration ou informatique)  pour dénombrer  le nombre de segments qui passent par exactement huit  points d'une grille carrée de 23 ×  23 .
Je n'arrive pas à savoir quelle méthode permettrait de faire ce dénombrement. 
C'est la condition "segments qui passent par exactement huit  points" que je n'arrive pas à mettre en équation.

Merci pour vos éclairements 

Cordialement, JeremyJeff

GaBuZoMeu

Bonsoir,

On peut voir quelles sont les pentes possibles (vecteurs primitifs avec des coordonnées de valeur absolue au plus 3 puisque 4 fois 7 dépasse 22), et puis compter pour chaque pente. Pas mal casse-pieds, mais faisable.

Rescassol

Bonsoir,

Il suffit de compter les rectangles dont les dimensions sont dans $\{0;7;14;21\}$.

Cordialement,
Rescassol

lourrran

Bonsoir,
Il faudra alors retirer le rectangle de hauteur 0 et de largeur 14, et quelques autres cas de ce type.

Plus précisément, il faudra retirer les rectangles de taille $7a \times 7b$ avec $a$ et $b$ non premiers entre eux.
 

LOU16

Bonjour,

Je trouve plus sûr de procéder comme le suggère Gabuzomeu.

Je note, pour $a\in \R\cup\{\infty\} ,\quad N(a) :=\text{ nombre de segments de pente }a.\:$ Soit $\:E:=\Big\{a\in\R\cup\{\infty\}\mid N(a)\neq 0 \Big\}.\:$ Alors:

 $\:a\in E \iff \left(a= \dfrac pq ,\quad p,q\in\Z,\quad p\wedge q=1,\quad |p|,|q|\leqslant 3.\right)\:\:$ donc $\:\:E=\Big \{ 0, \pm \frac 13,\pm \frac 12, \pm\frac 23, \pm 1,\pm \frac 32,\pm 2, \pm 3,\infty \Big\}.$

$$\begin{array}{|c|c|}\hline \text{ Si } a= &\text{ alors }N(a) =\\\hline 0,\infty& 23\times 16 \\ \hline \pm \frac 13,\pm 3& 16\times 2\\ \hline \pm  \frac 12,\pm 2 & 16 \times 9\\ \hline \pm \frac 23,\pm \frac 32 & 9 \times 2 \\ \hline \pm 1& 16 \times16\\  \hline \end{array}\quad \displaystyle \sum_{a\in \R\cup\{\infty\}} N(a) =\sum_{a\in E}N(a)=2024.$$

Chacun de ces cinq cas correspond à un des cinq "formats de  rectangle" possibles: $\quad 7\times 0, \: 21 \times7, \:14\times 7, \:21\times 14, \:7\times 7.$

Chaurien

Il serait intéressant de généraliser, remplaçant $(23,8)$ par $(n,p)$.

Chaurien

J'ai trouvé ceci, je ne l'ai pas étudié, ça n'a pas l'air simple.

https://www.semanticscholar.org/reader/c4e50c1b805398a48ab9738d2bae2b4d176a34ff

http://www.survo.fi/papers/LinesInGrid2.pdf

LOU16

Bonjour,

Pour ma part, je ne trouve pas mieux que: $$\mathcal N(n,p) =2n(n-p+1)+2(n-p+1)^2+\displaystyle 4\sum_{\substack{1\leqslant s<t\leqslant\lfloor\frac n{p-1}\rfloor \\s\wedge t =1}}(n-ps+s)(n-pt+t).$$

jeremyjeff

Bonjour,

Je trouve aussi 2024 en traçant toutes les droites passant par deux des seize points, à coordonnées entières, situés sur les bords d'un carré de côté 4.
Comme quoi deux problèmes peuvent avoir les mêmes solutions, alors que les méthodes de dénombrement sont complètement différentes.

Cordialement

gerard0

Oui, c'est d'ailleurs une excellente méthode de démonstration d'égalités numériques.
Cordialement.

jeremyjeff

C'est-à-dire ? 
Cordialement. 

gerard0

Qu'on démontre des égalités dans $\mathbb N$ en traduisant chacun des deux membres comme un dénombrement, et comme c'est le même dénombrement, on en conclut l'égalité. On a eu de nombreux exemples sur le forum.

Un exemple élémentaire : On considère un ensemble E à n éléments, et on veut connaître le cardinal de ses parties.

* Première façon : Il y a bijection entre l'ensemble des parties de E et l'ensemble des applications de E dans {0,1}.

* Deuxième façon : L'ensemble des parties est la réunion disjointe des ensembles de parties à k éléments pour k variant de 0 à n.

On en déduit $2^n=\sum\limits_{k=0}^n C_n^k$

Cordialement.

jeremyjeff

Sans doute.
Je n'arrive pas à faire le lien entre les segments de  longueur 8 de la grille 23x 23 et le deuxième dénombrement où les polygones formés
sont des triangles (3 côtés), des quadrilatères (4 côtés), des pentagones (5 côtés) ....
Le lien ne saute pas aux yeux.  
On peut travailler avec toutes les pentes possibles  certes. 

Cordialement 

jeremyjeff

Ah je vois 

Le problème est symétrique.
On peut se limiter au quart de région droite et multiplier le nombre de solutions pour cette partie par 4.

On est alors amené à chercher le nombre de polygones formés à partir d'un grille de points 3 x 3  , avec les coordonnés entières.
On obtient alors des diagonales de polygones passant par 2 points, ou 3 points.
Donc les pentes possibles sont en valeurs absolues : 1/3,  2/3, 0 , l'infini 

Chaurien

@jeremyjeff Je pense que tu veux dénombrer les droites passant par $ 2$ des $16$ points, à coordonnées entières, situés sur les côtés d'un carré de côté $4$. ces deux points n’étant pas sur le même côté du carré, et que sur ton dessin, il n'y a que quelques-unes de ces droites, puisque tu affirmes qu'il  il y en a en tout $2024$.

 Il faudrait traiter ce problème pour un carré de côté autre que $4$, dans l'espoir d'une formule, mais il n'est pas nécessaire d'espérer pour entreprendre ...

Chaurien

Et ce résultat $ 2024$ me semble bizarre en y réfléchissant,  car d'une façon générale le nombre total de droites joignant $2$ points quelconques  parmi $16$ en position générale dans le plan est le nombre de paires de points parmi ces $16$, c'est $\binom{16}{2}=120$ seulement.

depasse

Bonjour
Tel Chaurien (c'est rare) je ne comprends pas: c'est quoi dont on cause et qu'y en a 2024?

jeremyjeff

oui, mais là on cherche à dénombrer les polygones formés par ces droites. à coordonnées entières.
L'énoncé n'était pas clair.

depasse

Désolé @jeremyjeff mais ce n'est toujours pas clair (pour moi): Tu écris, entre deux points:
"à coordonnées entières". Parles-tu des coordonnées des sommets de tes polygones à dénombrer? 
Sinon, veux-tu rappeler que tes droites passent des points entiers?
Enfin, parles-tu des polygones inclus dans ton carré ou de tous les polygones déterminés par tes droites?
Promis, je n'éprouve aucun plaisir à te dire que tu n'es pas clair (pour moi).
Paul

jeremyjeff

Si je trace toutes les droites passant par deux des seize points, à coordonnées entières, situés sur les bords d'un carré de côté 4, j'obtiens A polygônes. A vaut : 2024. Voilà de quoi on parle.
Et ce problème , peut se dénombrer à l'aide du problème initial : dénombrement du nombre de segments qui passent par exactement huit  points d'une grille carrée de 23 ×  23 .
Dans la 2ème figure :  on a dessiné quelques-unes des droites passant par deux des seize points.

Cordialement,

Chaurien

Qu'est-ce qu'un « polygone » dans ce contexte ?

Chaurien

Et pour un carré de côté $2$, et de côté $3$, quel est le nombre de « polygones » ?

lourrran

Je note les 16 points de A1 à E1 pour la ligne du bas, de A1 à A5 pour la colonne de gauche , etc, comme les notations classiques sur un échiquier.
Si on trace tous les segments, on trace entre autres le triangle (B1,C5,E4). Doit-on compter ce triangle dans le décompte final, sachant que sur le dessin final, ce triangle est divisé en plein de petits polygones ?
On alors, on se limite aux polygones unitaires, ceux qui ne sont traversés par aucun segment ?

jeremyjeff

On compte le nombre de polygones du 1/4 de la figure. 

Le carré qui nous intéresse peut lui même être découpé en 4 carrés.

Le carré qui passe par les points (0,0), (0,1), (1,1), (1,0) étant à l'extrémité  comporte  55 polygones. 

Le carré passant par les points (0,1), (0,2), (1,2), (1,1) est le même, par symétrie que le carré passant par les points (1,0), (1,1), (2,1), (2,0). 

Ils contiennent chacun 72 polygones. 

Le 4ème carré passant par les points (1,1), (1,2), (2,2), (2,1) est symétrique autour de l'axe (1,1), (2,2). 

Il contient 2 fois 27 polygones, soit 54 polygones.

Au total, on a donc 2 x (55 + 72 + 72 + 27 + 27) soit 2 x 253 = 506  polygones pour 1/4 de la figure. 

Ce qui fait au total 4 * 506 soit A = 2024 polygones

jeremyjeff

depasse

Veux-tu dire que tu paves le carré 00 10 11 01 avec 55 polygones (convexes)?

jeremyjeff

Bonjour,

Voici une méthode de dénombrement en vue de trouver une formule générale.
En reliant les points des sommets des carrés, on obtient des polygones élémentaires (non décomposables)  et de polygones qu'on peut décomposer à partir de 2, 3 ... de ces polygones élémentaires.

1°) cas n = 4  (carré formé de 4 points)
On relie les points situés sur les bordures du carré:
On obtient des polygones.
On compte ceux composés de:
 - Polygones élémentaires :  Il y en a 4  (1 , 2, 3, 4)
 - Polygones doubles :  Il y en a 6   (1-2, 1-4, 2-3, 2-4, 4-3, 1-3)
 - Polygones triples : Il y en a 4 (1-2-3,  2-3-4,   3-4-1,  4-1-2)
 - Polygones quadruples : Il y en a 1 (c'est le grand carré).
D'où au total  4 + 6 + 4 +1 = 15  à formuler avec  2 ou 4 :  4² -1

2°) ) cas n = 9  (carré formé de 9 points)
On constate que le nombre de total de polygones formé est symétrique.
On a 4 fois le nombres de régions d'un des 4 carrés.
Pour le 1er carré supérieur, on procède ainsi
  - Polygones élémentaires :  Il y en a 14 :  (1, 2, 3, ...., 14)
  - Polygones doubles:  Il y en a 30 :   (1-3, 1-2, 2-4 , 2-3 , 2-9,  2-5,  3-5,  3-6, 3-7,  4-5, 4-8 , 4-9 , 4 -10 , 5-7,  5-9,  5- 14, 6-7 , 7-13, 7-14,  8-10, 
                                         9-10, 9-11, 9-12 , 9-14, 10-11, 10-12 , 12-11, 12-14, 12-13,  13-14 )

   Polygones triples ...
on procède  de la sorte.
Je n'ai pas vraiment trouvé de formule.
C'est plus un procédé de dénombrement.
Cordialement,

gerard0

Bonjour.

En disant que le nombre total de polygones est 4 fois celui d'un des sous-carrés, tu oublies pas mal de polygones, comme par exemple celui formé par 6 et son symétrique dans le carré" d'à côté.

Le compte n'est pas bon !

Cordialement.