Dénombrement

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

Réponses

  • 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.
  • Bonsoir,

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

    Cordialement,
    Rescassol

  • lourrran
    Modifié (12 Mar)
    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.
     
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • LOU16
    Modifié (23 Mar)

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




  • Il serait intéressant de généraliser, remplaçant $(23,8)$ par $(n,p)$.
  • Chaurien
    Modifié (14 Mar)
  • LOU16
    Modifié (14 Mar)
    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).$$
  • 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
    Modifié (30 Mar)
    Oui, c'est d'ailleurs une excellente méthode de démonstration d'égalités numériques.
    Cordialement.
  • jeremyjeff
    Modifié (30 Mar)
    C'est-à-dire ? 
    Cordialement. 
  • gerard0
    Modifié (30 Mar)
    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
    Modifié (30 Mar)
    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
    Modifié (30 Mar)
    Ah je vois  :smile:

    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
    Modifié (30 Mar)
    @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
    Modifié (30 Mar)
    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.
  • Bonjour
    Tel Chaurien (c'est rare) je ne comprends pas: c'est quoi dont on cause et qu'y en a 2024?
  • jeremyjeff
    Modifié (30 Mar)
    oui, mais là on cherche à dénombrer les polygones formés par ces droites. à coordonnées entières.
    L'énoncé n'était pas clair.
  • 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
  • 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,
  • Qu'est-ce qu'un « polygone » dans ce contexte ?

  • Et pour un carré de côté $2$, et de côté $3$, quel est le nombre de « polygones » ?
  • 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 ?
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • 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


  • Veux-tu dire que tu paves le carré 00 10 11 01 avec 55 polygones (convexes)?
  • jeremyjeff
    Modifié (31 Mar)
    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
    Modifié (31 Mar)
    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.
Connectez-vous ou Inscrivez-vous pour répondre.