Selectivo de Ibero 2018 - Problema 2

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 897
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Matías V5 » Jue 02 Ago, 2018 9:16 pm

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.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 897
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Re: Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Matías V5 » Jue 02 Ago, 2018 9:34 pm

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$
3  
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 829
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Gianni De Rico » Jue 02 Ago, 2018 11:40 pm

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.
[math]

Teorema del Palomar
Mensajes: 3
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 » 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.
¿P=NP?

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 829
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de Ibero 2018 - Problema 2

Mensaje sin leer por Gianni De Rico » Dom 18 Nov, 2018 1:22 pm

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$.
[math]

Responder