Paisanos en una mesa redonda

Para cada entero n la maxima cantidad de personas que se pueden sentar es $n^2$

Sean $b_1,\cdots,b_n$ los paises. Algún representante de cierto pais tiene n opciones del pais que será el representante sentado a lado de él (a la derecha). Por lo tanto si hubiera $n+1$ representantes de dicho pais, por casillas dos de ellos tendrian a representantes del mismo pais sentados a sus lados, respectivamente. De esta manera si hay n, paises cada pais tiene a lo más $n$ representantes. Ahora hay que demsotrar que para cada n podemos acomodar $n^2$ personas.

Lo probaremos por induccion sobre n.

Caso base: n=2.  Hay dos representantes por ambos paises, asi colocamos  a los representantes del mismo pais uno a lado del otro. Cumple las condiciones, y acomodamos a $2^2$ personas.

Suponemos que para toda k podemos acomodar a $k^2$.

Y demostramos que para k+1 podemos acomodar a $(k+1)^2$ personas.

Usando la hipotesis de induccion acomodamos a $k^2$ personas, y  queremos acomodar a 2k+1 personas nuevas, k personas por cada pais que ya teniamos y k+1 personas de un pais nuevo.

Sean nuevamente $b_1,\cdots,b_{k+1}$ los paises.  Tratemos de acomodar las 2k +1 personas, por ejemplo sabemos que existe un representante de $b_1$ que tiene a su derecha un representante de $b_2$ y que existe un representante de $b_2$ que tiene a su derecha un representante de $b_3$ y asi sucesivamente para cada $i=1,2,\cdots,k$ sabemos que existe un representante de $b_i$ que tiene a su derecha un representante de $b_{i+1}$ si i=k entonces i+1=1. Entonces entre cada $b_i$ y $b_{i+1}$ colocamos un nuevo representante de $b_i$ de esta manera ya existen dos representantes de $b_i$ que tiene a su derecha un representante del mismo pais, pero este pais es exactamente  $b_i$  por lo entre dos representantes de $b_i$ (que se sienten juntos) colocamos un representante de $b_{k+1}$, de esta manera ningun representante de $b_i$ repite. Hacemos este acomodo patra cada i, y hemos colocado un representante de cada pais y k representantes del pais $b_{k+1}$ ya solo nos falta colocar un representante de $b_{k+1}$ como colocamos un representante de este pais entre dos representantes del mismo pais, quiere decir que $b_{k+1}$ ya tiene a de vecinos a $b_1,\cdots,b_k$ por lo que solo le falta tener de vecino a un representante de su mismo pais, asi lo colocamos a la derecha de cualquier representante de $b_{k+1}$ y con esto concluimos la induccion.

Saludos

Germán.