Maratón de Problemas

Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 52
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario - Santa Fe

Re: Maratón de Problemas

Mensaje sin leer por Fran2001 »

Solución 366:
Spoiler: mostrar
Sea $d(n)$ la cantidad de divisores de $n$, es fácil ver que $d(n)$ es impar si y solo si $n$ es un cuadrado perfecto.
Notemos ahora que $f(n)=d(1)+d(2)+\dots +d(n)+\sqrt n$.
Esto puede verse por inducción: para $n=1$ es cierto, y si se cumple para $n=k$, entonces para $n=k+1$ estamos sumando $1$ a los términos de la forma $\lfloor\frac{k+1}a\rfloor$, donde $a|k+1$. Es decir, estamos sumando $d(k+1)$, como queríamos.
Ahora procedamos nuevamente por inducción, notando que $f(1)$ es par. Supongamos que $f(k)$ también lo es. Si $k+1$ es un cuadrado perfecto, entonces $f(k+1)=f(k)+d(k+1)+\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt k\rfloor$.
Notemos que $d(k+1)$ es impar, y que $\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt k\rfloor=1$. Por lo tanto $f(k+1)$ es par.
Si $k+1$ no es un cuadrado perfecto, entonces $d(k+1)$ es par, y $\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt k\rfloor=0$. Por lo tanto $f(k+1)$ sigue siendo par, y estamos.
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4

Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 52
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario - Santa Fe

Re: Maratón de Problemas

Mensaje sin leer por Fran2001 »

Problema 367:
Hay $2n$ personas sentadas alrededor de una mesa redonda, jugando al psicólogo.
Como no se pueden decir las reglas de este juego, vamos a inventar otro. Supongamos que estas personas tienen en total $m$ precintos.
Puden pasarse los precintos siempre y cuando sigan las siguientes reglas:
a) Cada persona solo puede pasarle precintos a sus vecinos.
b) Cada vez que alguien pasa un precinto, debe tirar otro.
Supongamos que Emi es una de las personas que está jugando.
Como está re manija, quiere terminar el juego teniendo sí o sí un precinto.
Hallar el menor $m$ tal que, sin importar cómo estén distribuidos los precintos al comienzo, hay una estrategia que nos asegura que Emi reciba al menos uno.
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4

Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 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
Mensajes: 282
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 11
Nivel: Ñandú

Re: Maratón de Problemas

Mensaje sin leer por Monazo »

Llamamos a un par de enteros positivos $a$ y $b$ "generadores de cuadrado", si $ab+1$ es un cuadrado perfecto. Determinar para cada $n$ entero positivo si es posible dividir el conjunto $\{1,2,\dots,2n \}$ en $n$ parejas de "generadores de cuadrados".
El Diego es del Lobo! Y del Lobo no se va!

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años
Mensajes: 310
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 8
Nivel: Ñandú

Re: Maratón de Problemas

Mensaje sin leer por BrunZo »

Spoiler: mostrar

Yo digo que esto es posible para todo entero positivo $n$ par, pero para $n$ impar es imposible. Veamos por qué:

La clave que vamos a usar para $n$ par es que $(k-1)(k+1)+1 = k^2$. De este modo, consideremos las parejas:
$$(4k+1, 4k+3),\quad (4k+2, 4(k+1))$$
para algún $k$ entre $0$ y $n/2-1$ (recordemos que $n$ es par). Entonces, notemos que cada pareja es "generadora de cuadrados" y además logramos cubrir todos los números del $1$ hasta el $2n$. Con esto, terminamos un ejemplo para $n$ par.

Ahora, vemos que $n$ impar es imposible:

Tomemos un número $a$ que tenga resto $2$ módulo $4$. Yo digo que si $(a, b)$ es generadora de cuadrados, entonces $b$ es múltiplo de cuatro. Para ver esto, notemos que si es generadora de cuadrados, entonces
$$ab+1=k^2\iff ab=k^2-1=(k-1)(k+1)$$
Ahora bien, como $a$ es par, sabemos que el lado derecho es par, pero $k-1$ y $k+1$ tienen la misma paridad, así que tienen que ser ambos pares. Más aún, sabemos que uno de ellos tiene que ser múltiplo de cuatro, de modo que el producto es múltiplo de $8$. Pero como $a$ no es múltiplo de $4$, para llegar a que el lado derecho sea múltiplo de $8$, necesitamos que $b$ sea múltiplo de $4$, como queríamos demostrar.

