Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Está claro que no pueden sentarse más de $n^2$ personas cumpliendo esta condición, ya que en tal caso habría al menos $n+1$ de algún país por el principio del palomar y alguna de las personas a su lado tendría que ser del mismo país ya que sólo hay $n$ países (de nuevo por el principio del palomar. Vamos a ver que efectivamente pueden sentarse $n^2$ personas cumpliendo la propiedad, luego este será el máximo.

Vamos a encontrar la forma de sentarse por inducción sobre $n$. Para el caso base $n=2$, la forma de sentarse es 1221 (cíclicamente), siendo 1 un representante del primer país y 2 un representante del segundo. Ahora bien, para añadir un tercer país añadimos 33231 al inicio de la cadena, para añadir un cuarto país añadimos 4434241, para añadir un quinto país añadimos 554535251 y así sucesivamente, obteniendo las cadenas cíclicas \begin{align*} 1221,\\ 332311221,\\ 4434241332311221,\\ 5545352514434241332311221,\ldots \end{align*} En el paso $n$ se añade la cadena $nn(n-1)n(n-2)\ldots n1$ formada por $2n-1$ números. Como la suma de los impares entre $1$ y $2n-1$ es $n^2$, deducimos que tenemos así $n^2$ números para $n$ países. Ahora bien, cada número $k\lt n$ tiene a su derecha a cada uno de los números entre $1$ y $n-1$ una única vez por hipótesis de inducción y una vez al $n$ en la cadena añadida en el paso $n$. Por su parte, el número $n$ tiene a su derecha una vez a cada uno de los números entre $1$ y $n$ en la cadena añadida en el paso $n$. Por lo tanto, hemos probado que el número máximo es $n^2$.