IMO 1971

Key idea: after sorting, the terms pair up so that a positive term always outweighs its negative partner. For other $n$, repeated values kill all terms but one, and that one can be made negative.

Write $T_i=\prod_{j\ne i}(a_i-a_j)$, so the sum is $S=T_1+\dots+T_n$. The sum does not depend on the order of the numbers, so assume $a_1\ge a_2\ge\dots\ge a_n$.

$n=3$. Here $T_1=(a_1-a_2)(a_1-a_3)\ge(a_1-a_2)(a_2-a_3)=-T_2$, because $a_1-a_3\ge a_2-a_3\ge0$. And $T_3=(a_1-a_3)(a_2-a_3)\ge0$. So $S\ge0$.

$n=5$.

• $T_1+T_2\ge0$: $T_1=(a_1-a_2)\prod_{k=3}^5(a_1-a_k)$ and $-T_2=(a_1-a_2)\prod_{k=3}^5(a_2-a_k)$, and $a_1-a_k\ge a_2-a_k\ge0$ for $k\ge3$.
• $T_3=(a_1-a_3)(a_2-a_3)(a_3-a_4)(a_3-a_5)\ge0$.
• $T_4+T_5\ge0$: $T_5=\prod_{k=1}^4(a_k-a_5)\ge0$ and $-T_4=(a_4-a_5)\prod_{k=1}^3(a_k-a_4)$, and $a_k-a_5\ge a_k-a_4\ge0$.

So $S\ge0$.

Even $n\ge4$. Take $a_1=-1$ and $a_2=\dots=a_n=0$. Every $T_i$ with $i\ge2$ contains a factor $0$, and $T_1=(-1)^{n-1}=-1<0$.

Odd $n\ge7$. Take $a_1=0$, three numbers equal to $1$ and the remaining $n-4\ge3$ numbers equal to $-1$. Again only $T_1$ survives, and $T_1=(0-1)^3(0+1)^{n-4}=-1<0$.

(For $n=5$ this second construction fails, because then $-1$ appears only once.)

Key idea: all nine translates sit inside the solid scaled by $2$ from $A_1$, which has volume $8V$. Nine disjoint interiors of volume $V$ each cannot fit.

Let $V>0$ be the volume of $P_1$, and let $Q$ be the image of $P_1$ under the homothety with center $A_1$ and ratio $2$. Its volume is $8V$.

Each $P_i$ lies in $Q$. A point of $P_i$ has the form $x+(A_i-A_1)$ with $x\in P_1$. Since $P_1$ is convex and contains $x$ and $A_i$, it contains the midpoint $m=\frac{x+A_i}2$. The image of $m$ under the homothety is $A_1+2(m-A_1)=x+A_i-A_1$, our point. So it lies in $Q$.

Volumes. If the interiors of $P_1,\dots,P_9$ were pairwise disjoint, then (since the boundaries have volume zero) the union would have volume $9V$. But the union lies in $Q$, of volume $8V<9V$. So two of the interiors meet, and those two copies share an interior point.

Key idea: Euler’s theorem makes $2^{\varphi(s)}-3\equiv-2\pmod s$, which is prime to an odd $s$.

Start with $x_1=2^3-3=5$. Suppose we have chosen $x_1,\dots,x_m$, all of the form $2^k-3$ with $k\ge2$, pairwise coprime and all greater than $1$. Their product $s$ is odd and at least $5$. By Euler’s theorem $2^{\varphi(s)}\equiv1\pmod s$, so $$2^{\varphi(s)}-3\equiv-2\pmod s .$$ Since $s$ is odd, $\gcd(-2,s)=1$, so $x_{m+1}=2^{\varphi(s)}-3$ is prime to $s$, hence to each earlier $x_i$.

It is a valid new element: an odd $s\ge5$ has $\varphi(s)\ge4$, so the exponent is at least $2$ and $x_{m+1}\ge13>1$. And it differs from every earlier $x_i$, because it is prime to $x_i>1$. Repeating forever gives an infinite pairwise coprime subset.

Key idea: lay the four faces crossed by the path flat in a strip. A closed path becomes a broken line from a point $X$ to a copy $X'$ of it, where the copy comes from one rigid motion $R$ of the plane. If $R$ turns, a shortest path is impossible; if $R$ slides by a vector $v$, every path is at least $|v|$ long and many straight ones reach it.

