IMO 1972

Key idea: pigeonhole. There are more subsets than possible sums.

Ten numbers have $2^{10}-1=1023$ nonempty subsets. Every subset sum is at most $90+91+\dots+99=945$. So two different subsets $X\ne Y$ have the same sum.

Remove the common elements: $X'=X\setminus Y$ and $Y'=Y\setminus X$ are disjoint and still have equal sums (we subtracted the same amount from both). Neither is empty: if, say, $X'$ were empty, then $Y'$ would have sum $0$, so $Y'$ would be empty too, and $X=Y$. So $X'$ and $Y'$ are the required subsets.

Key idea: three kinds of pieces do all the work. A triangle splits into three cyclic kites, an isosceles trapezoid splits into any number of isosceles trapezoids, and a “pinwheel” around one inner point gives four cyclic pieces at once.

Let $ABCD$ be the cyclic quadrilateral, with angles $A,B,C,D$, so $A+C=B+D=180^\circ$. Recall that a quadrilateral is cyclic when two opposite angles add up to $180^\circ$.

Tools.

1. Triangle into 3. In a triangle, the incenter, two touch points, and the vertex between them form a quadrilateral with right angles at the touch points. It is cyclic, and three of them fill the triangle.
2. Isosceles trapezoid into any number. Lines parallel to the bases cut it into thinner trapezoids with the same base angles. These are isosceles, hence cyclic. (A rectangle is a special case.)
3. Parallel cut. If $E$ is on $AD$, $F$ is on $BC$, and $EF\parallel DC$, then $\angle AEF=\angle ADC$, so $\angle AEF+\angle ABF=D+B=180^\circ$ and $ABFE$ is cyclic.

Five or more pieces. If $ABCD$ is a rectangle, use tool 2. Otherwise two neighboring angles differ; label so that $C>D$. Take $E$ on $AD$ close to $D$, then $F$ on $BC$ with $EF\parallel DC$, and $G$ on $DC$ with $\angle EGC=C$. (As $E$ approaches $D$, $F$ approaches $C$ and $G$ approaches $D$, so for $E$ close enough all three points are inside their sides.) Now:

• $ABFE$ is cyclic, by tool 3;
• $EFCG$ has $EF\parallel GC$ and equal base angles $\angle EGC=\angle FCG=C$, so it is an isosceles trapezoid; cut it into $n-4$ pieces with tool 2;
• triangle $EDG$ has angles $D$, $180^\circ-C$ and $C-D>0$; cut it into 3 pieces with tool 1.

That makes $1+(n-4)+3=n$ cyclic pieces.

Exactly four pieces: the pinwheel. Take a point $P$ inside a convex quadrilateral and an angle $x$ between $0^\circ$ and $180^\circ$. Go around the quadrilateral counterclockwise. On each side $VW$ ($V$ first) mark the point $X$ with $\angle PXV=x$, and join it to $P$. The piece around vertex $A$ is $P\,X_{DA}\,A\,X_{AB}$. Its angles at the two marked points are $180^\circ-x$ and $x$, which add up to $180^\circ$, so it is cyclic. The same is true for all four pieces, and they tile the quadrilateral, as long as every marked point lies inside its side.

When are the marked points inside the sides? At each vertex $V$, the segment $VP$ splits the angle into a forward part $f_V$ (toward the next vertex) and a backward part $g_V$. As $X$ runs along side $VW$ from $V$ to $W$, the angle $\angle PXV$ falls from $180^\circ-f_V$ to $g_W$. So we need $$\max_V g_V<x<180^\circ-\max_V f_V,$$ and such an $x$ exists exactly when $g_V+f_W<180^\circ$ for every pair of vertices $V,W$.

Choosing $P$. Label so that $D\le90^\circ$ (then $B\ge90^\circ$). Let $P$ be the point of the diagonal $AC$ with $\angle PBC=\angle ABD$, so that also $\angle PBA=\angle DBC$. For $V=W$ the sum is the angle $V<180^\circ$. The twelve other sums:

• Six are two angles of one triangle: $g_A+f_C$ (triangle $ACD$), $g_C+f_A$ ($ABC$), $g_A+f_D$ ($APD$), $g_B+f_A$ ($ABP$), $g_C+f_B$ ($BPC$), $g_D+f_C$ ($CPD$).
• $(g_B+f_D)+(g_D+f_B)=B+D=180^\circ$ and all four parts are positive, so both sums are below $180^\circ$.
• With inscribed angles, $\angle CAD=\angle CBD$ and $\angle ACD=\angle ABD$. So $g_A+f_B=\angle CBD+\angle ABD=B$ and $g_B+f_C=\angle DBC+\angle ABD=B$, both below $180^\circ$.
• $g_C+f_D$ and $g_D+f_A$: here $f_D,g_D<D\le90^\circ$, while $g_C=\angle ACB$ and $f_A=\angle CAB$ are less than $180^\circ-B=D\le90^\circ$.

