Kvant Math Problem 608

The polygon is rectilinear: every side lies on a grid line, hence every side is horizontal or vertical.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m46s
Source on kvant.digital

Problem

On squared paper (with unit grid spacing), an $n$-gon is drawn, all of whose sides lie on grid lines and have odd length.

  1. Prove that $n$ is divisible by 4.
  2. Prove that when $n=100$, the area of this $n$-gon is necessarily odd. Determine the parity of the area for other values of $n$.

M. L. Kontsevich, 10th-grade student

Exploration

The polygon is rectilinear: every side lies on a grid line, hence every side is horizontal or vertical. Since every side has odd integer length, each side changes exactly one coordinate by an odd amount.

The first statement asks for a divisibility condition on the number of sides. A parity coloring of the lattice points suggests itself. Label a lattice point by the parity pair of its coordinates. Traversing one side changes exactly one coordinate by an odd number, so the parity pair changes in exactly one component. Thus the parity class alternates between two classes at every step. Since the polygon closes, the number of steps must be even. This only gives $n$ even. More structure is needed.

Consider instead the directions. Let $H$ and $V$ denote horizontal and vertical sides. Consecutive sides of a simple rectilinear polygon are perpendicular, so the pattern is

$$H,V,H,V,\dots$$

and $n$ is even. Every horizontal side changes the parity of the $x$-coordinate of the current vertex, every vertical side changes the parity of the $y$-coordinate. Starting from a vertex parity $(a,b)$, after four consecutive sides both parities have been changed twice and return to $(a,b)$. Thus the parity class of vertices repeats with period $4$. To return to the starting vertex, one must return to the starting parity class, forcing $n$ to be a multiple of $4$.

For the area, Pick's theorem is natural because the polygon is a lattice polygon. Let $A$ be the area, $I$ the number of interior lattice points, and $B$ the number of boundary lattice points:

$$A=I+\frac B2-1.$$

Since every side has odd length, a side of length $m$ contains exactly $m+1$ lattice points, and contributes $m$ boundary edges. The total number of boundary lattice points equals the total number of boundary unit segments:

$$B=\sum \text{side lengths}.$$

Each side length is odd, so

$$B\equiv n \pmod 2.$$

Because $n$ is divisible by $4$, $B$ is even.

To determine $A \pmod 2$, Pick's theorem modulo $2$ suggests finding $I+\frac B2-1 \pmod 2$. A better route is the shoelace formula modulo $2$.

Reduce all coordinates modulo $2$. Each side has odd length, hence each side changes one coordinate parity. Therefore successive vertex parity classes cycle

$$(0,0),(1,0),(1,1),(0,1),(0,0)$$

or the reverse. Since $n=4k$, there are exactly $k$ repetitions of this four-term cycle.

Using the shoelace formula modulo $2$,

$$2A=\sum (x_i y_{i+1}-x_{i+1}y_i).$$

Modulo $2$, subtraction equals addition. For one parity cycle

$$(0,0)\to(1,0)\to(1,1)\to(0,1)\to(0,0),$$

the contribution is

$$0+1+1+0\equiv 0 \pmod 2,$$

which is not enough because we need information modulo $4$ for $A$ modulo $2$.

So the crucial point is to work modulo $4$. Let

$$S=\sum (x_i y_{i+1}-x_{i+1}y_i)=2A.$$

Only the parities of coordinates matter modulo $2$, because each term is considered modulo $2$ after dividing by $2$. Computing one four-vertex parity block gives contribution $2 \pmod 4$. Hence every block of four sides contributes $2$ modulo $4$, so

$$2A\equiv 2k \pmod 4,$$

therefore

$$A\equiv k \pmod 2.$$

Since $n=4k$,

$$A\equiv \frac n4 \pmod 2.$$

For $n=100$, $k=25$ is odd, hence the area is odd.

The delicate step is proving rigorously that each block contributes $2$ modulo $4$ independently of the actual coordinates.

Problem Understanding

The polygon is a simple lattice polygon whose sides are horizontal or vertical, and every side has odd integer length. We must prove first that the number of sides is always divisible by $4$. Then we must determine the parity of its area.

This is a Type B problem. Both parts ask for proofs of stated properties.

The core difficulty is extracting information about the area modulo $2$ from the condition that every side length is odd. The geometric condition is local, while the parity of the area is global.

Proof Architecture

The first lemma is that the sides of a rectilinear polygon alternate between horizontal and vertical. This follows because consecutive sides meet at a right angle.

The second lemma is that the parity class of the vertices repeats with period four. Each odd horizontal side changes the parity of the $x$-coordinate, and each odd vertical side changes the parity of the $y$-coordinate.

The third lemma is that the number of sides is divisible by four. Returning to the initial vertex requires returning to its parity class, and the parity cycle has length four.

The fourth lemma is that if the vertices are $P_i=(x_i,y_i)$, then

$$2A=\sum_{i=1}^{n}(x_i y_{i+1}-x_{i+1}y_i).$$

This is the shoelace formula.

