OFO 2020 Problema 6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Chino2000

OFO - Medalla de Plata FOFO 7 años - Medalla Especial FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 40
Registrado: Mar 09 Dic, 2014 10:18 pm
Medallas: 7
Nivel: 1

OFO 2020 Problema 6

Mensaje sin leer por Chino2000 » Mié 22 Ene, 2020 12:01 am

Sea $N$ un entero positivo. Bat debe escribir una progresión aritmética de $180$ números reales en la cual exactamente $N$ de sus términos sean números enteros. Determinar el mínimo valor de $N$ para el cual la tarea de Bat es imposible.

Aclaración: Una progresión aritmética es una lista de números en la cual cada término se obtiene sumándole al anterior una cantidad fija $d$, que se llama la diferencia de la progresión. Por ejemplo, $3,~7,~11,~15,~19,~23$ y $\frac{1}{3},~\frac{1}{2},~\frac{2}{3},~\frac{5}{6}$ son progresiones aritméticas.
1  

Avatar de Usuario
Chino2000

OFO - Medalla de Plata FOFO 7 años - Medalla Especial FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 40
Registrado: Mar 09 Dic, 2014 10:18 pm
Medallas: 7
Nivel: 1

Re: OFO 2020 Problema 6

Mensaje sin leer por Chino2000 » Sab 01 Feb, 2020 12:26 am

Aquí vamos a publicar la solución oficial.

Avatar de Usuario
Sandy

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 90
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 2
Nivel: 3

Re: OFO 2020 Problema 6

Mensaje sin leer por Sandy » Sab 01 Feb, 2020 1:00 am

Chino2000 escribió:
Mié 22 Ene, 2020 12:01 am
Sea $N$ un entero positivo. Bat debe escribir una progresión aritmética de $180$ números reales en la cual exactamente $N$ de sus términos sean números enteros. Determinar el mínimo valor de $N$ para el cual la tarea de Bat es imposible.

Aclaración: Una progresión aritmética es una lista de números en la cual cada término se obtiene sumándole al anterior una cantidad fija $d$, que se llama la diferencia de la progresión. Por ejemplo, $3,~7,~11,~15,~19,~23$ y $\frac{1}{3},~\frac{1}{2},~\frac{2}{3},~\frac{5}{6}$ son progresiones aritméticas.
Spoiler: mostrar
Sean $a_1, a_2, ..., a_m$ los términos y $d$ la diferencia.

Es claro que para $N=1$ puede hacerlo. Por ejemplo con $a_1=0$ y $d$ cualquier irracional, o una sucesión con $a_1=0$ y $d<\frac{1}{179}$.

Supongamos que $a_t$ es el primer entero y $a_{t+q}=a_t+qd$ el segundo, tenemos que $a_{t+q}-a_t=qd$ debe ser entero, por lo tanto $a_{t+cq}=a_t+dcq$ será entero para cualquier entero $c$ (hasta que $t+cq>180$ obviamente), podemos entonces decir que $t\leq q$, ya que, si no, $a_{t-q}$ sería entero, pero dijimos que $a_t$ era el primer entero.

Supongamos que un número de la forma $a_{t+r}=a_t+rd$ es entero, donde $r$ no es de la forma $cq$ y sea $b$ el menor número tal que $bq>r$, tenemos que $a_{t+bq}-a_{t+r}=dbq-rd=(bq-r)d<q$ es entero, pero entonces $a_{t+bq-r}=a_t+d(bq-r)$ debe ser entero, lo cual es un absurdo ya que $t+bq-r<t+q$, pero dijimos que el segundo entero era $a_{t+q}$. Por lo tanto todos los enteros de la sucesión son de la forma $a_{t+cq}$ con $c$ entero.

Ahora, veremos que, de existir tal sucesión, debe existir una en la que los $N$ enteros que aparezcan sean los enteros del $1$ al $N$.

Sabemos que $qd$ es la diferencia entre dos enteros seguidos de la sucesión. Si a toda la sucesión le sumamos una constante entera, los números enteros seguirán siendo enteros y los no enteros seguirán siendo no enteros. Por lo tanto, restémosle a todos los números $a_t$ (es decir, hagamos que el primer entero sea $0$), $qd$ dividirá a todos los enteros de la sucesión, ya que son de la forma $a_{t+cq}=a_t+dcq$. Entonces podemos dividir a toda la sucesión por $qd$ y nos queda una sucesión con los números del $0$ al $N-1$. En esta sucesión le sumamos $1$ a todos los números y tenemos la sucesión que queríamos encontrar.
Notemos en esta sucesión que la diferencia debe ser el opuesto de un entero, ya que la diferencia entre dos enteros de la sucesión es una cantidad entera de veces la diferencia.

