Un grand classique: a+b-pgcd(a,b).

Première réponse : si [latex]a[/latex] et [latex]b[/latex] sont premiers entre eux, une diagonale ne passera pas par les coins de certains carrés intérieurs. Et comme elle partira d'une case d'un des coins du grand rectangle, et devra "voyager" de [latex]a-1[/latex] carrés unités dans une direction et [latex]b-1[/latex] dans une autre. La diagonale traversera donc [latex]a+b-1[/latex] carrés.

Si [latex]a[/latex] et [latex]b[/latex] ne sont pas premiers, que se passe-t-il ? On prend le [latex]PGCD[/latex] de [latex]a[/latex] et [latex]b[/latex], qu'on va appeler [latex]p[/latex], et on peut diviser le rectangle en [latex]p^2[/latex] rectangles de dimensions [latex]a/p[/latex] et [latex]b/p[/latex], ces deux dimensions étant entières et premières entre elles. On se ramène au cas ci-dessus : la diagonale traversera de la même façon [latex]p[/latex] rectangles "diagonaux" de dimensions [latex]a/p[/latex] et [latex]b/p[/latex], chaque rectangle étant traversé en passant au travers de [latex]a/p+b/p-1[/latex] carrés unités. La multiplication par [latex]p[/latex] est laissée au soin du lecteur.

On peut facilement généraliser pour parvenir au résultat suivant :

Une diagonale traversera [latex]a+b-PGCD(a,b)[/latex] carrés unités.

Bonjour,
Si a=b, alors la réponse triviale est N=a=b.
Si a et b sont premiers entre eux, on a N=a+b-1.
Si a et b ne sont pas premiers entre eux, soit m leur PGCD.
Dans ce cas, on a m² sous-figures et N=m(a/m+b/m-1)=a+b-m.
On s'apercoit que cette dernière formule marche dans tous les cas, puisque si a et b sont premiers entre eux, on a m=1 et si a=b, on a m=a=b: donc:
N=a+b-PGCD(a;b)
Bonne journée.
Frank

Si a et b sont premiers entre eux:

La diagonale traverse toute la figure suivant les 2 axes perpendiculaires formés par les côtés du rectangle (de gauche à droite et de bas en haut pour faire plus simple).
Chaque fois qu'elle traverse une ligne elle traverse un nouveau carré.
Elle ne peut pas traverser 2 lignes simultanément car a et b sont premiers entre eux.
Elle traverse donc a-1 lignes dans une direction et b-1 lignes dans l'autre direction.
Il faut aussi compter le carré de départ avant qu'elle ne traverse la première ligne.
Elle traverse donc a-1+b-1+1=a+b-1 carrés.

Si a et b ne sont pas premiers entre eux, soit p leur PGCD:
a=pa' et b=pb' avec a' et b' premiers entre eux.
La diagonale trace la diagonale d'un carré a' par b' puis passe par une intersection puis elle trace la diagonale d'un carré indentique, ... p fois. Pour chacun de ces carrés elle passe par a'+b'-1 carrés et cela p fois.
Elle passe donc par p(a'+b'-1)=pa'+pb'-p=a+b-p carrés. Ce qui généralise le cas précédent.

La réponse est donc: a+b-PGCD(a,b)

Merci pour l'énigme. Je n'avais jamais démontré ce résultat.

a