Pretorneo de las Ciudades - Nivel Juvenil - Problema 2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 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 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Pretorneo de las Ciudades - Nivel Juvenil - Problema 2

Mensaje sin leer por Turko Arias »

Un mago coloca formando una fila las $52$ cartas de un mazo, boca abajo, pero él sabe qué lugar ocupa cada carta. En cada etapa, una persona de la audiencia elige un entero positivo $k$, comprendido entre $1$ y el número de cartas que haya en ese momento, y a continuación el mago quita de la fila la carta de la posición $k$ desde la derecha o desde la izquierda, a elección del mago. Antes de empezar, el mago anuncia que la última carta que quedará en la fila luego de $51$ etapas será el tres de corazones.
Determinar para qué ubicaciones iniciales del tres de corazones puede el mago garantizar el éxito de su truco.
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 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 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Pretorneo de las Ciudades - Nivel Juvenil - Problema 2

Mensaje sin leer por Turko Arias »

Spoiler: mostrar
Como queremos que el mago pueda asegurarlo con certeza, en particular queremos que para cualquier posible combinación de números del público el pueda lograrlo, por lo tanto podríamos hacer de cuenta que el público también puede ver las cartas boca arriba y que juega lo mejor posible.
Digamos que el público gana si el mago tiene que sacar el tres de corazones en algún momento, y el mago gana en caso contrario.
Sea $l(n)$ la posición en la que se encuentra el tres de corazones contando de izquierda a derecha en el turno $n$, y $r(n)$ la posición en la que se encuentra contando de derecha a izquierda en el turno $n$. El primer turno es el turno $0$. Notamos que si en algún turno $n$ sucede que $l(n)=r(n)$, tomando $k=r(n)$ el mago si o si va a tener que sacar el tres de corazones.
Supongamos que $l(0) \neq 1$ y $r(0) \neq 1$, vamos a jugar con el público siguiendo la siguiente estrategia, en el turno $i$, vamos a elegir $k=min(l(i),r(i))$. Sin pérdida de generalidad, supongamos $l(i) \leq r(i)$, si $l(i)=r(i)$ por lo visto antes, ya ganamos. Si $l(i) < r(i)$, tomando $k=l(i)$ notamos que el mago o bien saca el tres de corazones, o bien saca una carta a la derecha del tres de corazones. Como su objetivo es que no se vaya esa gran carta, lo que hace es sacar una carta de la derecha del tres de corazones, por lo que ahora tenemos que $l(i+1)=l(i)$ y $r(i+1)=r(i)-1$, es decir, la posición contando desde la derecha se redujo en $1$. Como las posiciones son enteras y siempre estoy achicando al mayor, eventualmente va a suceder que $l(j)=r(j)$, ademas, como $l(0)>1$ y $r(0)>1$ y la suma $l(0)+r(0)=52+1$ tenemos que $l(0)<51$ y que $r(0)<51$, por lo que la igualdad se va a producir en menos de $51$ turnos y por ende, va a haber más de una carta, por lo que el tres de corazones no va a ser la última. Luego, en este caso el público siempre puede ganar.

Supongamos ahora que $r(0)=1$ y el caso $l(0)=1$ es análogo. Esto quiere decir que el tres de corazones está en la punta derecha. En cada turno, cuando el público elija el número $k$ vamos a proceder de la siguiente manera (porque ahora que el mago gana, nos pasamos a su bando):
-Si $k$ es la cantidad de cartas que quedan, sacamos la carta de la esquina izquierda
-Si $k$ es cualquier otro número, sacamos la carta que se encuentra en la posición $k$ contando desde la izquierda

Es claro que esta estrategia nos asegura que si hay más cartas en la mesa, podemos siempre sacar alguna que no sea el tres de corazones.

Luego, las únicas posiciones que le permiten al mago asegurar su objetivo son la esquina izquierda y la esquina derecha $\blacksquare$
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Responder