OMA Foros

En un campamento matemático hay $2018$ niños. El animador tiene $4036$ fichas. Hay dos fichas con cada uno de los números del $1$ al $2018$, es decir: hay dos fichas con el $1$, dos fichas con el $2$, y así siguiendo hasta dos fichas con el $2018$.
Se le entregan dos fichas con números distintos a cada niño. No puede haber dos niños que reciban los mismos dos números.
A continuación los niños se acomodan de manera que se cumpla la siguiente condición: cada niño queda tomado de la mano con cada uno de los dos niños que tienen un número en común con él.
Un trueque consiste en pedir a dos niños que intercambien una de sus fichas y se reacomoden de manera que se siga cumpliendo la condición anterior.
Si los $2018$ niños no quedaron en una misma ronda, el animador puede hacer trueques para lograr que formen una sola gran ronda. Pero cada vez que hace un trueque, debe depositar una moneda en la alcancía.
¿Cuál es la menor cantidad de monedas que necesita tener el animador para estar seguro de que con cualquier distribución inicial de las fichas puede conseguir una gran ronda haciendo trueques?

Me ha gustado este problema.

Spoiler: mostrar

Tome los niños como vértices de un grafo G y conecte una arista entre dos vértices si y solo si los dos niños correspondientes están tomados de la mano en la configuración actual. Tenga en cuenta que este es un grafo donde todos los vértices tienen grado 2.

Afirmación: G es una unión disjunta de ciclos mayor o igual a 3.
Prueba: Considere el siguiente algoritmo (supongamos que en el momento k tenemos el grafo G_k y G_0 = G):
1) Considere el camino más largo de G_k: N_1, N_2, ..., N_t (tamaño t)
2) Tenga en cuenta que N_1 y N_l deben estar conectados porque ninguno de los dos puede estar conectado a alguien fuera del camino (contradeciría la maximidad) y a nadie dentro del camino (todos los que están dentro ya están conectados a otros dos vértices).
3) Tal camino es un bucle y tiene una intersección vacía con el resto del grafo. Elimine este ciclo y considere G_(k+1) el grafo restante y repita el algoritmo hasta que no quede vértice.
Termina porque cada ciclo tiene al menos 3 niños y la cantidad de niños es finita.

Observe ahora qué sucede después de una operación realizada por el animador:
1) Si la operación se realiza con dos hijos del mismo ciclo, no cambia la conexión del grafo, solo cambia el orden de los hijos en este ciclo.
2) En este caso, observe que si los hijos son A y B y sus vecinos son A_1, A_2, B_1 y B_2 respectivamente, tendremos que B se desconectará de B_j ahora se conectará a A_i, mientras que A se desconectará de A_i y se conectará a B_j, con i, j numera entre 1 y 2. Tenga en cuenta que, por lo tanto, los ciclos de ambos niños se fusionan y ahora tenemos exactamente un ciclo menos en el grafo.

Por lo tanto, como el animador quiere gastar la menor cantidad de monedas posible, solo realizará operaciones con niños de diferentes ciclos. Además, la cantidad de operaciones requeridas para hacer que todos los niños formen un ciclo grande es el número inicial de ciclos menos 1. Como no hay ciclos de tamaño 2 o 1 y 2018 = 3 * 672 + 2 = 3 * 671 + 5, inicialmente hay como máximo 671 ciclos en el grafo (671 de tamaño 3 y 1 de tamaño 5). Por lo tanto, el animador siempre puede cumplir su tarea con 670 monedas.