Veremos entonces ahora para qué números existe una sucesión de $180$ términos que pase por los números del $1$ al $N$ y por ningún otro entero.

Primero veremos una manera de conseguir dicha sucesión para los números $N$ con $181\leq \lfloor \frac{179}{N-1} \rfloor \times (N+1)$

Dicha desigualdad la cumplen todos los números del $2$ al $18$ inclusive:
Spoiler: mostrar
$\lfloor \frac{179}{2-1} \rfloor \times (2+1)=537>181$
$\lfloor \frac{179}{3-1} \rfloor \times (3+1)=356>181$
$\lfloor \frac{179}{4-1} \rfloor \times (4+1)=295>81$
$\lfloor \frac{179}{5-1} \rfloor \times (5+1)=264>181$
$\lfloor \frac{179}{6-1} \rfloor \times (6+1)=245>181$
$\lfloor \frac{179}{7-1} \rfloor \times (7+1)=232>181$
$\lfloor \frac{179}{8-1} \rfloor \times (8+1)=225>181$
$\lfloor \frac{179}{9-1} \rfloor \times (9+1)=220>181$
$\lfloor \frac{179}{10-1} \rfloor \times (10+1)=209>181$
$\lfloor \frac{179}{11-1} \rfloor \times (11+1)=204>181$
$\lfloor \frac{179}{12-1} \rfloor \times (12+1)=208>181$
$\lfloor \frac{179}{13-1} \rfloor \times (13+1)=196>181$
$\lfloor \frac{179}{14-1} \rfloor \times (14+1)=195>181$
$\lfloor \frac{179}{15-1} \rfloor \times (15+1)=192>181$
$\lfloor \frac{179}{16-1} \rfloor \times (16+1)=187>181$
$\lfloor \frac{179}{17-1} \rfloor \times (17+1)=198>181$
$\lfloor \frac{179}{18-1} \rfloor \times (18+1)=190>181$
$\lfloor \frac{179}{19-1} \rfloor \times (19+1)=180<181$
Ahora, lo que haremos será comenzar con una sucesión que empiece en $1$ y termine en $N$, y luego le agregaremos términos al inicio y al final sin cambiar la cantidad de enteros de la sucesión.

Supongamos que tenemos $d=\frac{1}{y}$, en la sucesión tendremos (hasta ahora) $y(N-1)+1$ términos, por lo tanto necesitamos un $y$ tal que $y(N-1)+1\leq 180$, es decir $y\leq \frac{179}{N-1}$. Tomemos $y=\lfloor \frac{179}{N-1} \rfloor$.
Además, sabemos que, de extender la sucesión, sólo podremos extenderla $y-1$ términos para cada lado, ya que, al extenderla $y$ términos para algún lado, la sucesión tendría un entero más.

Por lo tanto, podemos en total agregar $2(y-1)$ términos.
Es decir, queremos que:
$180-(y(N-1)+1)\leq 2(y-1)$
$180-(\lfloor \frac{179}{N-1} \rfloor(N-1)+1)\leq 2(\lfloor \frac{179}{N-1} \rfloor-1)$
$181\leq \lfloor \frac{179}{N-1} \rfloor (N+1)$

Para cualquier número entre $2$ y $18$ inclusive, entonces, sabemos que Bat puede cumplir su objetivo, ya que puede conseguir la sucesión de $180$ términos que pase por los números del $1$ y $N$ y por ningún otro entero.

Ahora tenemos que ver entonces que no existe una sucesión de $180$ términos que pase por los enteros del $1$ al $19$, pero por ningún otro entero.

Sabemos, dado que $\lfloor \frac{179}{19-1} \rfloor \times (19+1)=180<181$, que no nos sirve que la diferencia de la sucesión sea $\frac{1}{\lfloor \frac{179}{19-1} \rfloor }$.

