IMO 2016 · Problem 3

Let \(P=A_1A_2\ldots A_k\) be a convex polygon in the plane. The vertices \(A_1, A_2, \ldots, A_k\) have integral 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\).

Official text of the problem. Official problem paper (PDF)

Solution

For vectors \(u=(u_x,u_y)\) and \(v=(v_x,v_y)\), write \[ [u,v]=u_xv_y-u_yv_x. \] If \(S=0\), the conclusion is immediate. Otherwise, orient the vertices counterclockwise and set \(A_{k+1}=A_1\). The shoelace formula gives \[ 2S=\sum_{i=1}^k[A_i,A_{i+1}]\in\mathbb Z. \]

Let \(O\) and \(R\) be the centre and radius of the circle. Both coordinates of \(O\) are rational: subtracting the equations \[ |A_i-O|^2=|A_j-O|^2 \] gives linear equations with integer coefficients, and three noncollinear vertices give two independent such equations. Consequently, \(R^2\) is rational.

Fix any prime power \(p^e\mid n\), where \(p\) is odd. For a nonzero rational number \(t\), let \(v(t)\) denote its exponent of \(p\), and put \(v(0)=+\infty\). We use \[ v(xy)=v(x)+v(y),\qquad v(x+y)\geq\min\{v(x),v(y)\}, \] with equality in the second relation when the two valuations differ. Set \(r=v(R^2)\).

Case 1: \(r\geq e\). For each side, put \[ d_i=|A_{i+1}-A_i|^2,\qquad T_i=[A_i-O,A_{i+1}-O]. \] The two vectors in this determinant have squared length \(R^2\), and their dot product is \(R^2-d_i/2\). Thus \[ T_i^2 =R^4-\left(R^2-\frac{d_i}{2}\right)^2 =R^2d_i-\frac{d_i^2}{4}. \] Since \(v(d_i)\geq e\) and \(p\) is odd, both terms on the right have valuation at least \(2e\). Hence \(v(T_i)\geq e\).

Translation does not change the sum in the shoelace formula, because the extra terms telescope. Therefore \[ 2S=\sum_{i=1}^kT_i, \] so \(v(2S)\geq e\). This argument also covers \(T_i=0\), and does not require \(O\) to lie inside the polygon.

Case 2: \(r<e\). We first prove that, for any three distinct vertices \(X,Y,Z\), \[ p^e\mid |X-Y|^2,\quad p^e\mid |Y-Z|^2 \quad\Longrightarrow\quad p^e\mid |Z-X|^2. \]

Write \[ a=|X-Y|^2,\qquad b=|Y-Z|^2,\qquad c=|Z-X|^2, \qquad D=[Y-X,Z-X]. \] The dot-product identity and the circumradius formula give, respectively, \[ 4D^2=4ab-(a+b-c)^2, \qquad abc=4R^2D^2. \tag{1} \] For the second identity, the triangle has area \(|D|/2\), so the usual formula for its circumradius is \(\sqrt{abc}=2R|D|\). The three vertices are noncollinear because they are distinct points of a circle.

Suppose \(v(a),v(b)\geq e\), but \(f=v(c)<e\). Then \[ v(a+b-c)=f,\qquad v(4ab)\geq 2e>2f. \] The first identity in (1) therefore yields \(v(D)=f\). Taking valuations in the second gives \[ r=v(a)+v(b)+v(c)-2v(D) =v(a)+v(b)-f \geq 2e-f>e, \] contrary to \(r<e\). This proves the implication.

Starting with the side \(A_1A_2\), apply this implication successively to \[ (A_1,A_2,A_3),\ (A_1,A_3,A_4),\ \ldots,\ (A_1,A_{k-1},A_k). \] It follows that every squared length \(|A_1-A_j|^2\) is divisible by \(p^e\).

Thus all three squared side lengths of every triangle \(A_1A_jA_{j+1}\), for \(2\leq j\leq k-1\), are divisible by \(p^e\). By the first identity in (1), its signed double area \[ D_j=[A_j-A_1,A_{j+1}-A_1] \] satisfies \(v(4D_j^2)\geq 2e\). Since \(p\) is odd, \(v(D_j)\geq e\). These triangles partition the convex polygon, so \[ 2S=\sum_{j=2}^{k-1}D_j \] is divisible by \(p^e\).

We have proved this for every prime power dividing \(n\). Since \(2S\) is an integer, it follows that \(n\mid 2S\). \(\square\)

The solution was checked against the official IMO shortlist solutions.