So a suitable $x$ exists, and the pinwheel cuts $ABCD$ into four cyclic quadrilaterals. (Each piece is convex: its angles are $x$, $180^\circ-x$, the vertex angle, and, at $P$, $180^\circ$ minus the vertex angle.)

Together, every cyclic quadrilateral can be cut into $n$ cyclic quadrilaterals for each $n\ge4$.

Key idea: the quotients satisfy a recurrence with integer coefficients, and the starting values are central binomial coefficients.

Let $$f(m,n)=\frac{(2m)!\,(2n)!}{m!\,n!\,(m+n)!}.$$ Changing one variable by $1$ gives $$f(m+1,n)=f(m,n)\cdot\frac{(2m+2)(2m+1)}{(m+1)(m+n+1)}=f(m,n)\cdot\frac{2(2m+1)}{m+n+1},$$ and in the same way $f(m,n+1)=f(m,n)\cdot\frac{2(2n+1)}{m+n+1}$. Adding these, $$f(m+1,n)+f(m,n+1)=f(m,n)\cdot\frac{4m+2+4n+2}{m+n+1}=4f(m,n).$$ So $$f(m,n+1)=4f(m,n)-f(m+1,n).$$

Now induct on $n$. For $n=0$, $f(m,0)=\frac{(2m)!}{m!\,m!}=\binom{2m}m$ is an integer for every $m$. If $f(m,n)$ is an integer for every $m$, the relation shows the same for $f(m,n+1)$. So $f(m,n)$ is always an integer.

Key idea: the sum of the five left sides is a sum of squares. It is also at most $0$, so every square vanishes.

Let $S$ be the sum of the five left-hand sides. Each is $\le0$, so $S\le0$. Expanding and grouping (a direct check), twice the sum is $$\begin{aligned}2S={}&x_1^2\left[(x_2-x_4)^2+(x_3-x_5)^2\right]+x_2^2\left[(x_1-x_4)^2+(x_3-x_5)^2\right]\\&+x_3^2\left[(x_1-x_4)^2+(x_2-x_5)^2\right]+x_4^2\left[(x_1-x_3)^2+(x_2-x_5)^2\right]\\&+x_5^2\left[(x_1-x_3)^2+(x_2-x_4)^2\right].\end{aligned}$$ (Both sides have the ten terms $2x_i^2x_j^2$ and the same ten terms of the form $-2x_i^2x_jx_k$.) So $S\ge0$, hence $S=0$ and every bracket vanishes, since all $x_i>0$. The $x_1^2$ and $x_2^2$ terms give $x_2=x_4$, $x_3=x_5$ and $x_1=x_4$; the $x_3^2$ term gives $x_2=x_5$. So all five are equal.

Conversely, if all five are equal to $t>0$, every factor is $t^2-t^2=0$ and all five inequalities hold.

Key idea: a value $|g(y_0)|>1$ would push the supremum of $|f|$ below itself.

Let $M=\sup_x|f(x)|$. Then $0<M\le1$, since $f$ is bounded by $1$ and not identically zero. Suppose $|g(y_0)|>1$ for some $y_0$. For every $x$, $$2|f(x)|\,|g(y_0)|=|f(x+y_0)+f(x-y_0)|\le 2M,$$ so $|f(x)|\le\dfrac{M}{|g(y_0)|}$ for all $x$. Taking the supremum over $x$ gives $M\le\dfrac{M}{|g(y_0)|}<M$, a contradiction. So $|g(y)|\le1$ for all $y$.

Key idea: instead of placing the tetrahedron, choose the planes’ normal direction. Three independent edge vectors let us prescribe any three heights, and scaling fixes the size.

Let the four planes be $z=0,\ a,\ b,\ c$ in a coordinate system whose $z$-axis is their common normal (shift so that one plane is $z=0$). Then $a,b,c$ are distinct and nonzero.

Take any regular tetrahedron with vertices $V_1,V_2,V_3,V_4$, and let $e_i=V_{i+1}-V_1$ for $i=1,2,3$. These three vectors are linearly independent, so the linear system $$e_1\cdot w=a,\qquad e_2\cdot w=b,\qquad e_3\cdot w=c$$ has a (unique) solution $w$, and $w\ne0$ because $a\ne0$. Let $u=w/|w|$ and scale the tetrahedron by the factor $\lambda=|w|$ about $V_1$. The scaled edge vectors $\lambda e_i$ satisfy $$(\lambda e_i)\cdot u=e_i\cdot w\in\{a,b,c\}.$$ So, measured along the unit vector $u$, the four vertices sit at heights $0,a,b,c$ above $V_1$. Finally move the scaled tetrahedron rigidly so that $V_1$ lies on the plane $z=0$ and $u$ points along the positive $z$-axis. Then its vertices lie on the four planes, one on each.