Hay dos mesas redondas, cada una de ellas tiene $n$ duendes sentados alrededor de ella. Cada duende tiene exactamente dos amigos y son los que están sentados junto a él, uno a su derecha y el otro a su izquierda. Un duende bueno quiere sentar a todos los duendes alrededor de una sola mesa redonda de modo que cada par de vecinos sean amigos. Sus poderes mágicos le permiten hacer que cualesquiera $2n$ pares de duendes se transformen en pares de amigos (los duendes de cada pareja pueden ser de la misma mesa o de mesas distintas) Sin embargo, él sabe que la hechicera maligna puede romper $n$ de esas nuevas amistades. Determinar para qué valores de $n$ el buen duende puede lograr su objetivo, no importa lo que haga la hechicera.
El duende puede lograr su objetivo para todo $n$ impar mayor a $1$.
Primero notemos que con $n=1$ sólo hay una amistad posible para armar, que la hechicera puede destruir. Ahora vamos a ver las estrategias para el duende y la hechicera cuando $n>1$ es impar o par, respectivamente.
$n$ impar:
Tenemos $n=2k+1$. Sean $a_1,\ldots,a_n$ los duendes de una mesa y $b_1,\ldots,b_n$ los duendes de la otra de manera que $a_i$ es vecino de $a_{i-1}$ y $a_{i+1}$ y análogamente ocurre con $b_i$ (tomamos los índices módulo $n$). Vamos a probar que si el duende bueno forma las amistades entre los pares $(a_i,b_i)$ (grupo $A$) y $(a_i,b_{i+1})$ (grupo $B$) para cada $i=1,2,\ldots,n$ entonces logra su cometido.
Notemos que en cada grupo hay $n$ amistades, luego en alguno de ellos la hechicera rompe a lo sumo $k$ de ellas. Supongamos sin pérdida de generalidad que es en el grupo $A$. Consideremos las $n$ parejas de vecinos $(a_i,a_{i+1})$, cada duende participa en exactamente $2$ parejas y tenemos $k$ duendes cuyas amistades con sus respectivos $b_i$ se rompieron, luego hay al menos un subíndice $j$ tal que las amistades entre $a_j,b_j$ y $a_{j+1},b_{j+1}$ no están rotas. Supongamos que $j=1$ (sino podemos renombrar a los duendes), se sigue que es posible sentar a todos los duendes de la siguiente forma: $$a_2,a_3,\ldots,a_n,a_1,b_1,b_n,b_{n-1},\ldots,b_2$$ con $a_2$ y $b_2$ siendo vecinos.
$n$ par:
Sean $m_1\leqslant m_2$ las cantidades de nuevas amistades formadas entre duendes de la misma mesa para cada mesa. Pintemos a los duendes de la mesa correspondiente a $m_1$ ($M$) alternadamente de rojo y azul y sean $s_1$ y $s_2$, respectivamente, la cantidad de amistades que formaron los duendes de cada color con los de la otra mesa. Supongamos sin pérdida de generalidad que $s_1\leqslant s_2$. Luego tenemos $2n=m_1+m_2+s_1+s_2\geqslant 2(m_1+s_1)\Rightarrow n\geqslant m_1+s_1$. Por lo tanto la hechicera puede romper todas las amistades nuevas entre los duendes de $M$ y entre los duendes rojos con la otra mesa, de manera que todos los duendes rojos permanezcan con exactamente los mismos $2$ amigos originales. De esta manera si el duende bueno trata de sentar a todos los demás en una mesa los vecinos de cada duende rojo están unívocamente determinados, los duendes azules, y no queda espacio para los de la otra mesa. $\bigstar$
"La suma de las raíces cuadradas de dos lados de un triángulo isósceles es igual a la raíz cuadrada del lado restante."