The unfolding. Put face $DAB$ in the plane. Attach $ABC$ along $AB$, then $BCD$ along $BC$, then $CDA$ along $CD$, then a second copy of $DAB$ along $DA$, each new face on the far side of the shared edge. Call the points $D_1,A_1,B_1$ (first copy), $C$, $D'$, $A_2$, $B_2$. The strip consists of the triangles $A_1B_1C$, $B_1CD'$, $CD'A_2$, $D'A_2B_2$. The two copies of $DAB$ are related by a motion $R$ of the plane that keeps orientation, with $R(A_1)=A_2$ and $R(B_1)=B_2$.

A path $XYZTX$ becomes the broken line $X\,Y\,Z\,T_2\,X'$, where $X'=R(X)$ and $T_2$ is $T$ on $D'A_2$. Each piece lies in one face, so the length is unchanged.

How much $R$ turns. Walk along $A_1\to B_1\to C\to D'\to A_2\to B_2$. Each triangle of the strip has two consecutive steps of the walk as sides, and the triangles lie alternately on the left and on the right. So the walk turns left by $180^\circ$ minus $\angle ABC$, right by $180^\circ$ minus $\angle BCD$, left by $180^\circ$ minus $\angle CDA$, right by $180^\circ$ minus $\angle DAB$. The direction of $A_2B_2$ differs from that of $A_1B_1$ by $$\theta=(\angle DAB+\angle BCD)-(\angle ABC+\angle CDA).$$ Each sum is between $0^\circ$ and $360^\circ$, so $R$ is a translation if the sums are equal and a rotation by $\theta\ne0$ otherwise.

(a) Unequal sums. Suppose a shortest path exists. Fix $X,Z,T$ and move $Y$ along edge $BC$. In the unfolding of the two faces at $BC$, $|XY|+|YZ|$ is a convex function of $Y$ on line $BC$, smallest only where segment $XZ$ crosses that line. As $Y$ is an inner point of the edge and gives a minimum, $X,Y,Z$ are collinear in the unfolding. The same holds at $Z$, at $T$, and at $X$ (unfold $DAB$ and $ABC$ along $AB$). So $XYZT_2X'$ is one straight segment with some direction $u$. The condition at $X$ says that $T_1X$ in the first copy (where $T_1$ is $T$ on $D_1A_1$) also has direction $u$. The motion $R$ carries $T_1X$ to $T_2X'$, so its turning part fixes the direction $u$, and $\theta=0$. Hence with unequal sums there is no shortest path.

(b) Equal sums. Now $R$ is the translation by a vector $v$, and every path has length at least $|XX'|=|v|$.

The length of $v$. Use coordinates with $A_1$ at the origin, $A_1B_1$ along the positive $x$-axis, and $C$ above it. Let $a_1=\angle BAC$, $a_2=\angle CAD$, $a_3=\angle DAB$, so $\alpha=a_1+a_2+a_3$. Ray $A_1C$ has direction angle $a_1$. A translation keeps directions, so $A_2B_2$ points along the $x$-axis and $A_2D'$ has direction $-a_3$, like $A_1D_1$. Since $C$ is across line $A_2D'$ from $B_2$, ray $A_2C$ has direction $-(a_2+a_3)$. Therefore $$v=(C-A_1)-(C-A_2)=AC\big[(\cos a_1,\sin a_1)-(\cos(a_2+a_3),\,-\sin(a_2+a_3))\big]=2\,AC\sin\tfrac{\alpha}{2}\,(\sin\delta,\cos\delta),$$ with $\delta=\frac12(a_2+a_3-a_1)$. So $|v|=2\,AC\sin\frac{\alpha}{2}$, which is positive because $\alpha<360^\circ$.

