Problema interesante #3

Avatar de Usuario
BR1

OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Medalla-FOFO Pascua 2024 FOFO 14 Años - Medalla-FOFO 14 años
Mensajes: 604
Registrado: Sab 28 Oct, 2023 1:33 pm
Medallas: 3
Nivel: 1

Problema interesante #3

Mensaje sin leer por BR1 »

Para cada entero positivo $n$, denominamos $p(n)$ al mayor divisor impar de $n$, y sea $q(n)=p(n)+p(n+1)+p(n+2)+ \ldots +p(2n)$.
Hallar todos los enteros positivos $m$ para los cuales $q(m)=8145$.
ACLARACIÓN: $1$ no es primo
Leiva24
Mensajes: 1
Registrado: Jue 31 Oct, 2024 1:29 pm
Nivel: Exolímpico

Re: Problema interesante #3

Mensaje sin leer por Leiva24 »

Spoiler: mostrar
Tenemos un n entero positivo. La función p(n) recibe un número y entrega su mayor divisor impar, mientras que la función q(n) recibe un p(n) devuelve una sumatoria desde p(n) hasta p(2n).

Como q(n) = p(n) + p(n+1) ... p(2n) recibe todos integrantes impares, el valor de q(n) va a ser par o impar dependiendo de la cantidad de elementos. Al ser n un entero positivo impar, la cantidad de p(n)s va desde un impar hasta un par, por lo que se podría reagrupar impar par hasta el final, por ende, va a ser una cantidad par de elementos, por ende, q(n) va a ser par (un número par de impares sumados es un número par).
Al contrario, si n es par, la cantidad de elementos va a ser impar, ya que tomamos desde un par hasta otro.
Está claro que como queremos que q(n) == 8145, entonces n no puede ser impar.
También notamos que para todos los impares constantemente p(n) = n ya que se pueden dividir por sí mismos y ser su mayor divisor impar.
Todos los pares también tienen sus reglas: constantemente los vamos a dividir por 2 hasta que nos den un número impar, pero el rango de nuestra sumatoria es desde un n hasta un 2n, por lo que si dividimos un número por 2 ya es menor que n. De esto deducimos que los pares desde n hasta 2n no se van a repetir, incluso cuando los dividamos por 2, salvo n y 2n. Entonces a mayor número de elementos tendremos desde 1,3 ... n-1 el rango de los resultados finales de los pares, salvo el correspondiente a n, que está sumado 2 veces.
Si probamos con un par de ejemplos, notamos que para un q(n) cualquiera tenemos n+1 elementos que integran la sumatoria.
Entonces con n+1 integrantes, podemos pensar la situación como una suma de Gauss.
Cada para impar vamos sumando desde n+1 (primer impar), n+3, n+5 ... 2n-1 y para cada par vamos sumando desde n-1, n-3 ... 1, esto con n dos veces. Entonces como los términos se van cancelando, el promedio de estos es n
Quitando n de esta sumatoria, que está 2 veces, y el término que lo cancelaría, tenemos que n*n-2 + (p(n) + p(2n) + 2n-p(n)) = q(n). Esto es n (promedio) multiplicado por n-2 (número de elementos ya que sustrajimos p(n) como primer elemento, p(2n) como último elemento y 2n-p(n) como elemento asociado a p(n) dentro de la sumatoria. Entonces es (n+1) - 3 = n-2) más los otros dos. Como ya probamos antes, p(n) = p(2n) por lo que se puede reescribir n*(n-2) + 2n + 2p(n) - p(n). Usamos factor común entre n*(n-2) y 2n y restamos los p(n) y nos queda q(n) = n*(n-2+2) + p(n).
Es decir, n*n + p(n) = q(n). Entonces 8145 tiene que estar cerca de un cuadrado perfecto de un n, cuyo p(n) sea el resto.
Además n era obligatoriamente par, por lo que rápido se nos ocurre n = 90, ya que 90*90 = 8100 y p(90) = 45.
Se puede verificar haciendo la sumatoria:

(45 91 23 93 47 95 3 97 49 99 25 101 51 103 13 105 53 107 27 109 55 111 7 113 57 115 29 117 59 119 15 121 61 123 31 125 63 127 1 129 65 131 33 133 67 135

17 137 69 139 35 141 71 143 9 145 73 147 37 149 75 151 19 153 77 155 39 157 79 159 5 161 81 163 41 165 83 167 21 169 85 171 43 173 87 175 11 + (177 + 89 + 179 + 45) = 8145

Entonces el único m existente es 90.
1  
Responder