Ibero 2020 - P2

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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
Mensajes: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Ibero 2020 - P2

Mensaje sin leer por Gianni De Rico »

Para cada entero positivo $n$, se define $T_n$ como el menor entero positivo tal que $1+2+\cdots +T_n$ es múltiplo de $n$. Por ejemplo, $T_5=4$ puesto que $1$, $1+2$ y $1+2+3$ no son múltiplos de $5$, pero $1+2+3+4$ sí es múltiplo de $5$.
Determine todos los enteros positivos $m$ tales que $T_m\geqslant m$.

Nota. Todo entero positivo es múltiplo de sí mismo.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 985
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 13
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Ibero 2020 - P2

Mensaje sin leer por Fran5 »

Spoiler: mostrar
Si $n>1$ es impar, es $T_n \leq n-1$ ya que
$1+2+ \ldots + n-1 = \frac{n(n-1)}{2} \equiv 0 \pmod{n}$
¿Qué pasará en el caso opuesto?

Si $n = 2^k$ entonces para todo $m < n = 2^k$ es
$1 +2 +\ldots + m = \frac{m(m+1)}{2}$ el cual es imposible que sea múltiplo de $2^k = n$

Si $n = 2^kI$ con $I > 1$ impar, entonces $gcd(I,2) = 1$
En este caso como $gcd(I,2^k) = 1$, buscamos $j<2^k$ tal que $Ij \equiv \pm 1 \pmod{2^{k+1}}$ y verifique alguna de las siguientes
$1+ 2+ \ldots + jI \equiv \frac{(jI)(jI+1)}{2}$
$1+ 2 + \ldots + jI -1 \equiv \frac{(jI)(jI-1)}{2}$

La pregunta es, existe tal $j$ ?

En particular, sabemos que dentro del rango $0 < j < 2^{k+1}$ este $j$ es único.
Supongamos entonces que las soluciones que encontramos a $xI \equiv 1 \pmod{2^{k+1}}$ e $yI \equiv -1 \pmod{2^{k+1}}$ son ambas mayores (estricto) que $2^{k}$.

Como $x \neq y$ y son impares, podemos suponer que $2^k < x < y < 2^{k+1}$, luego $z = \frac{y-x}{2} \in \mathbb{N}$ verifica
$zI \equiv \frac{1}{2} (-1- 1) \equiv \frac{2}{2} \pmod{2^{k+1}}$.
Luego $zI \equiv -1 \pmod{2^{k+1}}$ con $0 < z < 2^{k}$

(si $y < x$ tomamos $z = \frac{x-y}{2}$ con $zI \equiv 1 \pmod{2^{k+1}}$)

Finalmente, encontramos nuestro $j := z$, de donde $0 < I-1 \leq T_n \leq zI < 2^k I = n$

Esto es, $T_n \geq n$ si y sólo si $n$ es potencia de $2$ (en particular para $n=1$ esto vale!)
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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
Mensajes: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Ibero 2020 - P2

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Primero que nada, vemos que la suma pedida es $\frac{T_n(T_n+1)}{2}$, en realidad los $T_n$ casi nunca van a aparecer, lo que importa es que la cuenta nos da un número de la forma $\frac{k(k+1)}{2}$. De acá sale la observación clave del problema: Como $k$ y $k+1$ son coprimos, si queremos que la fracción sea múltiplo de $n$, entonces los factores primos de $n$ van a estar "separados" entre $k$ y $k+1$ (o sea, si por ejemplo $k$ es múltiplo de $3$, todos los factores $3$ de $n$ tienen que estar en $k$).

Vamos a resolver primero el caso donde $T_n<n$, para el que nos alcanza simplemente con fabricar un número $x<n$ tal que $\frac{x(x+1)}{2}$ sea múltiplo de $n$. Este es el caso en que $n$ no es una potencia de $2$.
Como no es potencia de $2$, tenemos que $n=2^k\cdot (2t+1)$ con $t$ entero positivo. Por lo que dijimos antes, cada primo que divide a $n$ va a aparecer en uno sólo entre $x$ y $x+1$, como el único primo del que tenemos información es $2$, vamos a tratar de hacer que uno de los números sea múltiplo de $2t+1$ y el otro tenga todos los factores $2$, pero como estamos dividiendo por $2$, en realidad lo que necesitamos es que sea múltiplo de $2^{k+1}$.
Notemos entonces que como $2t+1$ y $2^{k+1}$ son coprimos, $2t+1$ tiene inverso módulo $2^{k+1}$, es decir, existe $0<m<2^{k+1}$ tal que $(2t+1)m\equiv 1\pmod{2^{k+1}}$.
Si $m<2^k$, entonces eligiendo $x=(2t+1)m-1$ tenemos que $x$ es múltiplo de $2^{k+1}$ y $x+1=(2t+1)m$ es múltiplo de $2t+1$, como $x<n$ ya tenemos el ejemplo.
Ahora, si $m>2^k$ (no puede ser $2^k$ porque no es invertible), entonces $2^{k+1}-m<2^k$, además $\left (2^{k+1}-m\right )(2t+1)\equiv -m(2t+1)\equiv -1\pmod{2^{k+1}}$, entonces eligiendo $x=\left (2^{k+1}-m\right )(2t+1)$ tenemos que $x$ es múltiplo de $2t+1$ y $x+1$ es múltiplo de $2^{k+1}$, como $x<n$ ya tenemos el ejemplo.

Ahora, cuando $n$ es una potencia de $2$ esta construcción no anda, básicamente porque $2t+1=1$ y entonces $m=1$, así que no hay mucho que podamos hacer.
Para demostrar que si $n=2^k$ entonces $T_n\geqslant n$, recurrimos nuevamente a la observación clave, todos los factores $2$ van a tener que estar en $x$ o en $x+1$, más aún, al que le toque va a tener que ser múltiplo de $2^{k+1}$ para cubrir al $2$ que está dividiendo. Si $x$ es múltiplo de $2^{k+1}$ entonces claramente es mayor que $n$. Si $x+1$ es múltiplo de $2^{k+1}$ entonces $x+1\geqslant 2n$, si pasara que $x<n$ tendríamos $2n\leqslant x+1<n+1$, de modo que $n<1$, absurdo. Entonces $x\geqslant n$.
En ambos casos si un número cumple lo pedido tiene que ser mayor o igual a $n$, de modo que $T_n\geqslant n$, y con eso estamos.

En resumen, los números que cumplen lo que dice el enunciado son las potencias de $2$.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Responder