Alrededor de una mesa redonda están sentados representantes de $n$ países ($n\geq 2$), de tal manera que si dos representantes son del mismo país, entonces sus vecinos de la derecha no son del mismo país. Determinar, para cada $n$, el número máximo de personas que pueden sentarse alrededor de la mesa.
Para cada entero n la maxima
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.