Balti Tee 1990 · Ülesanne 16
Kombinatoorika
A closed polygonal line is drawn on squared paper so that its links lie on the lines of the paper (the sides of the squares are equal to 1). The lengths of all links are odd numbers. Prove that the number of links is divisible by 4 .
Kui oled valmis
Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.
Ülevaade
Teemad
Invariandid ja monovariandid
Lahendused
Lahendus
Solution:
There must be an equal number of horizontal and vertical links, and hence it suffices to show that the number of vertical links is even. Let's pass the whole polygonal line in a chosen direction and mark each vertical link as "up" or "down" according to the direction we pass it. As the sum of lengths of the "up" links is equal to that of the "down" ones and each link is of odd length, we have an even or odd number of links of both kinds depending on the parity of the sum of their lengths.