Déjà je pense qu'il faut séparer le rectangle de côtés n et p en plusieurs sous rectangles dans lesquels la diagonale ne passera jamais par un nœud du quadrillage (à l'intersection de traits du quadrillage).
On va commencer par établir quelques notations pour simplifier les explications :
Notons R(n,p) le rectangle de côtés n et p.
On dit qu'il y a passage par des nœuds pour un rectangle si sa diagonale passe par au moins un nœud du quadrillage.
On note D(n,p) le nombre de carreaux coupés par la diagonale de R(n,p).
Il est facile de constater (peut-être aussi de démontrer) qu'il y a passage par des nœuds pour R(n,p) si et seulement si n et p ne sont pas premier entre eux (c'est à dire si pgcd(n,p) <> 1).
Soit d = pgcd(n,p), on peut séparer R(n,p) en d rectangles R(n/d,p/d) "intéressants" (en ne conservant que ceux coupés par la diagonale).
Et bien évidemment : D(n,p) = d * D(n/d,p/d).
Maintenant qu'on a décomposé le problème, il faut calculer D(n,p) pour n et p premiers entre eux.
On considère alors R(n,p) avec pgcd(n,p) = 1.
Bon, je poste ça pour l'instant et j'essaie de trouver la suite. ^^
EDIT : Suite et résultat.
Tout à fait informellement : quand on trace les diagonales de quelques rectangles R(n,p) avec pgcd(n,p) = 1 et qu'on colorie les carreaux coupés par la diagonale on remarque que ça fait une sorte d'escalier et que chaque fois qu'on change de ligne (ou de colonne) deux carreaux sont coloriés au lieu d'un. On en "déduit" (là encore je ne démontre rien, ça se fait peut-être) que : D(n,p) = n + p - 1. Le "-1" étant du au fait que pour accéder à la 1re ligne/colonne parcourue on n'a pas besoin de passer une marche puisqu'on y commence.
On a donc pour tout rectangle R(n,p) : D(n,p) = pgcd(n,p) * ( n/pgcd(n,p) + p/pgcd(n,p) - 1).
D'où le résultat :
D(n,p) = n + p - pgcd(n,p) !
Voilà, si le résultat suffit c'est bon, par contre si une démonstration ou une preuve rigoureuse est demandée y'a encore un peu de travail.
[Maths] Exercice de spé math, Terminale S
Bienvenue dans la Distillerie d'entraide
. 