Las fiestas de la OMA son legendarias, de modo que lleva un gran trabajo mantenerlas a la altura de su historia. Con este objetivo, a la hora de celebrar Halloween, los exolímpicos consiguieron un tablero gigante con más columnas que filas, colocaron calabazas en algunas de sus casillas, y desafiaron a los olímpicos a pintar de naranja algunas columnas del tablero (al menos una) de modo que en cada fila la cantidad de calabazas en casillas naranjas sea par. Demostrar que los olímpicos siempre pueden lograr su objetivo.
Digamos que el tablero es de $n\times m$, con $1\leq n<m$. A cada forma de pintar columnas le asignamos una nueva columna que tiene una calabaza en la fila $i$ si y sólo si hay una cantidad impar de calabazas en casillas naranjas en la fila $i$ del tablero, entonces el problema es equivalente a demostrar que hay una forma de pintar las columnas de modo que la nueva columna quede vacía.
Los olímpicos tienen $2^m-1$ formas de pintar algunas columnas del tablero (hay $2$ opciones por cada columna, pintarla o no pintarla, lo que nos da un total de $2^m$, y tenemos que descontar la opción de no pintar ninguna columna), mientras que la nueva columna puede tener las calabazas distribuidas de $2^n$ formas distintas (hay dos opciones por cada casilla, tener o no tener una calabaza). Como $m>n$ y son enteros, resulta $m\geq n+1$, de modo que$$2^m-1\geq 2^{n+1}-1=2^n+2^n-1>2^n,$$pues $2^n-1>0$ al ser $n\geq 1$. Entonces por Palomar tenemos que hay al menos dos formas distintas de pintar columnas a las que se les asigna la misma nueva columna. Sea $A$ el conjunto de columnas que están en la primera forma de pintar pero no en la segunda, sea $B$ el conjunto de columnas que están en la segunda forma de pintar pero no en la primera, y sea $C$ el conjunto de columnas que están tanto en la primera como en la segunda forma de pintar. Si en la fila $i$ de la nueva columna (que es la misma para ambas formas de pintar) hay una calabaza, entonces la cantidad de calabazas en las casillas de la fila $i$ de $A$ tiene distinta paridad que la cantidad de calabazas en las casillas de la fila $i$ de $C$, y la cantidad de calabazas en las casillas de la fila $i$ de $B$ tiene distinta paridad que la cantidad de calabazas en las casillas de la fila $i$ de $C$, con lo que la cantidad de calabazas en las casillas de la fila $i$ de $A$ tiene la misma paridad que la cantidad de calabazas en las casillas de la fila $i$ de $B$. Análogamente vemos que si no hay una calabaza en la fila $i$ de la nueva columna entonces la cantidad de calabazas en las casillas de la fila $i$ de $A$ tiene la misma paridad que la cantidad de calabazas en las casillas de la fila $i$ de $B$. Luego, pintando únicamente las columnas de $A$ y de $B$ los olímpicos obtienen una nueva columna sin calabazas.
Concluimos que los olímpicos siempre pueden lograr su objetivo.
Un tablero de $a\times b$ tiene $a$ filas y $b$ columnas, siempre. Recibí muchas soluciones que usaban la notación al revés, y no es para nada recomendable hacer eso.
Sea $n$ la cantidad de filas y $m$ la cantidad de columnas, numeramos las filas de $1$ a $n$ y las columnas de $1$ a $m$. Ahora representaremos el tablero como un multiconjunto (de tamaño $m$) de conjuntos (de números del $1$ al $n$) $U$, donde el conjunto $U_j$ (representando la columna $j$) tendrá el número $i$ si y solo si hay una calabaza en la casilla $(i,j)$ (fila $i$, columna $j$).
Denotemos $\bigoplus$ como el "o" exclusivo de dos conjuntos, o el xor (dado dos conjuntos $A$ y $B$, $A \bigoplus B = (A \cup B) - (A \cap B)$). Ahora, dado un multiconjunto de conjuntos $A$ de tamaño $k$ denotemos $x(A) = A_1 \bigoplus A_2 \bigoplus A_3 \bigoplus ... \bigoplus A_k$. Ahora si agarramos un subconjunto de columnas, es decir un subconjunto $A$ de $U$ y pintamos todas las columnas que elegimos en $A$, $x(A)$ es equivalente a los índices de las filas que nos quedan con una cantidad impar de calabazas en casillas pintadas, ya que la fila $i$ aparece en $x(A)$ si y solo si aparece una cantidad impar de veces en los conjuntos de $A$, es decir si pintamos una cantidad impar de casillas con calabazas de la fila $i$.
Ahora notemos que el problema es equivalente a encontar un subconjunto $A\neq\emptyset$ de $U$ tal que $x(A)=\emptyset$. Ya que debemos elegir un subconjunto no vacío de columnas tales que no haya ninguna con una cantidad impar de casillas con calabazas pintadas.
Dado un multiconjunto $U$ de tamaño $n$ de conjuntos de números del $1$ al $n$ veamos que o bien existe un subconjunto $A \neq \emptyset$ de $U$ tal que $x(A)=\emptyset$ o bien se puede formar cualquier conjunto no vacío de números del $1$ al $n$ la forma $x(A)$ con $A \subseteq U$, es decir para todo conjunto $B \neq \emptyset$ de números del $1$ al $n$ existe un $A \subseteq U$ tal que $x(A)=B$. Para demostrar lo segundo asumamos que no existe ningún subconjunto que dé xor vacío (lo primero), ahora asumamos que existen dos subconjuntos distintos $A$ y $B$ de $U$ tales que $x(A)=x(B)$, llamemos $C=A-(A\cap B)$ y $D=B-(A\cap B)$, como $x(A)=x(B) \Rightarrow x(A)\bigoplus x(A\cap B) = x(B)\bigoplus x(A\cap B) \Rightarrow x(C)=x(D)$ (para el último paso debemos notar que $A\bigoplus A = \emptyset$ y $A\bigoplus \emptyset = A$, es decir se cancelan los elementos que son iguales, por lo tanto se cancelan en $x(A)$ todos los elementos de $x(A\cap B)$ y se cancelan en $x(B)$ todos los elementos de $x(A\cap B)$, quedandonos $x(C)=x(D)$ ). Notemos que tanto $C$ como $D$ son disjuntos ya que son los conjuntos $A$ y $B$ sin los elementos que compartían, y la unión de $C$ y $D$ no es vacía ya que $A$ y $B$ son distintos, por lo que existe un elemento que no pertenece a ambos por lo que existe un elemento que pertenece a $C$ o $D$. Llamemos $E$ a $C\cup D$, notemos que $E$ también es un subconjunto no vacío de $U$ ya que es la unión de dos subconjuntos disjuntos de $U$ (y es no vacío por lo que ya vimos) por lo tanto $x(E) = x(C\cup D) = x(C)\bigoplus x(D) = x(C)\bigoplus x(C) = \emptyset$, por lo que llegamos a que existe un subconjunto no vacío de $U$ tal que el xor es vacío, y como estamos en el caso que no existe ningún subconjunto con xor vacío llegamos a un absurdo, que vino de suponer que existían dos subconjuntos distintos $A$ y $B$ de $U$ tales que $x(A)=x(B)$. Por lo tanto cualquier subconjunto no vacío $A$ de $U$ va a dar un $x(A)$ distinto y como hay $2^n-1$ distintos $A$ ($A\subseteq U \wedge A\neq \emptyset$) posibles y $2^n-1$ distintos $B$ ($B\subseteq \{ 1,2,3 ... n\} \wedge B\neq \emptyset$) posibles entonces se puede realizar una biyección entre todos los posibles $x(A)$ y todos los posibles $B$, es decir, los $x(A)$ van a cubrir todos los posibles resultados (conjuntos de números del $1$ al $n$) que podían llegar a dar excepto el vacío, que era lo que queríamos demostrar.
Con esto demostrado agarramos cualquier tablero y nos fijamos las primeras $n+1$ columnas (siempre hay al menos n+1 columnas ya que $m>n$), y vamos a demostrar que siempre podemos encontar un subconjunto $A\neq\emptyset$ de $U$ tal que $x(A)=\emptyset$. Asumamos que este subconjunto $A$ no existe, acá nos pueden pasar dos cosas: $U_{n+1}=\emptyset$ con esto $A=\{U_{n+1}\}$ y ya llegamos a un absurdo. En el otro caso nos fijamos las primeras $n$ columnas, llamémoslo $P$ a este conjnuto, por lo que demostramos antreriormente existe un subconjunto $S$ de $P$ tal que $x(S)=U_{n+1}$ (ya que $P$ es un multiconjunto de tamaño $n$ de conjuntos de números del $1$ al $n$ y no existe ningún subconjunto $A$ no vacío de $P$ tal que $x(A)=\emptyset$ por lo que $x(S)$ puede tomar cualquier valor no vacío que querramos, en particular $U_{n+1}$), con esto tenemos un subconjunto de $U$ no vacío, $A=S\cup \{U_{n+1}\}$ tal que $x(A) = x(S\cup \{U_{n+1}\}) = x(S)\bigoplus x(\{U_{n+1}\}) = x(S) \bigoplus U_{n+1} = U_{n+1} \bigoplus U_{n+1} = \emptyset$ por lo que llegamos de nuevo a un absurdo. En ambos casos el absurdo vino de suponer que no existía dicho $A$ por lo que siempre existe un subconjunto no vacío $A$ de $U$ tal que $x(A)=\emptyset$, es decir siempre existe un subconjunto de columnas con al menos una columna tales que al pintarlas nos queda cada fila con una cantidad par de calabazas en casillas pintadas, por lo que los olímpicos siempre tienen una estrategia que es pintar ese subconjunto.
Edu Carranza escribió: ↑Vie 13 Oct, 2023 10:10 pm
... ya que la fila $i$ aparece en $x(A)$ si y solo si aparece una cantidad impar de veces en los conjuntos de $A$ ...
Esto pasa por las propiedades del xor, ya que como explico más tarde $\{i\} \bigoplus \{i\} = \emptyset$ y $\{i\} \bigoplus \emptyset = \{i\}$, es decir que si cualquier elemento (fila) $i$ aparece dos veces se cancela, y si aparece una vez más vuelve a aparecer en el resultado y así sucesivamente (esto también se puede demostrar por inducción con el caso base de 0 apariciones que es igual a $\emptyset$ y el paso inductivo es alguna de las ecuaciones anteriores, dependiendo la paridad), es decir que si aparece o no depende de la paridad, si es impar aparece en $x(A)$ y si es par no aparece porque se canceló. (cuando me refiero a que $\{i\}$ "aparece" me refiero a que está de la forma $\bigoplus \{i\}$ exactamente una vez en la expresión mencionada)
Edu Carranza escribió: ↑Mié 18 Oct, 2023 12:10 am
Denotemos $\bigoplus$ como el "o" exclusivo de dos conjuntos
Ya me sentía emocionado, creía que era suma directa de teoría de grupos (no miento, incluso después que me contaras que usaste xor cuando, denuevo después de ese regional, usé vectores módulo dos jkasjkajska)
$n$ es la cantidad de filas del tablero. A cada columna la expresaremos como un vector de $n$ componentes donde cada componente vive en $\mathbb{Z} / \mathbb{Z}_2$, osea, cada componente vale o $0$ o $1$ y $1+1=0$; donde un $1$ en la i-ésima componente representa que hay una calabaza en la i-ésima fila sobre esa columna. Notemos que hay $2^n$ posibles vectores de este tipo (pueden pensarlo que cada componente puede ser $0$ o $1$, por lo que cada uno tiene dos posibilidades, como son $n$ componentes, tenés que en total hay $2$ multiplicado $n$ veces posibilidades, lo que es $2^n$).
De aquí podemos pensar que al pintar una columna de naranja es sumar dos de estos vectores y, el objetivo, es que de resultado nos dé el vector $0$ (el vector tal que todos sus componentes son iguales a 0) eventualmente, donde sumar dos vectores, por las dudas, nos devuelve otro vector donde la i-ésima componente de este nuevo vector es igual a la suma de las i-ésimas componentes de los vectores sumandos.
Notemos que si tenemos dos vectores iguales entonces su suma da el vector 0, pues, los componentes que valgan $1$ se sumarán con ellos mismos y $1+1=0$ y los componentes que valgan $0$ se sumarán con ellos mismos y $0+0=0$. Cabe notar también que el vector 0 es el elemento neutro pues, sea $v$ el vector 0, y $a$ y $b$ otros dos vectores tales que:
$a+v=b$
entonces sea $x$ la i-ésima componente en a, y $y$ la i-ésima componente en $b$:
$x+0=y\rightarrow x=y$
por lo que todas las componentes de $a$ son iguales a sus respectivas en $b$, de lo que se deduce $a=b$
Ahora, demostraré que con al menos $n+1$ columnas ya los olímpicos cumplen su objetivo, esto es, consiguen ciertas columnas cuyas sumas den el vector $0$:
Si hay al menos $n+1$ columnas entonces hay en total hay, al menos, $2^{n+1}-1$ sumas distintas (que nos interesan), porque podemos pensar que es una suma de todo y vamos vector por vector preguntando "lo dejo o lo saco de la suma", cada vector tiene dos posibilidades, o que se quede o se vaya de la suma (esto sería, que sume o que no sume), por lo que hay el doble de posibilidades por cada columna nueva, donde sí suma y donde no, por lo que en total habrían, hasta la columna $n+1$, $2^{n+1}$ sumas distintas, pero no contamos la posibilidad donde no haya ningún vector sumando, queremos que al menos haya uno, por lo que hay $2^{n+1}-1$ sumas distintas que nos interesan . recordemos que cada suma tiene $2^n$ posibles resultados porque hay $2^n$ posibles vectores. Notemos entonces que hay, necesariamente por palomar, dos sumas con al menos un vector distinto que sumen lo mismo (porque hay $2^{n+1}-1$ posibles sumas y $2^n$ posibles vectores). Pero si dos sumas suman lo mismo, entonces, si las sumamos nos dará el vector $0$, y notemos que si tienen una columna $c$ en común ambas sumas, $c+c=v$ por lo que podríamos descartar el vector de la columna $c$ que tienen en común, que sería lo mismo que hacer $c+c$, por lo que podríamos eliminar de ambas sumas todos los vectores en común, y dejar solo los que no comparten, estos vectores deberán sumar $v$, por lo que si pintamos las columnas correspondientes a esos vectores quedarán todas las filas con cantidades pares de calabazas en casillas naranjas y al menos hay una columna pintada de naranja.
Digamos que el tablero es de $n\times m$ y consideremos a las columnas como vectores en $(\mathbb{Z}/2\mathbb{Z})^n$ sobre $\mathbb{Z}/2\mathbb{Z}$. Como este último es un espacio vectorial de dimensión $n$ y $m>n$ por dato, tenemos que los vectores son linealmente dependientes, con lo que existe una combinación lineal no trivial de los mismos con coeficientes en $\mathbb{Z}/2\mathbb{Z}$ que suma $0$. Los olímpicos ganan pintando los vectores que aparecen con coeficiente $1$ en esa combinación lineal.
Lo que vamos a hacer es definir una operación $a \oplus b$ entre dos columnas $a$ y $b$, cuyo resultado es una columna posible (es decir, una columna con una combinación de casillas con calabaza y sin calabaza que no necesariamente existe en el tablero). Es análoga a la operación XOR entre cadenas binarias, o disyunción binaria exclusia.
Definiremos esta operación con este algoritmo:
$a \oplus b = c$, sí y solo sí por cada fila $f$:
(1) Si hay una calabaza en $(a; f)$ y hay una calabaza en $(b; f)$, entonces no hay una calabaza en $(c; f)$
(2) Si no hay una calabaza en $(a; f)$ y no hay una calabaza en $(b; f)$, entonces no hay una calabaza en $(c; f)$
(3) Si ninguna de esas dos condiciones se cumple, entonces hay exactamente una calabaza en ${(a; f), (b; f)}$. En este caso, habrá una calabaza en $(c; f)$.
Podemos construir una tabla de esta operación, para cada fila:
Para toda columna $a$, $a \oplus a = 0$, porque siempre sucederá el caso (1) del algoritmo que describimos arriba, entonces no habrá ninguna calabaza en $c$, por lo que $c = 0$
$a \oplus b = c \Rightarrow (a \oplus b) \oplus b = c \oplus b \Rightarrow a \oplus (b \oplus b) = c \oplus b \Rightarrow a = c \oplus b$
También, obviamente, $a \oplus 0 = a$, porque el caso (3) sucederá cuando hay una calabaza en $a$, y el caso (2) sucederá cuando no haya.
Lema: Un conjunto de columnas cuya disyunción exclusiva sea 0, si las pintamos, cumpliría con las condiciones del problema.
Lo interesante que tiene esta operación es que tiene una relación muy linda con la paridad. Si imaginamos que hacemos la operación $a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = c$ con $n$ columnas, entonces para cada fila $f$, podemos imaginarnos calculando los resultados parciales $a_1 \oplus a_2, a_1 \oplus a_2 \oplus a_3, ...$, y por cada fila, cada vez que nos cruzemos con una calabaza en esa fila y en uno de los $a_i$, si ya hay una calabaza en el resultado parcial anterior, no va a haber una en el siguiente, y si no hay, va a haber una en el siguiente.
Si se fijan, cuando la cantidad de unos es impar, el resultado es $1$, y cuando la cantidad de unos es par, el resultado es $0$.
Entonces, lo que hace esta operación es decirte la cantidad de calabazas en cada fila mod 2. Si es impar, hay una calabaza en esa fila en el resultado, y si es par, no hay.
Entonces, lo que nos pide el problema es un conjunto de columnas $a_1, a_2, a_3, ..., a_n$, tal que $a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0$. El resultado es $= 0$ sí y solo si la cantidad de calabazas en cada fila que estén en algunas de estas columnas es par, es decir, que si pintamos las columnas en el conjunto, cumpliremos con las condiciones del problema.
Lema: Existen dos subconjuntos distintos de columnas del tablero tales que su disyunción exclusiva es igual:
Cada columna tiene $F$ filas. Cada una o bien tiene una calabaza, o no la tiene. Entonces hay $2^F$ columnas posibles.
Ahora, imaginemos todos los subconjuntos del conjunto de columnas del tablero. Como hay $C$ columnas, hay $2^C$ subconjuntos. No podemos pintar sólamente el conjunto vacío, entonces tenemos $2^{C - 1}$ opciones para pintar.
Imaginemos que, para cada uno de estos subconjuntos, hacemos la operación XOR de todas las columnas en el subconjunto. Tendremos $2^{C - 1}$ resultados. Como $C > F > 1$, entonces $2^{C - 1} > 2^F$, entonces hay más resultados del XOR que columnas posibles. Entonces, entre estos resultados, por el principio del palomar, hay por lo una columna que se repite. Es decir, que hay dos subconjuntos distintos de columnas del tablero, que si para cada subconjunto hacemos la operación XOR, nos dan el mismo resultado.
Construcción del conjunto de columnas que podemos pintar:
Llamemos $r$ al resultado, ${a_1, a_2, ..., a_n}$ a las columnas que solamente están en el primer conjunto de columnas, ${c_1, c_2, ..., c_n}$ a las columnas que solamente están en el segundo conjunto de columnas, y ${b_1, b_2, ..., b_n}$ a las columnas que tienen en común
$a_1 \oplus a_2 \oplus ... \oplus a_n \oplus b_1 \oplus b_2 \oplus ... \oplus b_n = r = c_1 \oplus c_2 \oplus ... \oplus c_n \oplus b_1 \oplus b_2 \oplus ... \oplus b_n $
$a_1 \oplus a_2 \oplus ... \oplus a_n \oplus (b_1 \oplus b_2 \oplus ... \oplus b_n) \oplus (b_1 \oplus b_2 \oplus ... \oplus b_n) = c_1 \oplus c_2 \oplus ... \oplus c_n \oplus (b_1 \oplus b_2 \oplus ... \oplus b_n) \oplus (b_1 \oplus b_2 \oplus ... \oplus b_n)$
$a_1 \oplus a_2 \oplus ... \oplus a_n \oplus 0 = c_1 \oplus c_2 \oplus ... \oplus c_n \oplus 0$
$a_1 \oplus a_2 \oplus ... \oplus a_n = c_1 \oplus c_2 \oplus ... \oplus c_n$
$a_1 \oplus a_2 \oplus ... \oplus a_n \oplus (c_1 \oplus c_2 \oplus ... \oplus c_n) = (c_1 \oplus c_2 \oplus ... \oplus c_n) \oplus (c_1 \oplus c_2 \oplus ... \oplus c_n)$
$a_1 \oplus a_2 \oplus ... \oplus a_n \oplus c_1 \oplus c_2 \oplus ... \oplus c_n = 0$
Como no hay columnas en común entre ${a_1, a_2, ..., a_n}$ y ${c_1, c_2, ..., c_n}$, podemos pintar estas columnas. El resultado de su disyunción binaria exclusiva es igual a cero, por lo que en cada fila, la cantidad de calabazas pintadas es par. Entonces, esto cumple las condiciones del problema.
Resumido:
Buscamos dos subconjuntos de columnas del tablero cuya disyunción binaria exclusiva sea igual. Por el principio del palomar, siempre existirá uno, ya que hay más subconjuntos de columnas del tablero que columnas posibles. Pintamos todas las columnas que están en exactamente uno de estos dos subconjuntos. Por lo que escribimos arriba, su disyunción binaria exclusiva es una columna sin calabazas, por lo que la cantidad de calabazas pintadas en cada fila es par.