Many straight paths. All faces are acute, so every $a_i<90^\circ$, $|\delta|<90^\circ$, and $v$ points upward. Measure each point’s offset across the direction of $v$ by $o(P)=P\cdot(\cos\delta,-\sin\delta)$. Then $o(A_1)=o(A_2)=0$, $o(B_1)=o(B_2)=AB\cos\delta>0$, and $$o(C)=AC\cos\tfrac{\alpha}{2},\qquad o(D')=AD\cos\tfrac{a_1+a_3-a_2}{2}>0.$$ We claim $o(C)<o(B_1)$ and $o(C)<o(D')$. Let $b=\angle ABC$ and $c=\angle ACB$. The law of sines gives $AC=AB\sin b/\sin(a_1+b)$, and expanding, $$o(B_1)-o(C)=\frac{AB\sin a_1}{\sin(a_1+b)}\,\cos(b-\delta).$$ Here $b-\delta>-90^\circ$. Also $b-\delta<90^\circ$ is the same as $b-c<a_2+a_3$, which holds because $b-c<180^\circ-b-c=a_1<a_2+a_3$. (We used $b<90^\circ$, and the fact that a face angle at a corner of a tetrahedron is less than the sum of the other two.) The second claim is the same computation in face $ACD$, using $\angle ADC<90^\circ$.

So the interval $\big(\max(0,o(C)),\ \min(o(B_1),o(D'))\big)$ is not empty. Pick any $X$ on $A_1B_1$ with $o(X)$ in it; there are infinitely many. The line through $X$ in direction $v$ has $A_1,C,A_2$ strictly on one side and $B_1,D',B_2$ strictly on the other. Starting at $X$, it enters triangle $A_1B_1C$ and must leave through $B_1C$ (both ends of $A_1C$ are on the same side). Then it crosses $B_1CD'$ and leaves through $CD'$, crosses $CD'A_2$ and leaves through $D'A_2$, and leaves $D'A_2B_2$ through $A_2B_2$ at the point $X+v$. Folding the strip back gives a closed path with inner points on the four edges and length $|v|$, the least possible.

So there are infinitely many shortest paths, all of length $2\,AC\sin\frac{\alpha}{2}$.

Key idea: take the set and a copy shifted by a unit vector chosen in a generic direction. Each point gains exactly one new unit neighbor: its own copy.

Call a finite set $m$-good if every point has exactly $m$ points of the set at distance $1$. A single point is $0$-good. We show: if $S$ is $m$-good, then for a suitable unit vector $v$ the set $S'=S\cup(S+v)$ is $(m+1)$-good, with $2|S|$ points.

Bad directions. For points $x,y\in S$:

• $x+v=y$ happens for at most one unit vector $v$ (when $|y-x|=1$).
• For $x\ne y$, the condition $|x+v-y|=1$ says that $v$ lies on the unit circle centered at $y-x$. That circle and the unit circle centered at $0$ are different, so they share at most $2$ points.

There are finitely many pairs, so we can choose a unit vector $v$ avoiding all of these.

Counting neighbors. Then $S$ and $S+v$ are disjoint, so $S'$ has $2|S|$ points. Take $x\in S$. Its unit neighbors in $S$ are the same $m$ as before. In $S+v$, a point $y+v$ is at distance $1$ from $x$ only if $y=x$ (by the choice of $v$), and $x+v$ is indeed at distance $|v|=1$. So $x$ has exactly $m+1$ unit neighbors. The same argument works for points of $S+v$.

Starting from one point and repeating $m$ times gives an $m$-good set with $2^m$ points.

Key idea: take the line with the smallest sum $k$. Its zeros force big sums on the crossing lines, and all other crossing lines are at least $k$; the total is at least $(n-k)^2+k^2$.

Among all $2n$ rows and columns, choose one with the smallest sum $k$; by symmetry say it is row $r$. If $k\ge\frac n2$, then all $n$ rows have sum at least $\frac n2$ and the total is at least $\frac{n^2}2$.

So suppose $k<\frac n2$. Row $r$ has at most $k$ nonzero entries (they are positive integers adding up to $k$), so it has $z\ge n-k$ zeros. For each zero $a_{rj}=0$, row $r$ and column $j$ together have sum at least $n$, so column $j$ has sum at least $n-k$. Every other column has sum at least $k$, by the choice of $k$. Adding up the columns, $$\text{total}\ge z(n-k)+(n-z)k=nk+z(n-2k)\ge nk+(n-k)(n-2k),$$ using $n-2k>0$ and $z\ge n-k$. The right side equals $(n-k)^2+k^2$, and $$(n-k)^2+k^2=\frac{n^2}{2}+\frac{(n-2k)^2}{2}\ge\frac{n^2}2 .$$