IMO 1999

Key idea: all the reflections fix the centroid, so the points lie on a circle around it. Reflecting in the bisector of second neighbors shows that consecutive gaps are equal.

On a circle. Let $G$ be the centroid of $S$. A reflection that maps $S$ to itself maps $G$ to the centroid of the image, which is $G$. So $G$ lies on the perpendicular bisector of every pair $A,B$, that is $GA=GB$. All points are equally far from $G$.

Equal gaps. List the points around the circle as $P_1,\dots,P_n$ (indices mod $n$, $n\ge3$). The reflection in the perpendicular bisector of $P_iP_{i+2}$ swaps $P_i$ and $P_{i+2}$ and maps the arc between them that contains $P_{i+1}$ to itself. The only point of $S$ inside that arc is $P_{i+1}$, so it is mapped to itself, and it lies on the axis: it is the midpoint of the arc. So $P_iP_{i+1}=P_{i+1}P_{i+2}$ for all $i$, and $S$ is a regular polygon.

Converse. For a regular $n$-gon, the perpendicular bisector of two vertices passes through the center at an angle that is a multiple of $\frac\pi n$ from a vertex, which is one of the polygon’s mirror lines.

Key idea: replace each $x_i^2+x_j^2$ by the full sum of squares, then AM–GM on $p$ and $2q$.

Let $p=\sum x_i^2$ and $q=\sum_{i<j}x_ix_j$, so $\big(\sum x_i\big)^2=p+2q$. Since all $x_k\ge0$, $x_i^2+x_j^2\le p$, so $$\sum_{i<j}x_ix_j(x_i^2+x_j^2)\le p\,q=\frac18\cdot4\,p\,(2q)\le\frac18(p+2q)^2=\frac18\Big(\sum x_i\Big)^4 .$$ So $C=\frac18$ works.

Equality. We need $x_i^2+x_j^2=p$ whenever $x_ix_j>0$, and $p=2q$ (or both sides $0$). If three numbers are positive, the first fails. If exactly one is positive, the left side is $0$ and the right is not. If exactly two are positive, say $x,y$, then $p=x^2+y^2$ and $q=xy$, and $p=2q$ forces $x=y$. Indeed for $x_1=x_2=1$ and the rest $0$, both sides equal $2$. So $C=\frac18$ is the least constant, with equality exactly when two values are equal and the rest are $0$, or all are $0$.

Let $n=2k$. Number rows and columns $1,\dots,n$, and call cell $(i,j)$ black if $i+j$ is even and white if $i+j$ is odd.

Key idea: neighbors have opposite colors, so the black marks must serve the white cells and the white marks must serve the black cells. Each half needs exactly $1+2+\dots+k=\frac{k(k+1)}2$ marks, so $N=k(k+1)=\frac{n(n+2)}4$.

The mirror map $(i,j)\mapsto(i,\,n+1-j)$ keeps neighbors as neighbors and swaps the colors (because $n$ is even). So it is enough to show that the least number of black cells such that every white cell has one of them as a neighbor is $\frac{k(k+1)}2$.

Lower bound. Two white cells share a black neighbor exactly when their distance (counting row steps plus column steps) is $2$: two apart in a line, or diagonal neighbors. So if $S$ is a set of white cells with no two at distance $2$, each cell of $S$ needs its own marked neighbor, and at least $|S|$ black cells are marked.

Number the square rings from the outside: cell $(i,j)$ is in ring $t=\min(i,\,j,\,n+1-i,\,n+1-j)$. Let $$S=\{\text{white cells }(i,j)\text{ with } i-j\equiv3\pmod4\text{ in a ring with odd number}\}.$$

• No two at distance 2. For two cells of $S$, the values of $i-j$ differ by a multiple of $4$. A step $(\pm2,0)$, $(0,\pm2)$ or $(\pm1,\mp1)$ changes $i-j$ by $2$, so the two cells would differ by $\pm(1,1)$. Write $\mu=\min(i,j)$ and $\nu=\min(n+1-i,n+1-j)$ for the lower cell, so its ring is $\min(\mu,\nu)$. The step $(1,1)$ raises $\mu$ by $1$ and lowers $\nu$ by $1$. The ring numbers differ by at most $1$ and are both odd, so they are equal, and that happens only when $\nu=\mu+1$. Then $\min(i,j)=\mu$ and $\max(i,j)=n-\mu$, so $i+j=n$ is even and the cell is black, not white. So no two cells of $S$ are at distance $2$.
• Its size. Ring $t$ is a square frame of side $2m$ with $m=k+1-t$, and it has $4m-2$ white cells. Going around the frame, consecutive white cells differ by $(0,\pm2)$ or $(\pm2,0)$ along a side, and by $(\pm1,\mp1)$ at the two black corners. Each such step changes $i-j$ by $2$, so $i-j \bmod 4$ alternates between $1$ and $3$, and exactly $2m-1$ of the white cells of the ring have $i-j\equiv3$. The odd rings have $m=k,\,k-2,\,k-4,\dots$, so $$|S|=(2k-1)+(2k-5)+\dots=\big(k+(k-1)\big)+\big((k-2)+(k-3)\big)+\dots=\frac{k(k+1)}2.$$

Construction. Mark the black cells $(i,j)$ with $i+j$ divisible by $4$ that have both coordinates odd when $i+j\le n$, and both coordinates even when $i+j\ge n+2$.

