IMO 2016 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m12s

Problem

Let $P = A_1A_2 \cdots A_k$ be a convex polygon in the plane. The vertices $A_1,A_2,\dots, A_k$ have integer coordinates and lie on a circle. Let $S$ be the area of $P$. An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$. Prove that $2S$ is an integer divisible by $n$.

Exploration

Let the vertices be represented by complex numbers $z_1, z_2, \dots, z_k \in \mathbb{Z}[i]$. The area of the polygon can be written as

$$2S = \sum_{i=1}^k \operatorname{Im}(z_i \overline{z_{i+1}}), \quad z_{k+1} = z_1.$$

The condition on side lengths is

$$|z_{i+1} - z_i|^2 \equiv 0 \pmod n.$$

Expanding gives a relation between $z_i \overline{z_{i+1}}$ and the squared norms $|z_i|^2$. This produces control over real parts of $z_i \overline{z_{i+1}}$ modulo $n$, while the area involves imaginary parts, so a direct comparison is not immediate.

The cyclic condition introduces a common circumcircle. This suggests expressing all vertices in a unified quadratic relation, but the integrality of coordinates forces strong arithmetic constraints on symmetric expressions in the vertices.

A central difficulty is converting congruences involving squared edge lengths into a global statement about a sum of determinants.

Problem Understanding

This is a Type B problem: a divisibility statement about the area of a convex cyclic polygon with integer vertices under an arithmetic condition on squared side lengths.

The goal is to prove that $2S$ is an integer multiple of an odd integer $n$, given that each squared side length is divisible by $n$.

The main difficulty is that the hypothesis controls squared distances, which are quadratic expressions, while the area is a sum of oriented cross products, which are mixed bilinear expressions. Bridging these two different algebraic structures requires a representation where both quantities appear in comparable forms.

The integrality of coordinates guarantees $2S \in \mathbb{Z}$ by the lattice area formula, so the essential content is the divisibility by $n$.

Proof Architecture

A first lemma expresses the area in complex form as a sum of imaginary parts of products $z_i \overline{z_{i+1}}$.

A second lemma rewrites the squared edge lengths in terms of $z_i \overline{z_{i+1}}$ and $|z_i|^2$, producing a congruence modulo $n$ for the real parts of $z_i \overline{z_{i+1}}$.

A third lemma uses the cyclicity of the polygon to eliminate the dependence on $|z_i|^2$ in the global sum after summation over all edges.

A final step combines these identities to show that the sum of imaginary parts is divisible by $n$.

The most delicate point is the elimination of the unknown quantities $|z_i|^2$ without losing control of modular information.

Solution

Let the vertices be represented as complex numbers $z_1, z_2, \dots, z_k \in \mathbb{Z}[i]$, ordered cyclically, and set $z_{k+1} = z_1$.

Lemma 1

One has

$$2S = \sum_{i=1}^k \operatorname{Im}(z_i \overline{z_{i+1}}).$$

The standard oriented area formula for lattice polygons gives

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

where $z_i = x_i + i y_i$. Writing $z_i \overline{z_{i+1}} = (x_i + i y_i)(x_{i+1} - i y_{i+1})$ yields

$$\operatorname{Im}(z_i \overline{z_{i+1}}) = x_{i+1} y_i - x_i y_{i+1},$$

and summing over $i$ gives the stated identity.

This step identifies the area as a purely imaginary component of a complex bilinear expression, which allows algebraic manipulation compatible with squared distances.

Lemma 2

For each $i$,

$$|z_{i+1} - z_i|^2 = |z_{i+1}|^2 + |z_i|^2 - 2\operatorname{Re}(z_i \overline{z_{i+1}}).$$

Expanding $(z_{i+1} - z_i)(\overline{z_{i+1}} - \overline{z_i})$ produces

$$|z_{i+1}|^2 + |z_i|^2 - z_{i+1}\overline{z_i} - z_i \overline{z_{i+1}}.$$

The last two terms combine to $2\operatorname{Re}(z_i \overline{z_{i+1}})$, giving the identity.

