Juego de sustituir dos números por la media

Question

Alicia y Bart juegan a un juego. Alicia primero escribe $100$ números reales en el tablero. Después se mueven alternativamente; Bart va primero. En cada movimiento, el jugador elige dos números, los borra y los sustituye por su media. Si en algún momento los números pueden dividirse en dos conjuntos de $50$ números cada uno tal que las sumas en ambos conjuntos sean iguales, Bart gana.

¿Puede Alicia evitar que Bart gane?

[Fuente: basado en el problema de la competencia húngara].

Answer 1

Una pregunta equivalente es preguntar si Bob tiene una estrategia ganadora. Si Bob tiene una estrategia ganadora, entonces Alicia no puede impedir que Bob gane.

Lo definiré en términos de "burbujas de tamaño $n$ " y "popping"

A burbuja de tamaño $2n$ será un grupo de $2n$ números que pueden separarse en dos grupos, cada uno de ellos de tamaño $n$ de manera que su suma total sea la misma.

Soplar una burbuja será la acción de en su turno elegir dos números, ninguno de los cuales está en una burbuja.

Expandir una burbuja (o combinando burbujas) será la acción de combinar una burbuja con otra, realizada eligiendo dos números de burbujas diferentes.

Reventar una burbuja será la acción de cambiar la burbuja de tal manera que haya disminuido su tamaño, lo que se consigue eligiendo un número de una burbuja y otro que no lo sea o eligiendo dos números de la misma burbuja. Supondremos el peor de los casos y diremos que cuando una burbuja estalla, todos los números de la burbuja son diferentes. Observe que al hacerlo, se forma una nueva burbuja de tamaño 2 (es decir, los dos números seleccionados). También hay que tener en cuenta que esta acción de seleccionar dos de la misma burbuja no está garantizada para hacerla estallar realmente, pero supondremos que los números elegidos serán elegidos de tal manera que lo haga.

Denote $S_2 = $ el conjunto de burbujas de tamaño 2, $S_4 = $ el conjunto de burbujas de tamaño 4, $S_6 = $ burbujas de tamaño 6, $S_8 = $ ..., etc...

Denote $S = \cup S_{2i}$

Denote $|S_{2i}| =$ el número de burbujas de tamaño $2i$

Denote $|S| = 2 |S_2| + 4 |S_4| + 6 |S_6| + \cdots 100 |S_{100}|$

Bob gana si en algún momento $|S| = 100$

---

En cada uno de los turnos de Bob, siempre elige "soplar una burbuja". En otras palabras, elige un vértice que no es un elemento de un elemento de $S$ y lo hace igual a otro elemento que no es un elemento de $S$ . Como resultado, en cada turno, $|S_2|$ se incrementa en uno, provocando $|S|$ para aumentar en 2.

En cada uno de los turnos de Alicia, ella tiene las siguientes opciones:

1: Soplar una burbuja, aumentando $|S|$ por 2 (esto sólo ayuda a Bob a cumplir su objetivo)

2: Ampliar una burbuja, tomando elementos de diferentes burbujas. Esto no cambia $|S|$ . Si las opciones fueran de una burbuja de tamaño $2i$ y $2j$ la nueva burbuja formada es de tamaño $2(i+j)$ .

3: Reventar una burbuja, tomando dos elementos de la misma burbuja o uno de una burbuja y otro de fuera de la burbuja. Si la burbuja que se revienta es de tamaño $2n$ Esto reducirá el tamaño de $|S|$ por $(2n-2)$ (porque al reventar se forma una nueva burbuja de tamaño 2).

Obsérvese que como Bob no está expandiendo ninguna burbuja, por la cantidad que Alicia disminuye el tamaño de $|S|$ por ser positiva, debe haber pasado varios turnos expandiendo burbujas. Si la burbuja que se reventaba era de tamaño 4, tenía que pasar un turno combinando dos burbujas de tamaño 2 y luego reventarlas, causando una pérdida neta de $|S|$ de 2 en dos vueltas. Sin embargo, Bob habrá aumentado $|S|$ por 4 en ese mismo tiempo.

Si el tamaño de la burbuja que se ha explotado era $2n$ Habrá tomado $n-1$ gira para que una burbuja se expanda hasta tener ese tamaño. Alicia pasa el $n-1$ turnos de expansión de la burbuja y el $n$ El turno de reventar, proporcionando una pérdida neta a $|S|$ igual a $2n - 2$ . Durante esos $n$ sin embargo, Bob habrá aumentado el tamaño de $|S|$ por una cantidad igual a $2n$ .

Como resultado, el obstáculo que Alicia proporciona nunca es suficiente para obstaculizar completamente el progreso de Bob, y éste acabará ganando.

---

Detalles adicionales: Prueba de que la expansión de una burbuja crea una nueva burbuja y $|S|$ se mantiene igual:

Supongamos que tenemos dos burbujas, una de tamaño $2n$ y otra de tamaño $2m$ . Entonces los números de la primera burbuja pueden escribirse como $x^1_1, x^1_2, x^1_3,\cdots, x^1_n, y^1_1, y^1_2, y^1_3,\cdots,y^1_n$ con $\sum_{i=1}^{n} x^1_i = \sum_{i=1}^{n} y^1_i$ y la segunda burbuja puede escribirse como $x^2_1, x^2_2, x^2_3,\cdots, x^2_m, y^2_1, y^2_2, y^2_3,\cdots,y^2_m$ con $\sum_{i=1}^{m} x^2_i = \sum_{i=1}^{m} y^2_i$

Podemos suponer que los dos elementos elegidos son $x^1_1$ y $x^2_1$ (si no, sustituye las x por las y y/o viceversa y vuelve a indexar los números).

Entonces, $\frac{x^1_1 + x^2_1}{2} + \sum_{i=2}^{n} x^1_i + \frac{x^1_1 + x^2_1}{2} + \sum_{i=2}^{m} x^2_i = \sum_{i=1}^{n} x^1_i + \sum_{i=1}^{m} x^2_i = \sum_{i=1}^{n} y^1_i + \sum_{i=1}^{m} y^2_i$ que satisface la condición de ser una burbuja de tamaño $2(n+m)$

Así, hay una burbuja menos de tamaño $2n$ y una burbuja menos de tamaño $2m$ pero una burbuja más de tamaño $2(n+m)$ . Así que $|S| - 2n - 2m + 2(n+m) = |S|$

Tldr: Alicia no puede impedir que Bob gane. Gran parte del mérito es de un compañero de clase que dio la idea de usar burbujas para describir el escenario.