Primer pretorneo 2021 Nivel mayor: Problema 4

Problemas que aparecen en el Archivo de Enunciados.
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021
Mensajes: 116
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 7
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Fedex »

Hay $101$ monedas ubicadas alrededor de una circunferencia y cada moneda pesa $10\text{ g}$ u $11\text{ g}$. Demostrar que existe una moneda tal que el peso total de las $k$ monedas a su izquierda es igual al peso total de las $k$ monedas a su derecha para:
$a)$ $k=50$.
$b)$ $k=49$.
This homie really did 1 at P6 and dipped.

Santi's AI
Mensajes: 3
Registrado: Vie 14 May, 2021 3:44 pm
Nivel: 2

Re: Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Santi's AI »

Respondiendo únicamente al caso K=50:
Spoiler: mostrar
Sabemos que en la circunferencia se dará una de las siguientes dos opciones, ya que hay 101 monedas en total:
- Una cantidad par de monedas que pesan 10g e impar de monedas que pesan 11g
- El caso inverso

Entonces, sin prestar atención al peso de cada una, llamemos "X" a cada moneda con un determinado peso e "Y" a cada moneda con el otro peso.
Sabemos que habrá una cantidad impar de X, entonces el procedimiento consiste en numerar en orden consecutivo todas las monedas que aparecen una cantidad impar de veces (supongamos que tenemos una cantidad "Z" de X, entonces numeramos todas las X desde 1 hasta Z).
Luego, teniendo numeradas esas monedas, tomaremos como moneda de referencia la que esté ubicada en la posición
(Z+1)/2 (disculpen que no sepa escribir en LaTeX aún).
Tomando esa moneda como referencia, entonces tanto a la izquierda como a la derecha de ésta tendremos una cantidad
(Z+1)/2 - 1 de monedas X, y
50 - [(Z+1)/2 - 1] de monedas Y.

Entonces, sin importar el peso de cada X e Y, podremos proceder de esta forma y siempre se logrará el objetivo para K=50.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021
Mensajes: 1665
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 11
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Gianni De Rico »

Santi's AI escribió:
Jue 03 Jun, 2021 1:20 pm
Respondiendo únicamente al caso K=50:
Spoiler: mostrar
Sabemos que en la circunferencia se dará una de las siguientes dos opciones, ya que hay 101 monedas en total:
- Una cantidad par de monedas que pesan 10g e impar de monedas que pesan 11g
- El caso inverso

Entonces, sin prestar atención al peso de cada una, llamemos "X" a cada moneda con un determinado peso e "Y" a cada moneda con el otro peso.
Sabemos que habrá una cantidad impar de X, entonces el procedimiento consiste en numerar en orden consecutivo todas las monedas que aparecen una cantidad impar de veces (supongamos que tenemos una cantidad "Z" de X, entonces numeramos todas las X desde 1 hasta Z).
Luego, teniendo numeradas esas monedas, tomaremos como moneda de referencia la que esté ubicada en la posición
(Z+1)/2 (disculpen que no sepa escribir en LaTeX aún).
Tomando esa moneda como referencia, entonces tanto a la izquierda como a la derecha de ésta tendremos una cantidad
(Z+1)/2 - 1 de monedas X, y
50 - [(Z+1)/2 - 1] de monedas Y.

Entonces, sin importar el peso de cada X e Y, podremos proceder de esta forma y siempre se logrará el objetivo para K=50.
Ojo, la idea está bien, pero le falta algo para poder terminarla
Spoiler: mostrar
Suponete que empiezo a numerar las monedas del $1$ al $101$ desde la que está "más arriba". Si las monedas desde la $1$ a la $25$ son $X$, las monedas desde la $26$ a la $75$ son $Y$, y las monedas desde la $76$ a la $101$ son $X$. Básicamente lo que tengo es este dibujo:
Dibujo.png
Entonces hay $51$ monedas $X$, de modo que la moneda que vos estás eligiendo es la $76$, que es la que tendría el número $26$ cuando arrancás a contar las $X$ desde la que tiene el $1$. Esa moneda tiene $50$ monedas $X$ a la derecha y $50$ monedas $Y$ a la izquierda, así que tienen pesos distintos.

¿Cómo arreglamos esto? Bueno, en este caso es muy sencillo, simplemente elegimos la moneda que tiene el $1$ (es decir, arrancamos a contar desde la $76$), esa va a tener $25$ monedas $X$ y $25$ monedas $Y$ a cada lado, así que ya estaríamos.

