OFO 2017 Problema 11

[Vladislao]

Se tienen [math]100 monedas con pesos desconocidos, todos distintos. Demetrio tiene una máquina especial que recibe [math]50 monedas y las devuelve ordenadas según su peso de menor a mayor. Determinar cuál es la mínima cantidad de veces que Demetrio debe usar su máquina para poder ordenar todas las [math]100 monedas según su peso de menor a mayor.

[Vladislao]

Spoiler: mostrar

Veamos que $4$ preguntas no son suficientes. Supongamos que la permutación original es $a_1, a_2, \dots, a_{100}$. Notar que para cada $i, 1 \le i \le 99,$ tanto $a_i$ como $a_{i+1}$ deben aparecer en $1$ de nuestras "preguntas". De otro modo, las $2$ permutaciones
$$a_1, a_2, \dots, a_i, a_{i+1}, \dots, a_{100},\\
a_1, a_2, \dots, a_{i+1}, a_i, \dots, a_{100}$$ tendrían la misma respuesta.

Sean $k_1, k_2, \dots, k_{50}$ los números de nuestra primera pregunta (ya ordenados según la respuesta), y sean $k'_1, k'_2, \dots, k'_{50}$ los números de nuestra segunda pregunta. Es posible que estos conjuntos se intersecten. A partir de estos números, vamos a construir una permutación $b_1, b_2, \dots, b_{100}$ como sigue. Para $1 \le i \le 25$, sea
$$(b_{4i-3}, b_{4i-2}, b_{4i-1}, b_{4i}) = \begin{cases}
(k_{2i-1}, *, *, k_{2i}) & \text{si } k_{2i-1} = k'_{2i-1} \text{ y } k_{2i} = k'_{2i} \\
(k_{2i-1}, *, k_{2i}, k'_{2i}) & \text{si } k_{2i-1} = k'_{2i-1} \text{ y } k_{2i} \neq k'_{2i} \\
(k_{2i-1}, k'_{2i-1}, k_{2i}, k'_{2i}) & \text{si } k_{2i-1} \neq k'_{2i-1} \text{ y } k_{2i} \neq k'_{2i} \\
(k_{2i-1}, k'_{2i-1}, *, k_{2i}) & \text{si } k_{2i-1} \neq k'_{2i-1} \text{ y } k_{2i} = k'_{2i} \\
\end{cases}$$
donde los $*$ pueden ser cualquier número que no esté en ninguna de nuestras $2$ preguntas. (No es difícil ver que la cantidad de apariciones de $*$ es igual a la cantidad de números que no aparecen en ninguna de nuestras 2 preguntas.)

La permutación $b_1, b_2, \dots, b_{100}$ es consistente con las respuestas de nuestras $2$ preguntas. Además, ninguna de nuestras primeras $2$ preguntas incluye simultáneamente a $b_i$ y $b_{i+1},$ para $1 \le i \le 99$ y $i$ no múltiplo de $4$. Sea $\mathcal{P}$ el conjunto de los pares $(b_i, b_{i+1})$ que no aparecen en nuestras primeras 2 preguntas. Entonces cada par en $\mathcal{P}$ debe aparecer en una pregunta posterior.

Supongamos que todos los pares en $\mathcal{P}$ pueden ser incluidos en $2$ preguntas más. Todos los $100$ números aparecen entre los pares de $\mathcal{P}$, por lo que deben también aparecer en esas $2$ preguntas. Pero sólo podemos preguntar sobre $50$ números en cada pregunta, por lo que cada uno de esos $100$ números aparece en exactamente $1$ de las $2$ preguntas.

Considerando las cuaternas de la forma $(b_{4i-3}, b_{4i-2}, b_{4i-1}, b_{4i}), 1 \le i \le 25,$ si un número de una cuaterna aparece en alguna pregunta, entonces todos los números de la misma cuaterna deben aparecer en la pregunta, pues debemos incluir todos los pares de $\mathcal{P}$. Pero entonces la cantidad de números en cada pregunta tendrá que ser múltiplo de $4$, y $50$ no es múltiplo de $4$, absurdo. Luego, $4$ preguntas no son suficientes.

[jujumas]

Es increíble como buena parte de la dificultad de este problema está en no sonar chamuyero.

Solución:

Spoiler: mostrar

Para hablar de "Demetrio usando su máquina con las monedas", me refiero a "operaciones a las monedas".
Para no hablar de peso, a lo largo de esta solución hablo de "monedas mayores" o "monedas menores".
Cuando hablo de "peso bien definido" en la solución, me refiero a que ya se logró determinar cuales son todas las monedas menores y mayores a la misma. El objetivo es claramente que todas las [math]100 monedas consigan tener el peso bien definido.

Nota: En el problema, di por entendido que si se tiene una moneda [math]a y se le aplica la operación con otras [math]49, al volver las monedas ordenadas de menor a mayor peso, somos capaces de distinguir qué moneda era [math]a. Aún así, creo que esto es obvio, porque si las monedas fueran constantemente indistinguibles y por cada vez que aplicásemos una operación perdiésemos la identidad de una moneda, no creo que sea posible lograr lo pedido, sin importar la cantidad de operaciones.

Vamos a demostrar que el mínimo es de [math]5 operaciones:

Ejemplo: Tomamos dos conjuntos disjuntos de [math]50 monedas cada uno, llamados [math]A y [math]B. Aplicando la operación una vez en cada grupo, tenemos a [math]A y [math]B individualmente ordenados de menor a mayor.

Tomemos ahora las [math]25 monedas de mayor peso de cada conjunto, y apliquemos una operación con ellas. Sin pérdida de generalidad, la menor moneda de estas es del grupo [math]B. Luego, toda moneda mayor o igual a la menor moneda de [math]A que fue usada en esta operación, tiene su posición bien definida. Esto es porque fue comparada con todas las monedas de su propio conjunto, y al ser mayor que una moneda del conjunto opuesto, que fue comparada con todas las monedas de su conjunto, sabemos que monedas del conjunto opuesto son menores a ella, y como fue comparada en la tercer operación con toda moneda mayor, sabemos que monedas del conjunto opuesto son mayores a ella.

Siguiendo suponiendo que la menor moneda de estas es del grupo [math]B, tomamos ahora las [math]25 mayores monedas de este conjunto con las que acabamos de hacer la operación, solo que esta vez las comparamos con las [math]25 monedas menores del grupo [math]A. Notemos ahora que todas las monedas de este subconjunto de [math]25 de [math]B fueron comparadas con todas las monedas del conjunto [math]A, y todas las monedas del conjunto [math]B, de donde tienen su peso bien definido.

Nos queda una operación. En esta, compararemos las menores [math]25 monedas del conjunto [math]B con las [math]25 menores monedas del conjunto [math]A. Notemos que como las [math]25 menores monedas del conjunto [math]B, son menores que la moneda número [math]25 del conjunto [math]B ordenado de mayor a menor, son menores que las [math]25 monedas mayores del conjunto [math]A, y al ser comparadas con las [math]25 menores del conjunto [math]A, definimos también el peso de estas monedas.

Luego, los pesos de las [math]100 monedas se pueden definir en [math]5 operaciones.


Cota: Vamos a ver que con [math]4 operaciones no se puede. De esto será inmediato que tampoco se puede con menos.

Lema: Es imposible determinar el peso de una moneda sin usarla en al menos [math]2 operaciones.

Demostración: Es claro que sin usarla es imposible. Para ver que usándola una vez no se puede lograr determinarla, podemos simplemente tomar el peor caso, ya que el peso de esta moneda puede ser cualquiera.

Simplemente, hagamos al ordenar las monedas por peso de menor a mayor, esta moneda sea vecina de peso de alguna de las [math]50 monedas no elegidas para realizar la operación con ella. Esto quiere decir, que al aplicarle la operación a esta moneda, o va a quedar entre el peso de dos monedas elegidas, habiendo también otra moneda sin elegir entre estas dos, o será la menor de las [math]50 monedas elegidas, habiendo también otra moneda entre las [math]50 no elegida menor a estas [math]49, o será la mayor con el mismo problema.

En los [math]3 casos, no tenemos forma de saber si el peso de esta moneda es menor a mayor que el de la "otra moneda" mencionada en los tres casos usando los pesos de las [math]49 monedas involucradas en la operación, y como esta moneda nunca volverá a ser pesada, tenemos que su peso no es determinable.


Notemos que si tenemos [math]4 operaciones para hacer, sumando la cantidad de operaciones aplicada a cada moneda entre las [math]100 monedas, tendremos [math]200 de resultado. Sin embargo, sabemos que toda moneda estará involucrada en al menos dos operaciones por el Lema. Luego, cada moneda aparece en exactamente dos operaciones.

Llamemos ahora [math]A, [math]B, [math]C, [math]D a los conjuntos de [math]50 monedas cada uno a los que se le aplicará cada operación, en ese orden.

Es claro que si los conjuntos [math]A y [math]B son disjuntos, los conjuntos [math]A y [math]C tienen monedas en común y viceversa.

Si [math]A y [math]B no son disjuntos, tomemos [math]x tal que aparezca en [math]A y [math]B, y notemos que [math]x es comparado a lo sumo con [math]98 monedas distintas tras estas dos operaciones. Luego, no es comparada con una moneda. En el peor de los casos, esta moneda es vecina de peso con la moneda [math]x, y no tenemos forma de determinar si esta moneda es más liviana o más pesada que [math]x, ya que estas monedas no serán comparadas, y como las operaciones [math]A y [math]B eran las primeras, esto no se pudo hacer antes de estas operaciones, y como son monedas vecinas de peso, no podremos razonar cual es más pesada sin compararlas. Absurdo.

Si [math]A y [math]B son disjuntos, notemos que [math]C no puede ser ni disjunto con [math]A ni con [math]B. Supongamos que tiene [math]a monedas en común con [math]a, y [math]b monedas en común con [math]b. Luego, [math]a+b=50, al ser [math]A y [math]B disjuntos. Tomando ahora las monedas que no aparecen en [math]C, como cada una de ellas apareció en solo un conjunto, por Lema, estas [math]50 deben aparecer en [math]D. Luego, [math]D tiene [math]a monedas en común con [math]B, y [math]b monedas en común con [math]A. Además, [math]C y [math]D son disjuntos.

Tomemos ahora una moneda [math]x en [math]A y [math]C, y supongamos que tuvimos el peor caso, y la moneda vecina de peso de [math]x no está en [math]A. Notemos que tras aplicar la operación en [math]B, no tenemos suficiente información entre las monedas respecto a [math]x, ya que [math]A y [math]B son disjuntos. Luego, al elegir el conjunto [math]C, no podemos asegurarnos que la vecina de peso de [math]x quede en este conjunto, de donde no podemos asegurarnos lograr comparar el peso de estas dos monedas, por lo mismo en el caso mencionado arriba. Absurdo.


Con la cota y el ejemplo probado, tenemos que el mínimo de operaciones necesarias para lograr el objetivo es de [math]5.

[fleschler.ian]

Spoiler: mostrar

Sea [math]p_i la [math]i-esima pesada.
Empezamos dando una forma de conseguir cumplir el objetivo de Demetrio, en [math]5 pesadas.
1- En la primer pesada Demetrio pesa [math]50 monedas cualesquiera.
2- En la segunda pesada Demetrio pesa las [math]50 monedas restantes (que no agarro en la primera pesada).
3- Claramente entre las [math]25 más livianas que se usaron en [math]p_1 y las [math]25 más livianas que se usaron en la [math]p_2, se encuentran las [math]25 monedas más livianas. Luego al pesar las [math]25 más livianas de [math]p_1 con las [math]25 más livianas de [math]p_2, las [math]25 monedas más livianas son; en orden, las [math]25 monedas más livianas del total de las monedas.
4- Análogamente a [math]p_3, pesamos las [math]25 más pesadas de [math]p_1 y las [math]25 más pesadas de [math]p_2;determinando y ordenando las [math]25 monedas más pesadas del total de las monedas.
5- Una vez obtenidas y ordenadas las [math]25 monedas más livianas y las [math]25 monedas más pesadas; para terminar de ordenar la totalidad de las monedas, con una pesada ordenamos las monedas restantes.

Antes de demostrar que son necesarias [math]5 pesadas; veremos una condición necesaria y suficiente para que sea posible ordenar todas las monedas.
Sean [math]a_1, [math]a_2, ... [math]a_{100} las monedas ordenadas según su peso. Decimos que dos monedas [math]m y [math]n son consecutivas, si al asignarles el orden [math]m=a_{i} y [math]n=a_{j} se satisface [math]\left | i-j \right |=1
Veamos que una serie de pesadas funciona, si y solo sí para todo [math]i; [math]a_{i} y [math]a_{i+1} fueron comparadas en alguna pesada.
La ida es inmediata, si [math]a_{i} y [math]a_{i+1} fueron comparadas para todo [math]i. Entonces sabremos que [math]a_{1}<a_{2}<...[math]<a_{99}<a_{100}.
Para ver la vuelta basta ver la única comparación que distingue a [math]a_{i} de [math]a_{i+1} es [math]a_{i}<a_{i+1}. Como los pesos de estas son consecutivos:
[math]a_{i}<a_{j} si y solo sí [math]a_{i+1}<a_{j} (para todo [math]j entre [math]1 y [math]100 distinto de [math]i, [math]i+1). [Esto implica que todas las otras comparaciones distintas de [math]a_{i} con [math]a_{i+1} no las ordenan]

Empecemos viendo que [math]4 pesadas son necesarias.
Decimos que una pesada descubre un par de monedas consecutivas [math](a_{i}, a_{i+1}), si en esa pesada [math]a_{i} y [math]a_{i+1} aparecieron.
Claramente una pesada descubre a lo sumo [math]49 pares de monedas consecutivas.
Si en la primer pesada agarráramos las monedas [math]a_{2i-1} con [math]1 \leq i \leq 50, entonces esta pesada no descubre ningún par de monedas consecutivas.
Como hay que descubrir en total [math]99 pares de monedas consecutivas, entonces se necesitan al menos [math]\left \lceil \frac{99}{49} \right \rceil=3 pesadas más.

Supongamos que es posible descubrir el orden de las monedas en [math]4 pesadas.
Si las monedas de [math]p_1 y [math]p_2 fuesen disjuntas, basta considerar [math]p_1 como las monedas [math]a_{2i-1} con [math]1 \leq i \leq 50. Que implicaría que en [math]p_1 y en [math]p_2 no se descubren pares de monedas consecutivas. Entonces en este caso serían necesarias al menos [math]5 pesadas. (Por el mismo razonamiento con el que vimos que siempre se necesitan [math]4 pesadas).
Entonces las monedas de [math]p_1 y las monedas de [math]p_2 no pueden ser disjuntas.
Sea [math]S_1 las monedas que aparecen tanto en [math]p_1 y en [math]p_2. Sea [math]S_2 las monedas que aparecen en [math]p_1 y no en [math]p_2. Sea [math]S_3 las monedas que aparecen en [math]p_2 y no en [math]p_1. Y sean [math]S_4 las monedas que no aparecieron ni en [math]p_1 ni en [math]p_2.
Llamaremos [math]a a la cantidad de monedas de [math]S_1. Sabemos que [math]\left | S_1 \right |=\left | S_4 \right |=a y [math]\left | S_2 \right |=\left | S_3 \right |=50-a y que [math]0<a<50.
Supongamos que la [math]i-esima moneda de [math]S_2 es consecutiva a la [math]i-esima moneda de [math]S_3.
Entonces sería necesario comparar la [math]i-esima moneda de [math]S_2 con la [math]i-esima moneda de [math]S_3 o bien en [math]p_3 o bien en [math]p_4.
Eso implica que los conjuntos de monedas [math]S_2 y [math]S_3 aparecen totalmente entre [math]p_3 y [math]p_4.
Es claro que también toda moneda de [math]S_4 tiene que aparecer o bien en [math]p_3 o bien en [math]p_4 ya que si no participara en ninguna pesada; no tendríamos información alguna sobre ella.

Hay dos posibilidades:
1- [math]S_4 no aparece entero en [math]p_3.

Spoiler: mostrar

Este caso lo subdividimos en dos subcasos:
A- No se repiten monedas entre [math]p_3 y [math]p_4
Llamemos [math]A a una moneda que apareció en [math]p_3, que no pertenece a [math]S_4 y que no apareció en [math]p_4. Existe ya que cualquier moneda que no pertenece a [math]S_4 y apareció en [math]p_3 no pudo aparecer en [math]p_4 por la hipótesis de este caso.
Entonces necesitaríamos una quinta pesada, si una moneda de [math]S_4 que apareció en [math]p_4 y no en [math]p_3 fuese consecutiva de [math]A.
B- Se repiten monedas entre [math]p_3 y [math]p_4
Como entre [math]p_3 y [math]p_4 pesamos [math]100 monedas, y hay dos repetidas; entonces existe alguna moneda que no apareció ni en [math]p_3 ni en [math]p_4 llamemosla [math]A. Como bien dijimos antes [math]S_4 aparece completamente entre [math]p_3 y [math]p_4; por lo tanto [math]A no pertenece a [math]S_4.
Entonces necesitaríamos una quinta pesada, si una moneda de [math]S_4 que apareció en [math]p_4 y no en [math]p_3 fuese consecutiva de [math]A.

2-[math]S_4 aparece entero en [math]p_3.

Spoiler: mostrar

Este caso lo dividimos en dos subcasos:
A- Ninguna moneda de [math]S_1 aparece en [math]p_3.
Entonces si la [math]i-esima moneda de [math]S_4 fuese consecutiva de la [math]i-esima moneda de [math]S_1 para todo [math]1 \leq i \leq a.
Necesitaríamos que [math]S_1 y [math]S_4 aparezcan en [math]p_4.
Que implicaría que entre [math]p_3 y [math]p_4 pesamos al menos [math]\left | S_1 \right |+\left | S_2 \right |+\left | S_3 \right |+2\left | S_4 \right |=a+50-a+50-a+2a=100+a que es estrictamente mayor que [math]100 que es la cantidad de monedas que podemos pesar en dos pesadas.
Por lo tanto este caso no puede suceder.
B- Al menos una moneda de [math]S_1 aparece en [math]p_3
Decimos que un par de monedas [math](A,B) es bueno si [math]A es la [math]i-esima moneda de [math]S_2 y [math]B es la [math]i-esima moneda de [math]S_3 para algún [math]i.
Decimos que un par bueno es simpático si ninguna de sus monedas apareció en [math]p_3.
Supongamos que en [math]p_3 aparecieron [math]k pares buenos. Entre [math]p_3 y [math]p_4 deberían aparecer [math]50-a pares buenos.
Sea [math]j la cantidad de monedas de [math]S_2 o [math]S_3 que aparecieron en [math]p_3 sueltas (es decir sin armar su par bueno).
Entonces la cantidad de pares simpáticos es [math]50-a-k-j.
Sabemos que aparecieron [math]50-a-2k-j monedas de [math]S_1 en [math]p_3. Entonces hay [math]a-(50-a-2k-j)=2a+2k+j-50 monedas de [math]S_1 que no aparecieron en [math]p_3.

Notemos que entre ambas cantidades (pares simpáticos y monedas de [math]S_1 que no aparecieron en [math]p_3) hay [math](50-a-k-j)+(2a+2k+j-50)=a+k que es mayor o igual a [math]a.
Vamos a hacer que sea necesario pesar a todo el conjunto [math]S_4 nuevamente en [math]p_4.
Dada una moneda de [math]S_4 podemos conseguir que sea consecutiva a una moneda de las de un par simpático.
Y también podemos conseguir que dada otra moneda de [math]S_4 sea consecutiva a una moneda de [math]S_1 que no apareció en [math]p_3.
Como entre esas cantidades hay al menos [math]a monedas, podemos conseguir que todas las monedas de [math]S_4 sean consecutivas a alguna que no fue pesada en [math]p_3.
Entonces [math]S_4 tuvo que aparecer totalmente en [math]p_4. Lo que implica que entre ambas pesadas, [math]p_3 y [math]p_4 tienen que estar (al menos):
[math]1 moneda de [math]S_1, [math]S_2, [math]S_3 y dos veces [math]S_4.
Por lo tanto entre ambas pesadas se pesaron al menos [math]1+\left | S_2 \right |+\left | S_3 \right |+2\left | S_4 \right |=1+50-a+50-a+2a=101 que es estrictamente mayor que [math]100 que es la cantidad de monedas que podemos pesar en dos pesadas.
Por lo tanto este caso no puede suceder.

Habiendo considerado todos los casos posibles y viendo que para cada uno existe una configuración para la cual no es posible determinar el orden de las monedas con certeza:
Queda entonces demostrado que [math]5 pesadas es la cantidad necesaria y suficiente para ordenar a todas las monedas.[/quote]