Sur un damier rectangulaire de n cases de long sur m cases de larges, on trace une diagonale.
Combien de cases la diagonale traverse-t-elle ?
Notons C le nombre de cases traversées par la diagonale.
La diagonale va d'un coin du damier, disons le coin supérieur gauche, jusqu'au coin opposé, le coin inférieur droit.
Pour aller d'un coin à l'autre, la diagonale va traverser toutes les lignes verticales du damier ainsi que toutes les lignes horizontales, sauf les lignes qui servent de "cadre" au damier, les lignes extérieures (au nombre de 4). La diagonale va donc traverser n-1 lignes verticales et m-1 lignes horizontales, soit un total de n + m - 2 lignes.
Pour chaque ligne traversée, la diagonale va aussi traverser une case, à l'exception des endroits où la diagonale traverse en même temps 2 lignes, c'est à dire quand elle traverse le coin d'une case. Dans ces cas-là, une case traversée correspond à 2 lignes traversées.
On peut donc dire que le nombre de cases traversées par la diagonale est égal au nombre de lignes traversées moins le nombre de coins traversés plus 1 pour la toute première case. En notant p le nombre de coins que la diagonale traverse, on a : C = n + m - 1 - p Il nous reste donc à trouver p. p = pgcd(n,m) - 1 (pgcd = plus grand commun diviseur) Pour la démonstration de ce résultat, voir ci-après, je n'ai pas trouvé de démonstration courte et lumineuse, avis à ceux qui en trouveront une plus rapide.
Aucun commentaire:
Enregistrer un commentaire