Provincial 2023 N3 P2

[Felibauk]

Mili tiene $100$ tarjetas en blanco y escribe en cada una de ellas uno o varios números enteros positivos. Cada número puede figurar en una, varias o en ninguna tarjeta. Puede haber tarjetas repetidas. Felipe tiene que adivinar los números de las $100$ tarjetas, y para ello, en cada paso, debe señalar dos tarjetas y de inmediato Mili le informará cuáles son todos los números que están en alguna de esas dos tarjetas, y todos los números que figuran simultáneamente en las dos tarjetas. Por ejemplo, si las dos tarjetas señaladas por Felipe tienen respectivamente $\{1,2,5,7\}$ y $\{2,3,4,5\}$, Mili responderá $\{1,2,3,4,5,7\}$ y $\{2,5\}$.
Determinar el menor número de pasos con los que Felipe se asegura su objetivo, no importa qué números escriba inicialmente Mili en las $100$ tarjetas.

[fran :)]

Solución, si me acuerdo bien @Felibauk mostró una solución parecida a esta en la discusión de problemas de esa provincial. Ojo que puede ser que me esté equivocando en algo.

Spoiler: mostrar

Primero un poquito de notación y terminología.

Spoiler: mostrar

$A \cup B$ es todos los elementos que están en A o en B. $A \cap B$ es todos los elementos que están en A y B. $A \setminus B$ es todos los elementos que están en A pero no en B. Cuando Feli hace un paso con dos tarjetas $A$ y $B$, Mili le dice $A \cup B$ y $A \cap B$. Felipe puede realizar estas operaciones entre conjuntos y aplicar varias propiedades que tienen para sacar los valores de las tarjetas.

Un grafo es bipartito si se puede colorear con 2 colores tal que no haya dos vértices del mismo color conectados por un arista. Es equivalente a decir que no hay ciclos impares (esto es un teorema de teoría de grafos).

Un grafo es conexo si hay un camino entre dos vértices para cada par de vértices (si no tiene subgrafos aislados)

Un grafo conexo es un árbol si no tiene ciclos. Todos los árboles son bipartitos, porque la única manera de que se te complica colorear es si hay un cíclo, y los árboles son acíclicos.

Con 100 pasos se puede:

Spoiler: mostrar

Para esto voy a demostrar dos cosas:

Si Feli conoce una tarjeta $A$, entonces haciendo la pregunta $A$ con $B$ puede saber $B$.
La pregunta le brinda $A \cup B$ y $A \cap B$, y sabiendo $A$ Feli puede calcular $((A \cup B) \setminus A) \cup (A \cap B) = B$.
(si no están seguros de como llegue a eso, pueden pensarlo con diagramas de Venn)

Para tres tarjetas $A$, $B$, $C$, Feli puede hacer las tres preguntas posibles y saber las tres tarjetas.
Esto es porque $A = (A \cap B) \cup (A \cap C) \cup (((A \cup B) \cup (A \cup C)) \setminus (B \cup C))$. Una vez que sabe A, con lo que ya demostramos arriba puede sacar las otras dos (no es necesario hacer ninguna otra pregunta porque las preguntas ya están hechas).

Entonces, si Felipe hace tres preguntas con tres tarjetas cualquiera, y despues hace una pregunta con cada una de las 97 tarjetas que quedan, puede saber los contenidos de todas las tarjetas.

Con 99 no se puede.

Spoiler: mostrar

Esto lo voy a demostrar con inducción fuerte. Mi hipótesis es que con $n$ tarjetas y $n - 1$ preguntas entre esas tarjetas, Felipe no puede asegurar su objetivo.

Si el grafo que representa sus pasos es bipartito, Feli no puede asegurar su objetivo:

Spoiler: mostrar

Felipe no puede asegurar su objetivo si y solo sí hay por lo menos dos maneras diferentes en las que Mili puede escribir los números que hacen que Mili le diga exactamente los mismos conjuntos números a Feli en cada pregunta (Es decir, que Feli, con las preguntas que hace, no puede diferenciar entre estas dos posiblidades).

