XXVIII - I - Zadanie 3

Zawody matematyczne:

XXVIII OM, 1976-1977

Etap:

Niech $a$ i $b$ będą liczbami naturalnymi. Prostokąt o bokach długości $a$ i $b$ podzielono prostymi równoległymi do boków na kwadraty jednostkowe. Przez wnętrza ilu kwadratów przechodzi przekątna prostokąta ?

Rozwiązanie

Niech dany prostokąt $ABCD$ ma podstawę $\overline{AB}$ długości $a$ i wysokość $\overline{BC}$ długości $b$ . Rozważmy jego przekątną $\overline{AC}$ łączącą lewy dolny wierzchołek $A$ z prawym górnym wierzchołkiem $C$ (rys. 4).

Załóżmy najpierw, że liczby $a$ i $b$ są względnie pierwsze. Gdyby pewien wierzchołek $E$ kwadratu jednostkowego zawarty wewnątrz prostokąta $ABCD$ należał do $\overline{AC}$ , to mielibyśmy $\displaystyle \frac{a}{b}= \frac{AB}{BC} = \frac{AF}{EF}$ , czyli $a \cdot EF = b \cdot AF$ , gdzie $F$ jest rzutem punktu $E$ na prostą $AB$ . Ponieważ liczby $a$ i $b$ są względnie pierwsze, a liczby $EF$ i $AF$ - naturalne, więc z ostatniej równości wynika, że $a$ jest dzielnikiem liczby $AF$ . Jest to niemożliwe, ponieważ $AF < AB = a$ .

Uzyskana sprzeczność dowodzi, że przekątna $AC$ nie przechodzi przez żaden wierzchołek kwadratu jednostkowego zawarty wewnątrz prostokąta $ABCD$ . Wyznacza więc ona ciąg kwadratów jednostkowych, których wnętrza kolejno przecina. Każdy następny kwadrat ciągu ma bok wspólny z kwadratem poprzednim i jest położony na prawo od niego lub nad nim. Idąc wzdłuż drogi wyznaczonej przez kwadraty tego ciągu wykonujemy $a - 1$ przesunięć w prawo i $b - 1$ przesunięć do góry. Razem mamy więc $a + b - 2$ przesunięcia, czyli droga składa się z $a + b - 1$ kwadratów, tzn. przekątna $\overline{AC}$ przechodzi przez wnętrza $a + b - 1$ kwadratów jednostkowych.

Jeżeli zaś liczby $a$ i $b$ nie są względnie pierwsze i ich największy wspólny dzielnik jest równy $d$ , to niech $a = da'$ , $b = db'$ . Wtedy liczby $a'$ i $b'$ są względnie pierwsze. Przekątna prostokąta o bokach, długości $a$ i $b$ składa się z $d$ równych odcinków, z których każdy jest przekątną pewnego prostokąta o bokach długości $a'$ i $b'$ . Na podstawie już rozpatrzonego przypadku każdy taki odcinek przekątnej przechodzi przez wnętrza $a' + b' - 1$ kwadratów jednostkowych i wobec tego cała przekątna przechodzi przez wnętrza $d(a' + b' - 1) = a + b - d$ kwadratów jednostkowych.