Ahora bien, notemos que si $n$ es impar, entonces $2n$ es $2$ módulo $4$, así que en la lista $\{1,2,3,...,2n\}$, hay $\frac{n-1}{2}$ múltiplos de $4$ y $\frac{n+1}{2}$ números que son $2$ módulo $4$. Pero sabemos que cada uno de estos últimos tiene que emparejarse con uno de los primeros, pero $\frac{n+1}{2}>\frac{n-1}{2}$, así que el emparejamiento es imposible.

Problema 368:

En la Ciudad de La Plata, el Intendente está pensando en remodelar su ciudad construyendo algunas plazas. Como bien es sabido, La Plata es una ciudad cuadrada y el Intendente quiere que todas las plazas también sean cuadradas (los lados de cada cuadrado son calles transitables, los bordes de la ciudad también son transitables); y además, al Intendente le gustaría que las plazas no se superpongan y que cubran toda el área de la ciudad (es decir, que no queden huecos sin cubrir). El Arquitecto Mayor, luego de escuchar el proyecto, le dice que para que el trazado sea eficiente, se necesita que se cumpla la siguiente condición: "no puede haber ningún recorrido con forma de cuadrado (a través de calles transitables) en cuyo interior haya más de una plaza; a menos que el recorrido bordee toda la Ciudad". Al Turko, que está muy atento a todas las noticias de su amada Ciudad, le preocupa muchísimo saber cuántas plazas van a quedar después de la remodelación. Determinar todas las posibles cantidades de plazas en las que se puede partir la Ciudad para que se cumplan los requisitos.

Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 52
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario - Santa Fe

Re: Maratón de Problemas

Mensaje sin leer por Fran2001 »

Solución 367:
Spoiler: mostrar
Fede me hizo notar que este problema ya está en el Foro (es una versión general del Problema 5 de la COFFEE Iván Sadofschi).
Vamos a comenzar numerando a las personas.
Le asignamos a Emi el $0$, y luego a cada persona le asignamos la distancia en personas a la que se encuentra de Emi (por ejemplo, las $2$ personas sentadas al lado de Emi tienen el $1$, y la persona diametralmente opuesta tiene el $n$).
Ahora, para cada precinto que tenga la persona $i$, definimos su peso como $w_i=\frac 1{2^i}$. Así, el peso de cada precinto de Emi es $1$, el peso de cada precinto de sus vecinos es $\frac 12$ y el peso de cada precinto de la persona diametralmente opuesta es $\frac 1{2^n}$.
Ahora basta notar que si una persona $i$ tiene precintos, y pasa alguno a la $i+1$, entonces la suma de los pesos decrece: el peso del precinto que movimos disminuyó, y el peso del precinto que tiramos desapareció.
Además, si la persona $i$ pasa un precinto a la persona $i-1$, la suma de los pesos no varía: teníamos $2$ precintos con peso $\frac 1{2^i}$, y ahora tenemos uno solo con peso $\frac 1{2^{i-1}}$.
Es decir que la suma de los pesos es una monovariante: nunca puede crecer.
Si Emi termina con un precinto, la suma de los pesos en ese momento va a ser al menos $1$. Por lo tanto, si inicialmente el peso total es menor que $1$, no vamos a poder hacerle llegar un precinto a Emi.
Ahora, si tenemos menos de $2^n$ precintos, e inicialmente tiene todos la persona $n$, el peso total inicial va a ser menos de $1$.
Es decir que necesitamos al menos $2^n$ precintos.
Es fácil ver que con $2^n$ precintos siempre vamos a poder hacerle llegar uno a Emi, mirando el lado con mayor peso de la mesa y jugando solo por ese lado.
Por lo tanto $m=2^n$.
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4

Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 52
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario - Santa Fe

Re: Maratón de Problemas

Mensaje sin leer por Fran2001 »

Problema 368 bis:
Brian tiene $3$ cuentas bancarias, cada una con una cantidad entera de pesos. Tiene permitido transferir plata de una cuenta a la otra, pero de forma que la cantidad de plata de la cuenta que recibe se duplique. Puede realizar esta operación cuantas veces quiera.
Demostrar que Brian siempre puede lograr que toda su plata esté en $2$ cuentas, dejando la otra vacía.
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4

Responder