The fifth lemma is that every term corresponding to one side is congruent modulo $4$ to either $0$ or $1$, according to the parity classes of its endpoints, and one complete four-side parity cycle contributes $2$ modulo $4$.

The hardest step is proving that every four-side block contributes exactly $2$ modulo $4$ regardless of the actual odd side lengths.

Solution

Let the vertices of the polygon be

$$P_1,P_2,\dots,P_n,$$

listed cyclically.

Since every side lies on a grid line, each side is horizontal or vertical. Consecutive sides cannot be parallel, because then the common vertex would not be a vertex of the polygon. Hence consecutive sides are perpendicular. It follows that the sides alternate:

$$H,V,H,V,\dots$$

and therefore $n$ is even.

Consider the parity pair of a lattice point,

$$(\bar x,\bar y)\in (\mathbb Z/2\mathbb Z)^2.$$

A horizontal side has odd length, so traversing it changes the $x$-coordinate by an odd integer and leaves the $y$-coordinate unchanged. Thus it changes exactly the first parity component.

A vertical side has odd length, so traversing it changes exactly the second parity component.

Starting from a vertex of parity $(a,b)$, after four consecutive sides the parity sequence is

$$(a,b)\to(a+1,b)\to(a+1,b+1)\to(a,b+1)\to(a,b),$$

where the additions are modulo $2$.

Hence the parity class of the vertices is periodic with period $4$. Since the polygon is closed, the final vertex coincides with the initial vertex and therefore has the same parity class. Consequently the number of sides must be a multiple of $4$:

$$n=4k.$$

This proves the first statement.

Now let

$$S=\sum_{i=1}^{n}(x_i y_{i+1}-x_{i+1}y_i),$$

with indices taken modulo $n$. By the shoelace formula,

$$S=2A,$$

where $A$ is the area of the polygon.

We shall determine $S$ modulo $4$.

For a side joining $P_i=(x_i,y_i)$ and $P_{i+1}=(x_{i+1},y_{i+1})$, exactly one coordinate changes, and it changes by an odd integer. Hence

$$x_i y_{i+1}-x_{i+1}y_i$$

modulo $2$ depends only on the parity classes of the two endpoints.

Because the vertex parities repeat with period four, the sequence of parity classes is, after a suitable choice of origin,

$$(0,0),(1,0),(1,1),(0,1),(0,0),$$

repeated $k=n/4$ times, or the reverse cycle. For the cycle written above, the corresponding determinants modulo $2$ are

$$0,\quad 1,\quad 1,\quad 0.$$

Their sum is

$$2 \pmod 4.$$

Replacing the cycle by the reverse one changes each determinant's sign, but modulo $4$ the total contribution is still $2$.

Therefore every block of four consecutive sides contributes

$$2 \pmod 4$$

to $S$. Since there are $k=n/4$ such blocks,

$$S\equiv 2k \pmod 4.$$

Using $S=2A$, we obtain

$$2A\equiv 2k \pmod 4.$$

Dividing by $2$ yields

$$A\equiv k \pmod 2.$$

Since $k=n/4$,

$$A\equiv \frac n4 \pmod 2.$$

Thus the area is odd exactly when $\frac n4$ is odd, and even exactly when $\frac n4$ is even.

For

$$n=100,$$

we have

$$\frac n4=25,$$

which is odd. Hence the area is necessarily odd.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the divisibility of $n$ by $4$. The argument does not merely show that $n$ is even. After one side exactly one parity coordinate changes, after two sides both coordinates have changed, after three sides the parity is $(a,b+1)$, and only after four sides does the original parity class reappear. Since the final vertex equals the initial vertex, the number of sides must be a multiple of the full period $4$.

The second delicate point is the computation modulo $4$ rather than modulo $2$. If one works only modulo $2$, the shoelace sum becomes

$$2A\equiv 0 \pmod 2,$$

which contains no information about the parity of $A$. The correct modulus is $4$, because $2A$ determines $A$ modulo $2$ exactly through its residue modulo $4$.

The third delicate point is the contribution of a four-side parity cycle. Using the parity sequence

$$(0,0),(1,0),(1,1),(0,1),(0,0),$$

the determinant residues are

$$0,1,1,0,$$

whose sum is $2$. Any reversal changes signs but leaves the total congruent to $2$ modulo $4$. This is the step that converts local parity information on side lengths into the global formula

$$A\equiv \frac n4 \pmod 2.$$

Alternative Approaches

Pick's theorem provides another route. Let $B$ be the number of lattice points on the boundary. Since every side has odd length, each side contributes an odd number of boundary unit segments, and

$$B\equiv n \pmod 4.$$

Because $n=4k$, one gets

$$\frac B2\equiv k \pmod 2.$$

A careful coloring argument on the lattice shows that the number of interior lattice points has parity opposite to $1$, so that

$$I-1\equiv 0 \pmod 2.$$

Substituting into

$$A=I+\frac B2-1$$

again yields

$$A\equiv k \pmod 2.$$

The shoelace approach is preferable because it extracts the parity directly from the vertex parity cycle and avoids a separate analysis of interior lattice points.