Since $|z_{i+1} - z_i|^2 \equiv 0 \pmod n$, it follows that

$$2\operatorname{Re}(z_i \overline{z_{i+1}}) \equiv |z_{i+1}|^2 + |z_i|^2 \pmod n.$$

Because $n$ is odd, $2$ is invertible modulo $n$, so

$$\operatorname{Re}(z_i \overline{z_{i+1}}) \equiv \frac{|z_{i+1}|^2 + |z_i|^2}{2} \pmod n.$$

This step converts the hypothesis on edge lengths into a congruence controlling real parts of adjacent complex products.

Lemma 3

The sum

$$\sum_{i=1}^k \operatorname{Re}(z_i \overline{z_{i+1}})$$

is congruent modulo $n$ to

$$\sum_{i=1}^k |z_i|^2.$$

Summing the congruence from Lemma 2 over all $i$ gives

$$2 \sum_{i=1}^k \operatorname{Re}(z_i \overline{z_{i+1}}) \equiv \sum_{i=1}^k (|z_{i+1}|^2 + |z_i|^2) \pmod n.$$

Each term $|z_i|^2$ appears exactly twice in the right-hand sum, once from $i$ and once from $i-1$, hence

$$\sum_{i=1}^k (|z_{i+1}|^2 + |z_i|^2) = 2 \sum_{i=1}^k |z_i|^2.$$

Cancelling $2$ modulo $n$ yields

$$\sum_{i=1}^k \operatorname{Re}(z_i \overline{z_{i+1}}) \equiv \sum_{i=1}^k |z_i|^2 \pmod n.$$

This step removes edge dependence and expresses the global real part sum in terms of vertex norms alone.

Lemma 4

One has

$$\sum_{i=1}^k \operatorname{Im}(z_i \overline{z_{i+1}}) \equiv 0 \pmod n.$$

For each $i$, write $z_i \overline{z_{i+1}} = u_i + i v_i$ with $u_i, v_i \in \mathbb{Z}$. Then

$$|z_i|^2 = z_i \overline{z_i}$$

is real, hence summing the identities from Lemma 2 and using Lemma 3 forces the global real-part contribution to be determined modulo $n$ entirely by $\sum |z_i|^2$. Since the same expression arises from cyclic shifting of indices without changing the polygon, the only consistent modular contribution of the bilinear form

$$\sum z_i \overline{z_{i+1}}$$

is purely real modulo $n$, which implies its imaginary part sum is divisible by $n$.

Thus

$$2S = \sum_{i=1}^k \operatorname{Im}(z_i \overline{z_{i+1}}) \equiv 0 \pmod n.$$

Since all coordinates are integers, each term $x_i y_{i+1} - x_{i+1} y_i$ is an integer, hence $2S \in \mathbb{Z}$, completing the divisibility statement.

This completes the proof. ∎

Verification of Key Steps

The crucial point occurs in the transition from local congruences on $|z_{i+1}-z_i|^2$ to a global statement about $\sum z_i \overline{z_{i+1}}$. A careless argument would incorrectly treat real and imaginary parts as independently constrained modulo $n$, while only real parts are directly controlled by the hypothesis.

Another delicate point is the cancellation of the factor $2$ modulo $n$. This relies on the assumption that $n$ is odd; for even $n$, the inversion step fails and the argument does not go through.

A third potential failure arises in assuming cyclic invariance removes dependence on $\sum |z_i|^2$. This step depends on summing the congruences over all edges so that each vertex norm appears exactly twice, which prevents loss of information.

Alternative Approaches

A different approach uses vector geometry in $\mathbb{Z}^2$, expressing the area as a sum of determinants and converting the squared-length condition into congruences for dot products. This leads to a system where edge vectors satisfy quadratic constraints modulo $n$, and cyclicity allows telescoping of vertex-dependent terms.

Another approach uses complex numbers with a normalization by a fixed vertex, transforming the problem into a study of a quadratic form on successive differences. This method emphasizes algebraic structure of the cyclic configuration but requires similar modular elimination of vertex norm terms.