Lo que está faltando para terminar de cerrar tu solución es justamente esto, ver que siempre podemos elegir bien la moneda desde la que arrancamos a contar, porque si arrancamos contando desde otro lado nos puede dar cualquier cosa, como ya vimos en el ejemplo de antes.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Santi's AI
Mensajes: 3
Registrado: Vie 14 May, 2021 3:44 pm
Nivel: 2

Re: Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Santi's AI »

Sí quizás me olvidé de aclararlo pero siempre a la hora de contar se tienen en cuenta solo las monedas de las cuáles aparece una cantidad impar de veces, las que aparecen una cantidad par se dejan de lado, ya que al numerar en orden consecutivo las que son impares entonces la que esté justo en el medio de esas que son impares va cumplir las características que pide ahí la consigna

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021
Mensajes: 1665
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 11
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Gianni De Rico »

Creo que no me entendiste, voy a tratar de explicarlo con otras palabras.

Suponete que tenemos una moneda de tipo $X$, a la que llamamos $A$ (esa es la que en el dibujo anterior le puse el $1$). Recorriendo en sentido horario tenemos otras $24$ monedas de tipo $X$, después $50$ monedas de tipo $Y$, y por último $26$ monedas de tipo $X$.
Si vos arrancás a numerar las monedas de tipo $X$ desde la $A$ (o sea, esta es la número $1$), entonces como hay $51$ monedas $X$, la que vas a elegir es la número $26$, que es la primera que aparece después de toda la tira de monedas $Y$. El problema es que esta moneda tiene $50$ monedas $X$ a la derecha y $50$ monedas $Y$ a la izquierda, así que la moneda no cumple lo pedido.

Lo que tenés que demostrar es que hay una moneda desde la que podés empezar a contar y que tu estrategia funcione.

Creo que parte del problema es que no hay una noción intuitiva de la "moneda del medio" en general cuando estás en una circunferencia. Si están todas juntas (como en el ejemplo que di yo), entonces sí, pero si estuvieran más separadas no hay una forma clara de decidir cuál sería "la del medio".
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Santi's AI
Mensajes: 3
Registrado: Vie 14 May, 2021 3:44 pm
Nivel: 2

Re: Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Santi's AI »

Claro ya entendí, bueno eso en realidad me olvidé de aclararlo pero cuando se tiene una cantidad impar de monedas, entonces como a la derecha y a la izquierda hay 50 monedas la moneda de referencia va a tener todo el resto de monedas de la circunferencia a la izquierda y a la derecha, sin ninguna que sobre. Entonces sabiendo esto vos vas a poder elegir de entre las que aparecen una cantidad impar de veces 2X + 1, una que tenga X impares a su izquierda y X impares a su derecha. Ahí se la considera la del medio

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021
Mensajes: 1665
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 11
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Gianni De Rico »

Santi's AI escribió:
Vie 04 Jun, 2021 5:26 pm
vos vas a poder elegir de entre las que aparecen una cantidad impar de veces 2X + 1, una que tenga X impares a su izquierda y X impares a su derecha.
Acá estás haciendo razonamiento circular, lo que te pide el problema es justamente que demuestres que existe una moneda que tiene $X$ monedas de un valor (por ejemplo, $10$) entre las $50$ a su izquierda y $X$ monedas de $10$ entre las $50$ a su derecha. En cualquier ejemplo que hagas vas a encontrar una que cumple eso justamente porque el problema es cierto, pero estás tratando de demostrar el problema suponiendo que es algo válido. Es como si te pidieran demostrar que un número $n$ es par y vos dijeras algo del estilo
Si $n$ fuera par, entonces $n=2k$ con $k$ entero, así que $\frac{n}{2}=k$, que es entero. Entonces $n$ es par.
Esto no anda porque ya sabías de antes que $n$ era par, así que toda la cuenta que hiciste para demostrarlo fue innecesaria.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Sergiohuang2004

OFO - Mención-OFO 2021
Mensajes: 27
Registrado: Dom 23 Jun, 2019 7:45 pm
Medallas: 1
Nivel: 2

Re: Primer pretorneo 2021 Nivel mayor: Problema 4

Mensaje sin leer por Sergiohuang2004 »

Entonces alguien lo pudo hacer? :)

Responder