Selectivo de Ibero 2018 - Problema 2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Matías V5 »

En un pizarrón hay escritos $n > 3$ números enteros positivos distintos, todos menores que $(n-1)!$. Para cada pareja $a > b$ de estos números, Julián escribe en su cuaderno el cociente entero de $a$ dividido $b$ (por ejemplo, si $a=100$ y $b=7$, Julián escribe $14$, pues $100 = 14 \times 7 + 2$). Demostrar que en el cuaderno de Julián quedarán escritos por lo menos dos números iguales.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Re: Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Matías V5 »

Spoiler: mostrar
Sean $a_1 < a_2 < \ldots < a_n$ los números del pizarrón. Notemos que el cociente de dividir $a$ por $b$ es $\left \lfloor \frac{a}{b} \right \rfloor$. Si todos los números del cuaderno de Julián fueran distintos, en particular pasaría que $\left \lfloor \frac{a_2}{a_1} \right \rfloor, \left \lfloor \frac{a_3}{a_2} \right \rfloor, \ldots, \left \lfloor \frac{a_n}{a_{n-1}} \right \rfloor$ son $n-1$ enteros positivos distintos, y por lo tanto su producto sería mayor o igual que $(n-1)!$. Sin embargo, $\left \lfloor \frac{a_2}{a_1} \right \rfloor \cdot \left \lfloor \frac{a_3}{a_2} \right \rfloor \cdot \ldots \cdot \left \lfloor \frac{a_n}{a_{n-1}} \right \rfloor \leq \frac{a_2}{a_1} \cdot \frac{a_3}{a_2} \cdot \ldots \cdot \frac{a_n}{a_{n-1}} = \frac{a_n}{a_1} \leq a_n$, es decir que $a_n$ sería mayor o igual que $(n-1)!$, contradiciendo el enunciado. Entonces, en el cuaderno de Julián hay al menos dos números iguales, como queríamos ver. $\blacksquare$
4  
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
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 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 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Gianni De Rico »

Ligeramente distinta
Spoiler: mostrar
Sean $g_1<g_2<\ldots <g_n$ los números escritos. Sea $k_i$ el cociente entero de $g_{i+1}$ dividido $g_i$, luego $g_2\geqslant k_1g_1$, $g_3\geqslant k_2g_2\geqslant k_2k_1g_1$ y así siguiendo $g_n\geqslant k_{n-1}k_{n-2}\ldots k_2k_1g_1=g_1\prod \limits_{i=1}^{n-1}k_i$. Supongamos que los $k_i$ son todos distintos, luego, $\prod \limits_{i=1}^{n-1}k_i\geqslant \prod \limits_{i=1}^{n-1}i=(n-1)!$, entonces $g_n\geqslant (n-1)!$, pero $(n-1)!>g_n$, por lo tanto $(n-1)!>(n-1)!$. Absurdo!!
El absurdo provino de suponer que todos los números escritos en el cuaderno son distintos, luego, al menos dos de ellos son iguales.
♪♫ do re mi función lineal ♪♫
Teorema del Palomar
Mensajes: 5
Registrado: Mié 06 Sep, 2017 8:40 pm
Nivel: Exolímpico

Re: Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Teorema del Palomar »

Spoiler: mostrar
Sean 1,2,...,n,...,(n-1)! los números escritos en el pizarron. Para todo a>b con a,b>1 sea [a/b] la parte entera de la fracción a/b. Tomemos a, tal que a=b+1. Remplazamos en [a/b] y vemos que [(b+1)/b]= 1. Análogamente (b+1)/b= 1 + 1/b. Vemos que 1/b es necesariamente irracional, ya que b>1. Como n>3 entonces existen al menos dos pares de la forma a=b+1.Por tanto, hay al menos dos números iguales.
¿P=NP?
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 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 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Gianni De Rico »

Teorema del Palomar escribió: Dom 18 Nov, 2018 10:31 am
Spoiler: mostrar
Sean 1,2,...,n,...,(n-1)! los números escritos en el pizarron. Para todo a>b con a,b>1 sea [a/b] la parte entera de la fracción a/b. Tomemos a, tal que a=b+1. Remplazamos en [a/b] y vemos que [(b+1)/b]= 1. Análogamente (b+1)/b= 1 + 1/b. Vemos que 1/b es necesariamente irracional, ya que b>1. Como n>3 entonces existen al menos dos pares de la forma a=b+1.Por tanto, hay al menos dos números iguales.
Un par de cosas
Spoiler: mostrar
No hay $(n-1)!$ números escritos en el pizarrón, como mucho serían los números naturales hasta $(n-1)!-1$ ya que son todos menores que $(n-1)!$, además en caso de ser así el problema es trivial, porque podés ver a mano que $\left \lfloor \frac{4}{2}\right \rfloor =\left \lfloor \frac{5}{2}\right \rfloor$, (siempre están pues $n\geqslant 4$) por lo que hay dos números iguales.
¿A qué es análogo el hecho de que $\frac{b+1}{b}=1+\frac{1}{b}$? Porque más bien parece que estás demostrando que $\left \lfloor \frac{b+1}{b}\right \rfloor =1$.
Si $b$ es natural (supongo que es así porque si no tu solución no tiene mucho sentido), entonces $\frac{1}{b}$ es racional.
No es cierto que como $n>3$ entonces va a haber al menos dos pares de la forma $a=b+1$, tomando $n=5$ tenemos un contraejemplo con el conjunto de cinco números $\{1,7,12,18,23\}$, que cumple con las condiciones del enunciado pues son todos menores que $(5-1)!=4!=24$.
♪♫ do re mi función lineal ♪♫
Responder