Vamos a ver que alcanza con que Mili solamente use dos conjuntos de números distintos. Las tarjetas que vamos a llamar "blancas" van a tener el conjunto $\{1\}$, y las tarjetas que vamos a llamar "negras" van a tener el conjunto $\{2\}$. Feli tiene que averiguar los colores de cada tarjeta. En cada pregunta, si las tarjetas tienen el mismo color, Mili le dice $\{1\}, \{1\}$ o $\{2\}, \{2\}$, y si tienen colores distintos le dice $\{1, 2\}$ y $\{\}$.

Podemos representar las tarjetas y las preguntas de Feli como un grafo, donde los vértices son tarjetas y los aristas son las preguntas que hace Feli.

Si el grafo es bipartito, entonces lo podemos colorear con dos colores tal que cada arista conecte dos vértices de color opuesto. Entonces, Mili siempre le va a decir $\{1, 2\}$ y $\{\}$. Si Mili, en un universo paralelo, hubiese invertido los colores de las tarjetas, (blanco -> negro y negro -> blanco), esta propiedad se conservaría y las respuestas de Mili serían las mismas, pero cada tarjeta tendría otro conjunto de números. Entonces, si el grafo es bipartito, Feli no puede diferenciar estos dos universos paralelos y no puede asegurar su objetivo.

Nuestro caso base es $n = 1$, que es trivial. Con $0$ preguntas, Feli no consigue información y pierde.
Para $n > 1$:

Si el grafo es disconexo, entonces consiste en $k$ subgrafos aislados. Todos los subgrafos tienen que ser no-bipartitos, porque si hay algún subgrafo bipartito, entonces Felipe no puede diferenciar dos posibilidades dentro de ese subgrafo. Cada subgrafo es aislado y tiene una cantidad de vértices menor a $n$ por lo que podemos aplicar la hipótesis inductiva fuerte en cada uno para darnos cuenta que cada uno de los subgrafos necesita tener una cantidad de aristas igual o mayor a su cantidad de vértices para ser no-bipartito. Si sumamos todo, entonces, la cantidad de aristas en el grafo completo tiene que ser igual o mayor a $n$ para ser no-bipartito, por lo tanto, con $n - 1$ sí o sí es bipartito.

Si el grafo es conexo, entonces como tiene $n - 1$ aristas y $n$ vértices, es un árbol. Esto es por un teorema de teoría de grafos que dice que un grafo conexo es un arbol si y solo si tiene un arista menos que vértices.

Spoiler: mostrar

Demostración de un lado de la doble implicación de este teorema (no es necesario demostrarlo pero la pongo acá para el interesado)

Sabemos que tiene $n - 1$ aristas, es conexo, y asumimos que no es un árbol. Entonces por definición tiene un ciclo. Consideramos el grafo igual al anterior pero le sacamos un arista del ciclo. Como es un ciclo, el nuevo grafo sigue siendo conexo, pero ahora tiene $n$ vértices y $n - 2$ aristas. Es imposible tener un grafo conexo con estas condiciones entonces lo que asumimos es absurdo, por lo tanto, debe ser un árbol.

Como es un árbol, entonces es bipartito. Como es bipartito, entonces Felipe no puede asegurar su objetivo.

99 = 100 - 1, por lo tanto con 100 tarjetas y 99 preguntas, Felipe no puede asegurar su objetivo.

Detalle:

Spoiler: mostrar

Hasta ahora estuvimos asumiendo que Feli no cambia sus decisiones en el medio del juego, es decir, que Feli no usa la información que obtiene en el medio del juego. Pero en realidad para el ejemplo que estuvimos usando no importa, porque los dos universos paralelos son simétricos, entonces cualquier estrategia que use Feli va a resultar en las mismas acciones en cada universo paralelo. (Asumiendo que su estrategia es determinista, y que no le importan los valores de los números, solamente su rol en los conjuntos que le dice Mili)

Entonces con 100 puede pero con 99 no, por lo tanto el menor número de pasos es 100.