• Every white cell is served. For a white cell $(i,j)$, $i+j$ is odd, so one of $i+j\pm1$ is divisible by 4; call it $\sigma$. The cell has two neighbors with coordinate sum $\sigma$: $(i+1,j),(i,j+1)$ or $(i-1,j),(i,j-1)$. Exactly one of $i,j$ is odd, so one of these two neighbors has both coordinates odd and the other has both even. Take the odd one if $\sigma\le n$ and the even one if $\sigma\ge n+2$; it is marked. It is on the board: a coordinate $n+1$ (odd) together with another coordinate at least $1$ would give $\sigma\ge n+2$, and a coordinate $0$ (even) together with another at most $n$ would give $\sigma\le n$.
• The count. On the line $i+j=\sigma\le n$ there are $\frac\sigma2$ cells with both coordinates odd; here $\frac\sigma2$ runs over the even numbers up to $k$. On the line $i+j=\sigma\ge n+2$ there are $n+1-\frac\sigma2$ cells with both coordinates even; here $n+1-\frac\sigma2$ runs over the odd numbers up to $k$. In total $1+2+\dots+k=\frac{k(k+1)}2$.

Mirroring this set gives the white marks. So the smallest possible value is $N=k(k+1)=\frac{n(n+2)}4$.

Key idea: the smallest prime of $n$ must be $p$ itself, so $n=p$, and lifting the exponent allows only $p=3$.

$n=1$ always works. Let $n\ge2$.

$p=2$: the condition is $n\mid2$ with $n\le4$, so $n=2$.

$p$ odd: $(p-1)^n+1$ is odd, so $n$ is odd. Let $q$ be its smallest prime factor. From $(p-1)^n\equiv-1\pmod q$, the order of $p-1$ mod $q$ divides $2n$ and $q-1$; the only prime factor of $q-1$ that can divide $2n$ is $2$, and only once. So the order divides $2$, and $(p-1)^2\equiv1$, that is $p-1\equiv\pm1\pmod q$. Since $n$ is odd, $p-1\equiv1$ would give $(p-1)^n\equiv1\ne-1$ (as $q$ is odd). So $p-1\equiv-1$, and $q\mid p$, so $q=p$.

Then $p\mid n$, $n$ is odd and $n\le2p$, so $n=p$. We need $p^{p-1}\mid(p-1)^p+1$. By lifting the exponent (for odd $p$ dividing $(p-1)+1$), $$v_p\big((p-1)^p+1\big)=v_p(p)+v_p(p)=2 .$$ So $p-1\le2$, $p=3$, and indeed $3^2\mid2^3+1=9$.

Key idea: a homothety at $M$ shows $CD\parallel AB$, so both are perpendicular to the line of centers. A short computation of where $CD$ crosses that line gives distance exactly $r_2$ from the center of $G_2$.

Let $G_1$ have center $O_1$ and radius $r_1$, $G_2$ center $O_2$ and radius $r_2$, $G$ center $O$ and radius $R$. Scale so $r_1=1$, and use coordinates with $O_1=(0,0)$ and $O_2=(1,0)$ (as $O_2$ lies on $G_1$).

Line $AB$. It is the radical axis of $G_1$ and $G_2$: $x^2+y^2-1=(x-1)^2+y^2-r_2^2$, so it is the vertical line $x=x_0$ with $x_0=1-\frac{r_2^2}2$.

Line $CD$. $G_1$ touches $G$ internally at $M$, so the homothety $h$ at $M$ with ratio $\frac1R$ maps $G$ to $G_1$, sending $A,B$ to the second points $C,D$ on lines $MA,MB$. So $CD=h(AB)$ is the vertical line $x=c$ with $c=m_x+\frac{x_0-m_x}R$, where $M=(m_x,m_y)$. Since $M$ is on ray $OO_1$ at distance $1$ from $O_1$, $M=-\frac{O}{R-1}$, so $m_x=-\frac{O_x}{R-1}$ and $$c=\Big(1-\frac1R\Big)m_x+\frac{x_0}R=\frac{x_0-O_x}R .$$

Finding $O_x$. Internal tangency gives $|O|=R-1$ and $|O-O_2|=R-r_2$. Subtracting the squares, $2O_x-1=(R-1)^2-(R-r_2)^2$, so $$O_x=1-R+Rr_2-\frac{r_2^2}2,\qquad x_0-O_x=R(1-r_2).$$ Hence $c=1-r_2$. The line $CD$ is the vertical line at distance $1-c=r_2$ from $O_2=(1,0)$, so it is tangent to $G_2$.

Key idea: first find $f$ on its own values. Then show that every real number is a difference of two values, and the equation evaluates $f$ there.

Let $c=f(0)$ and let $V$ be the set of values of $f$. $f\equiv0$ fails (it gives $0=-1$), so some $v_0\ne0$ is in $V$.

On $V$. For $v=f(y)$ and $x=v$: $c=f(v)+v^2+f(v)-1$, so $$f(v)=\frac{c+1}2-\frac{v^2}2\qquad(v\in V).$$

Differences of values. With $f(y)=v_0$, the equation gives $f(x-v_0)-f(x)=f(v_0)+xv_0-1$. As $x$ varies, the right side takes every real value. So every real $z$ is $f(u)-f(w)$ for some $u,w$: a difference $v_1-v_2$ with $v_1,v_2\in V$.

Everywhere. For $v_1,v_2\in V$, take $x=v_1$ and $y$ with $f(y)=v_2$: $$f(v_1-v_2)=f(v_2)+v_1v_2+f(v_1)-1=(c+1)-\frac{v_1^2+v_2^2}2+v_1v_2-1=c-\frac{(v_1-v_2)^2}2 .$$ So $f(z)=c-\frac{z^2}2$ for all $z$. Comparing with the formula on $V$ (at $v_0$) gives $c=\frac{c+1}2$, so $c=1$.

Check. With $f(x)=1-\frac{x^2}2$ and $v=f(y)$: the left side is $1-\frac{(x-v)^2}2$, and the right side is $1-\frac{v^2}2+xv+1-\frac{x^2}2-1=1-\frac{(x-v)^2}2$.