Por lo tanto, si la diferencia es $\frac{1}{y}$ (sabemos que debe ser de esa forma), $y\leq \lfloor \frac{179}{19-1} \rfloor -1=8$.
Pero entonces entre $1$ y $N$ habrá ya, como máximo, $9\times (19-1)+1=163$ términos, por lo que faltará agregar como mínimo $17$ términos, por lo que, por Palomar, habrá que agregar por lo menos $9$ términos de alguno de los dos lados, pero como $y\leq 8$, al agregar $9$ términos se agregará al menos un entero a la sucesión, haciendo imposible que haya exactamente $19$ enteros.

Por lo tanto, no existe una sucesión de $180$ términos que incluya a los números entre $1$ y $19$ sin incluir a ningún otro número entero. Entonces es imposible que Bat logre su cometido si $N=19$, y éste es el menor valor para el que no puede.

Martín Lupin

OFO - Medalla de Plata
Mensajes: 15
Registrado: Lun 20 May, 2019 10:26 am
Medallas: 1
Nivel: 1
Ubicación: Mar del Plata

Re: OFO 2020 Problema 6

Mensaje sin leer por Martín Lupin » Sab 01 Feb, 2020 11:29 am

Spoiler: mostrar
Como se trata de una progresión aritmética, entre dos términos enteros siempre habrá la misma cantidad de términos no enteros. Llamemos $k$ a esta cantidad y $k'$ a la cantidad de términos no enteros antes del primer término entero y después del último término entero (nótese que $k'\leq 2k$ ya que sino tendríamos otro término entero). Entonces tenemos
$$(N-1)k+N+k'=180 \qquad (1)$$
Mirando$\bmod N-1$ tenemos $k'\equiv 179\pmod{N-1}$. Si tomamos el menor valor posible de $k'$ obtenemos el mayor valor posible de $k$, por lo que estos valores serían los "mejores" para asegurarnos de que se cumple que $k'\leq 2k$.
Ahora vamos a probar con valores de $N$ hasta llegar a una contradicción en la que obtenemos $k'>2k$. Si $N$ es un divisor de $180$, entonces podemos formar la progresión aritmética $a_n=\frac{N}{180}n$ la cual claramente tiene $N$ términos enteros. Probando con $N=7, 8, 11, 13, 14, 16, 17$ obtenemos valores válidos. Pero con $N=19$ tenemos $k'\equiv 179\equiv 17\pmod{18}$ por lo que tomamos $k'=17$. Reemplazando este valor en la ecuación $(1)$ obtenemos $k=8$ por lo que tenemos $k'>2k$, una contradicción. Luego el menor valor de $N$ para el que la tarea de Bat es imposible es $N=19$
1  

joa.fernandez

FOFO 9 años - Mención Especial OFO - Mención OFO - Medalla de Plata
Mensajes: 13
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 4
Nivel: 3

Re: OFO 2020 Problema 6

Mensaje sin leer por joa.fernandez » Sab 01 Feb, 2020 2:18 pm

