Baltic Way 1990 · Problem 16
Combinatorics
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 .
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Invariants and monovariants
Solutions
Solution
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.