Exercice 3 — La diagonale sur quadrillage

Sujet

Sur une feuille quadrillée, on trace un rectangle ABCD de côtés entiers \(a\) et \(b\) selon les lignes du quadrillage, puis sa diagonale [AC]. On note \(N(a,b)\) le nombre de carreaux traversés par cette diagonale. Exemple : \(N(4,6)=8\).

Donner \(N(2,3)\), \(N(2,4)\), \(N(3,4)\), \(N(3,6)\), \(N(5,7)\), \(N(8,12)\).
a) Déterminer \(N(1,b)\). b) Que vaut \(N(2,b)\) selon la parité de \(b\) ? c) Relier \(N(k,kb)\) à \(N(1,b)\).
On suppose \(a/b\) irréductible (\(a,b\) premiers entre eux). a) Exprimer \(N(a,b)\). b) Exprimer \(N(ka,kb)\) en fonction de \(a,b,k\).
Calculer \(N(1500,2010)\).
Déterminer \(N(a,b)\) dans le cas général.

La diagonale change de carreau à chaque fois qu'elle traverse une ligne verticale ou horizontale du quadrillage. Si \(a\) et \(b\) sont premiers entre eux, elle ne passe jamais exactement par un nœud du quadrillage (point d'intersection ligne verticale/horizontale) — compter séparément le nombre de côtés verticaux et horizontaux traversés donne directement le nombre de carreaux. Dans le cas général (\(a,b\) non premiers entre eux), le rectangle se découpe en \(\mathrm{pgcd}(a,b)\) copies d'un même petit rectangle aux côtés premiers entre eux.

1. \(N(2,3)=4\), \(N(2,4)=4\), \(N(3,4)=6\), \(N(3,6)=6\), \(N(5,7)=11\), \(N(8,12)=16\).

2a. \(N(1,b)=b\) (avec \(a=1\), toujours premier avec \(b\) : la diagonale traverse \(b\) carreaux, un par ligne).

2b. \(N(2,b)=b+1\) si \(b\) est impair (2 et \(b\) premiers entre eux), \(N(2,b)=b\) si \(b\) est pair (\(\mathrm{pgcd}=2\)).

2c. \(N(k,kb)=k\times N(1,b)=kb\).

3a. Si \(a,b\) premiers entre eux, la diagonale ne rencontre aucun nœud du quadrillage : elle coupe \(b-1\) côtés verticaux et \(a-1\) côtés horizontaux, donc traverse \(a+b-2\) nouveaux carreaux après le premier, plus le premier lui-même : \(N(a,b)=a+b-1\).

3b. En multipliant les dimensions par \(k\) (le motif se répète \(k\) fois) : \(N(ka,kb)=k(a+b-1)\).

4. \(\mathrm{pgcd}(1500,2010)=30\) (car \(1500=30\times50\), \(2010=30\times67\), et \(\mathrm{pgcd}(50,67)=1\)). Donc \(N(1500,2010)=30\times N(50,67)=30\times(50+67-1)=30\times116=\mathbf{3480}\).

5. En posant \(a=ka'\), \(b=kb'\) avec \(k=\mathrm{pgcd}(a,b)\) (donc \(a',b'\) premiers entre eux) : \(N(a,b)=N(ka',kb')=k(a'+b'-1)=ka'+kb'-k=a+b-k\).

Formule générale : \(N(a,b)=a+b-\mathrm{pgcd}(a,b)\).

Exercice 3 — La diagonale sur quadrillage (académique)

Sujet