Solución: (no sé si es la misma que las de arriba, pero la dejo igual)
Spoiler: mostrar
Sean $a_1, a_2, \ldots , a_{180}$ los números de la progresión y sea $d$ su diferencia.
Si $a_i$ es el primer número entero de la progresión, y $a_{i+k}$ el segundo, con $k$ natural, entonces vale que $a_{i+nk}$, con $n$ natural, será entero. Esto ya que: $a_{i+k} - a_i = kd~~\Rightarrow~~a_{i+nk} = a_i + nkd$, y como en el lado derecho todos los sumandos son enteros, el lado izquierdo también lo es.
Ahora, supongamos que existe un $a_j$ con $i + nk < j < i + (n+1)k$ que también es entero. Luego, sabiendo que restando $k$ veces la diferencia se obtiene otro entero:
$i + nk - nk < j - nk < i + (n+1)k - nk~~\Rightarrow~~i < j - nk < i + k$
Esto quiere decir que $a_{j-nk}$ es un número entero de la progresión que está entre $a_{i}$ y $a_{i + k}$. Absurdo, ya que estos dos eran enteros consecutivos de la progresión.
Luego, todos los números enteros que aparezcan en la progresión serán los de la pinta $a_{i + nk}$.
Viendo los subíndices módulo $k$ tenemos que:
$i~ \equiv ~i + k~ \equiv~ i + nk ~(mód~ k)$
De esto entonces sabemos que la cantidad de números enteros de la progresión serán los congruentes a $i$ módulo $k$, pero esa cantidad es exactamente $\lfloor {\frac {180}{k}} \rfloor$ o $\lfloor {\frac {180}{k}} \rfloor + 1$.
El primer caso se da cuando $k(\lfloor {\frac {180}{k}} \rfloor)$ + $i$ $> 180$, es decir que el posible número de más aparece en un término que no pertenece a la progresión, ya que el subíndice no puede ser mayor a $180$ (recordar que $i$ es mayor a $0$ ya que el menor $a_i$ posible es $a_1$).
El segundo caso se da cuando $k(\lfloor {\frac {180}{k}} \rfloor)$ + $i$ $\leq 180$, donde básicamente, si dividimos en paquetes de $k$ elementos a la progresión, tendremos una cantidad $t$ (con $0 < t < k$) la cual no podremos meter toda en un paquete, pero debido a que $i$ es menor o igual $t$, aporta a la suma de la cantidad de enteros de la progresión.
Sabiendo esto, podemos terminar el problema.
Es trivial encontrar ejemplos para $N < 19$ con lo ya demostrado.
Spoiler: mostrar
Para los $N$ que son divisores de $180$, tomando $a_1 = \frac{N}{180}$ y $d = a_1$ funciona.
Para $N = 7$, tomando $a_1 = \frac{1}{25}$ y $d = a_1$ funciona.
Para $N = 8$, tomando $a_1 = \frac{1}{22}$ y $d = a_1$ funciona.
Para $N = 11$, tomando $a_1 = \frac{1}{16}$ y $d = a_1$ funciona.
Para $N = 13$, tomando $a_1 = \frac{1}{13}$ y $d = a_1$ funciona.
Para $N = 14$, tomando $a_1 = \frac{3}{13}$ y $d = \frac{1}{13}$ funciona.
Para $N = 16$, tomando $a_1 = \frac{1}{11}$ y $d = a_1$ funciona.
Para $N = 17$, tomando $a_1 = \frac{8}{11}$ y $d = \frac{1}{11}$ funciona.
Veamos que para $N = 19$ es imposible.
Supongamos que se puede. Luego:
Dato:
Spoiler: mostrar
Es trivial ver que si $\lfloor a \rfloor > b$ con $a$ racional y $b$ entero $a \geq b$ con $a$ racional y $b$ entero. Esto será usado a continuación.
Caso 1: $\lfloor {\frac {180}{k}} \rfloor = 19$
Si $k = 9 ~~\Rightarrow~~ \lfloor {\frac {180}{9}} \rfloor = 20$ Absurdo.
Si $k < 9 ~~\Rightarrow~~ \frac {180}{k} > \frac {180}{9} ~~\Rightarrow~~ \lfloor {\frac {180}{k}} \rfloor \geq \frac {180}{9} = 20$. Absurdo.
Si $k \geq 10 ~~\Rightarrow~~ \frac {180}{k} \leq \frac {180}{10}~~\Rightarrow~~\lfloor {\frac {180}{k}} \rfloor \leq \frac {180}{10} = 18$. Absurdo.
Caso 2: $\lfloor {\frac {180}{k}} \rfloor + 1 = 19$ y también se tiene que cumplir que: $k(\lfloor {\frac {180}{k}} \rfloor) + i \leq 180$
Si $k = 9~~\Rightarrow~~ \lfloor {\frac {180}{9}} \rfloor + 1 = 21$ Absurdo.
Si $k = 10 ~~\Rightarrow~~ 10(\lfloor {\frac {180}{10}} \rfloor) + i \leq 180 ~~\Rightarrow~~ 180 + i \leq 180$. Absurdo, ya que $i$ es un natural.
Si $k > 10 ~~\Rightarrow~~ \frac {180}{k} < \frac {180}{10} ~~\Rightarrow~~ \lfloor {\frac {180}{k}} \rfloor + 1 < \frac {180}{10} + 1 = 19$. Absurdo.
Si $k < 9~~\Rightarrow~~ \frac {180}{k} > \frac {180}{9} ~~\Rightarrow~~ \lfloor {\frac {180}{k}} \rfloor + 1 \geq \frac {180}{9} + 1 = 21$. Absurdo.
Se sigue que Bat no podrá escribir una progresión aritmética de $180$ números reales con exactamente $19$ números enteros, siendo el menor $N$ con el cual no puede realizarlo.

Responder