Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

La traversée du rectangle

[Difficulté: Difficile - Niveau de connaissances : Troisième et +]

La figure ci-dessous représente un quadrillage de 8×68 \times 6 carreaux.

La traversée du rectangle

Une diagonale traverse 1212 cases (colorées en vert sur la figure).

Combien de cases traversera une diagonale d'un rectangle de 2016×16202016 \times 1620 carreaux ?

Solution

La bonne réponse est : 36003600

Pour obtenir cette réponse, nous allons d'abord raisonner sur le rectangle de 8×68 \times 6 carreaux, puis nous généraliserons ce raisonnement à un rectangle de dimensions n×mn \times m quelconques avec n⩾mn \geqslant m. Enfin nous appliquerons le résultat trouvé au rectangle de 2016×16202016 \times 1620 carreaux.  

Première étape : Subdivision en rectangles plus petits

On voit sur la figure ci-dessous que la diagonale qui traverse le rectangle de 8×68 \times 6 carreaux traverse successivement deux rectangles de 4×34 \times 3.

La traversée du rectangle 2

Pourquoi peut-on partager en 22 ? Parce que 22 divise à la fois 88 et 66.

Dans le cas général d'un rectangle de dimensions n×mn \times m, on pourra (au maximum) subdiviser le rectangle en dd sous-rectangles où dd est le PGCD de nn et de mm. La taille de chacun de ces sous-rectangles sera n′×m′n^{\prime} \times m^{\prime} avec n′=ndn^{\prime}=\frac{n}{d} et m′=mdm^{\prime}=\frac{m}{d}.

 

Seconde étape : Nombre de carreaux traversés dans les sous-rectangles

Il reste à calculer le nombre de carreaux traversés dans chacun des sous-rectangles de 4×34 \times 3 carreaux. Comme 44 et 33 sont premiers entre eux, la diagonale ne passe par aucun point d'intersection ("noeud") du quadrillage.

Colorons d'une couleur différente (jaune) les carreaux traversés situés au-dessus d'un autre carreau traversé.

La traversée du rectangle 3

Il est alors facile de compter :

  • les carreaux verts : il y en a un par colonne (donc 44)

  • les carreaux jaunes : il y en a un par ligne sauf pour la ligne du bas (donc 22)

Il y a donc 4+2=64+2=6 cases colorées au total.

Dans le cas d'un sous-rectangle de dimensions n′×m′n^{\prime} \times m^{\prime} avec n′⩾m′n^{\prime} \geqslant m^{\prime}, on aura

  • n′n^{\prime} carreaux verts (un par colonne)

  • m′−1m^{\prime} - 1 carreaux jaunes (un par ligne sauf la ligne du bas )

Au total, il y a donc n′+m′−1n^{\prime}+m^{\prime} - 1 carreaux traversés.

Dernière étape : Calcul du total

Pour le rectangle de 8×68 \times 6, la diagonale traverse successivement deux sous-rectangles. Dans chacun de ces sous-rectangles, elle traverse 66 carreaux donc au total la diagonale traverse 2×6=122 \times 6=12 carreaux.

Pour un rectangle de dimensions n×mn \times m, la diagonale traverse successivement dd sous-rectangles avec d=PGCD(m,n)d=PGCD(m,n). Dans chacun de ces sous-rectangles, elle traverse n′+m′−1=nd+md−1n^{\prime}+m^{\prime} - 1=\frac{n}{d}+\frac{m}{d} - 1 cases.

Au total la diagonale va traverser d×(nd+md−1)=n+m−dd \times \left(\frac{n}{d}+\frac{m}{d} - 1\right)=n+m - d c'est à dire n+m−PGCD(n,m)n+m - PGCD(n,m) carreaux.

Il ne reste plus qu'à appliquer ce résultat au rectangle de 2016×16202016 \times 1620 carreaux.

En utilisant l'algorithme d'Euclide ou à la calculatrice on trouve PGCD(2016,1620)=36PGCD(2016 ,1620)=36.

Le nombre de cases traversées est donc : 2016+1620−36=36002016+1620 - 36=3600

Autres exercices de ce sujet :