Géométrie sur quadrillage
Problème : Sur un quadrillage on trace un rectangle dont les sommets sont des nœuds du quadrillage et les côtés suivent le quadrillage. On trace une des diagonales de ce rectangle et on numérote les points d’intersection de sa diagonale avec les lignes du quadrillage en commençant à 0.
Trouver une formule qui donne le nombre obtenu sur le sommet opposé à celui de départ à l’aide des dimensions a et b du rectangle on attribue la valeur 0 au premier point d'intersection.
Publié le 04/10/2013 à 15:40:31 - Auteur : Gaëtan
REPONSES :
a et b sont des entiers car le rectangle suit le quadrillage.
Si a = 1 ou b = 1 quelque soit la valeur du second, la diagonale ne passe par aucun noeud.
Supposons 1 < a < b, il y a toujours au plus (a-1) noeud(s).

Si a divise b alors il y a (a−1) noeud(s) sinon il n'y a pas de noeud.

Réponse publiée le 21/10/2018 à 17:07:51 - Auteur : Le webmaster
Exemple : avec a = 5 et b = 10 ⇒ 4 noeuds.
Réponse publiée le 21/10/2018 à 17:23:31 - Auteur : Le webmaster
Une correction d'abord. La diagonale ne passe pas par des nœuds seulement quand a divise b. Elle passe par un nœud intérieur chaque fois que a et b ont un diviseur commun : le nombre de nœuds traversés, sans compter les deux sommets, est égal à PGCD(a ; b) − 1.
Exemple : a = 4 et b = 6. Le PGCD vaut 2 et la diagonale passe par le nœud situé à 2 carreaux en hauteur et 3 en largeur, alors que 4 ne divise pas 6. Avec a = 5 et b = 10, le PGCD vaut 5 et on retrouve les 4 nœuds de l'exemple.
On peut maintenant répondre à la question posée, en mettant 0 sur le sommet de départ. À l'intérieur du rectangle, la diagonale coupe b − 1 lignes verticales et a − 1 lignes horizontales, puis elle arrive au sommet opposé. Quand elle passe par un nœud, elle coupe deux lignes au même point, qui ne reçoit qu'un numéro. Le sommet opposé porte donc le numéro :
N = a + b − PGCD(a ; b)
Vérification avec a = 2 et b = 3 : PGCD = 1, donc N = 4. La diagonale coupe les 2 lignes verticales et la ligne horizontale en 3 points différents, numérotés 1, 2 et 3, et le sommet opposé reçoit le 4.
Si l'on donne le 0 au premier point après le sommet de départ, il faut retrancher 1 : N = a + b − PGCD(a ; b) − 1.
Pour calculer le PGCD : PGCD de deux nombres.
La question est maintenant close.
Réponse publiée le 20/10/2026 à 10:00:00 - Auteur : Le webmaster