Provincial 2015 P2 N3

[3,14]

Determinar cuántos enteros [math]N<10^6 tienen la siguiente propiedad:
Para cada [math]j=2, 3, 4, 5, 6, 7, 8, 9, 10, el resto de dividir [math]N por [math]j es mayor o igual que [math]\frac {j}{2}.

[JPablo]

Las cuentas del final no las voy a hacer porque son fáciles, largas, aburridas y rutinarias. Voy a desarrollar el planteo de las mismas y sus resoluciones quedan a cargo del interesado

Spoiler: mostrar

Para [math]i=2 el resto debe ser mayor o igual a [math]1, la única posibilidad es [math]N\equiv 1\pmod 2

Para [math]i=3 el resto debe ser mayor o igual que [math]1,5, la única posibilidad es [math]N\equiv 2\pmod 3

Para [math]i=4 el resto debe ser mayor o igual que [math]2. Como teníamos ya que [math]N\equiv 1\pmod 2 entonces la única posibilidad es [math]N\equiv 3\pmod 4. Ahora nos podemos olvidar de la condición sobre [math]i=2.

Para [math]i=5 se tiene que el resto debe ser mayor o igual que [math]2,5. Las únicas posibilidades son [math]N\equiv 3\pmod 5 y [math]N\equiv 4\pmod 5

Para [math]i=6 el resto ya quedó determinado por [math]i=2 e [math]i=3, y nos queda [math]N\equiv 5\pmod 6 que satisface la condición.

Para [math]i=7 el resto debe ser mayor o igual que [math]3,5, las únicas posibilidades son [math]N\equiv 4\pmod 7, [math]N\equiv 5\pmod 7 y [math]N\equiv 6\pmod 7

Para [math]i=8 el resto debe ser mayor o igual que [math]4, pero como ya teníamos [math]N\equiv 3\pmod 4 entonces la única posibilidad es [math]N\equiv 7\pmod 8 y nos olvidamos de la condición sobre [math]i=4.

Para [math]i=9 el resto debe ser mayor o igual que [math]4,5, pero teníamos [math]N\equiv 2\pmod 3, luego las únicas posibilidades son [math]N\equiv 5\pmod 9 y [math]N\equiv 8\pmod 9 y nos olvidamos de la condición sobre [math]i=3.

Para [math]i=10 el resto ya queda determinado por los casos [math]i=2 e [math]i=5. Sin embargo, [math]N\equiv 3\pmod 5 implica [math]N\equiv 3\pmod {10}, lo cual no puede ser. En cambio, [math]N\equiv 4\pmod 5 implica [math]N\equiv 9\pmod {10} y eso sí puede ser.

En conclusión, nos quedaron los siguientes sistemas:

[math]N\equiv 4\pmod 5
[math]N\equiv 4,5,6\pmod 7
[math]N\equiv 7\pmod 8
[math]N\equiv 5,8\pmod 9

Son [math]6 sistemas de ecuaciones con módulos coprimos dos a dos. Por el Teorema Chino del Resto se pueden resolver cada uno de ellos y luego proceder rutinariamente para ver cuántos naturales menores que [math]10^6 satisfacen la condición. No voy a hacerlo porque es la parte fácil, larga y aburrida del problema

[LuchoLP]

Espero no haber pifiado en alguna cuenta

Spoiler: mostrar

En principio por la condición del enunciado los restos posibles en la división de [math]N por [math]i son:

[math]2: 1
[math]3: 2
[math]4: 2,3
[math]5: 3,4
[math]6: 3,4,5
[math]7: 4,5,6
[math]8: 4,5,6,7
[math]9: 5,6,7,8
[math]10: 5,6,7,8,9

La primer condición nos dice que [math]N es impar entonces descartamos que [math]N tenga resto: [math]2 mod [math]4, [math]4 mod [math]6, [math]4 mod [math]8, [math]6 mod [math]8, [math]6 mod [math]10, [math]8 mod [math]10. Como [math]N tiene resto [math]2 mod [math]3, descartamos [math]3 mod [math]6, [math]6 mod [math]9 y [math]7 mod [math]9. Como [math]N tiene resto [math]3 mod [math]4, descartamos [math]5 mod [math]8. Como [math]N tiene resto [math]3,4 mod [math]5, descartamos [math]5 mod [math]10 y [math]7 mod [math]10. Como [math]N tiene resto [math]9 mod [math]10, descartamos [math]3 mod [math]5.

Ahora bien, como [math]N tiene resto [math]1 mod [math]2 y [math]2 mod [math]3 digamos [math]N=2a+1=3b+2, de lo que [math]b debe ser de la forma [math]2k+1, es decir que [math]N=3(2k+1)+2=6k+5, que es el dato que ya sabíamos. Es decir que los datos de los restos en la división por [math]2 y por [math]3 están "de más".
De la misma forma, como [math]N tiene resto [math]3 mod [math]4 y [math]4 mod [math]5 llegamos a que esto equivale a que [math]N tenga resto [math]19 mod [math]20, y esto también nos dice que el dato de resto [math]9 mod [math]10 ya no nos interesa.
De que tiene resto [math]5 mod [math]6 y [math]7 mod [math]8 se llega a que [math]N debe tener resto [math]23 mod [math]24. Y sabiendo que [math]N tiene resto [math]19 mod [math]20 y [math]23 mod [math]24, concluímos que tiene resto [math]119 mod [math]120.

Ahora los posibles restos quedaron así:
[math]7: 4,5,6
[math]9: 5,8
[math]120: 119

De las primeras dos se determinan los posibles restos en la división por [math]63, quedando:
[math]63: 5,26,32,41,53,62
[math]120: 119

De esto sale que [math]N debe ser tal de tener en la división por [math]2520 resto [math]599,719,1439,1679,2399,2519.
De los primeros [math]4 casos tenemos [math]397 valores posibles para [math]N en cada uno, y en los últimos dos casos tenemos [math]396 valores posibles para [math]N en cada uno. Esto totaliza un total de [math]2380 valores posibles para [math]N, que es la respuesta al problema.

[3,14]

Lo hice exactamente como JPablo.

[NPCPepe]

LuchoLP, A mi me dio 4762 porque puede tener mas restos en la division por 2520, son 12:
383
1103
2183
503
1223
1943
599
1679
2399
719
1439
2519

[drynshock]

Edito el mensaje dejando una nueva solución, la otra estaba medio mal redactada.

Nueva:

Spoiler: mostrar

El enunciado se traduce a que:
$$N \equiv 1\pmod 2, N \equiv 2 \pmod 3, N \equiv 2,3 \pmod 4$$
$$N \equiv 3,4 \pmod 5 , N \equiv 3,4,5 \pmod{6} , N \equiv 4,5,6 \pmod{7}$$
$$N \equiv 4,5,6,7 \pmod 8 , N \equiv 5,6,7,8 \pmod{9}, N \equiv 5,6,7,8,9 \pmod {10}$$

Vamos a ir descartando a algunas condiciones que no pueden ocurrir en simultaneo. Para eso, notemos primero que $N \equiv 1 \pmod 2 \Rightarrow N \not\equiv 2 \pmod 4 \Rightarrow N \equiv 3 \pmod 4$. Y de manera similar, $N \equiv 3 \pmod{4} \Rightarrow N \not\equiv 4, 5, 6 \pmod{8} \Rightarrow \boxed{N \equiv 7 \pmod{8}}$. Notemos como este resultado nos fusiona las condiciones $N \equiv 1\pmod 2, N \equiv 2,3 \pmod 4, N \equiv 4,5,6,7 \pmod 8$ y a partir de ahora vamos a seguir haciendo lo mismo, hasta llegar a la menor cantidad de ecuaciones posibles.

Siguiendo, $N\equiv2 \pmod 3 \Rightarrow N \equiv 6, 8 \pmod 9 \Rightarrow \boxed{N \equiv 5,8 \pmod 9}$. Además, como $N \equiv 1 \pmod 2 \land N \equiv 2 \pmod 3$ entonces por teorema chino del resto $N \equiv 5 \pmod 6$, de donde $N \not\equiv 3, 4 \pmod 6$

Como $N \equiv 1 \pmod 2 \Rightarrow N \not\equiv 6, 8 \pmod{10} \Rightarrow N \equiv 5,7,9 \pmod{10}$ pero entonces $N \equiv 0,2,4 \pmod 5$ y combinando este resultado con que $N \equiv 3,4 \pmod 5$ obtenemos que $\boxed{N \equiv 4 \pmod 5}$

Entonces, nos queda resolver el siguiente sistema de ecuaciones:
$$N \equiv 7 \pmod 8, N \equiv 5, 8 \pmod 9, N \equiv 4,5,6 \pmod 7, N \equiv 4 \pmod 5$$

Debido a que todos los módulos son coprimos, entonces por teorema chino del resto sabemos que hay una única solución para cada elección de restos. Es decir, para el caso $N \equiv 5 \pmod 9$ y $N \equiv 4 \pmod 7$ tenemos una solución, para $N \equiv 8 \pmod 5$ y $N \equiv 6 \pmod 7$ tenemos otra y así siguiendo.

Resolviendo los sistemas tenemos

$\text{Si } N \equiv 7 \pmod 8 \land N \equiv 4 \pmod 5 \Rightarrow N \equiv -1 \pmod {40}$
$\text{Si } N \equiv -1 \pmod{40} \land N \equiv -1 \pmod 9 \Rightarrow N \equiv -1 \pmod {360}$
$\text{Si } N \equiv -1 \pmod{40} \land N \equiv 5 \pmod 9 \Rightarrow N \equiv 239 \pmod {360}$
$\text{Si } N \equiv -1 \pmod{360} \land N \equiv -1 \pmod 7 \Rightarrow N \equiv -1 \pmod {2520}$
$\text{Si } N \equiv -1 \pmod{360} \land N \equiv 5 \pmod 7 \Rightarrow N \equiv 719 \pmod {2520}$
$\text{Si } N \equiv -1 \pmod{360} \land N \equiv 4 \pmod 7 \Rightarrow N \equiv 1439 \pmod {2520}$
$\text{Si } N \equiv 239 \pmod{360} \land N \equiv 4 \pmod 7 \Rightarrow N \equiv 599 \pmod {2520}$
$\text{Si } N \equiv 239 \pmod{360} \land N \equiv -1 \pmod 7 \Rightarrow N \equiv 1679 \pmod {2520}$
$\text{Si } N \equiv 239 \pmod{360} \land N \equiv 5 \pmod 7 \Rightarrow N \equiv 2399 \pmod {2520}$

Luego, $N \equiv 2519, 2399, 1679, 1439, 719, 599 \pmod{2520}$ son soluciones al problema. Dado que $N < 10^6$ y el mismo es entero positivo, entonces podemos expresarlo como $N = 2520k+r$ donde $k$ es un entero y $r \in \{2519, 2399, 1679, 1439, 719, 599\}$. Ahora veamos que $N < 10^6 \iff 2520k +r < 10^6 \iff x < \frac{10^6-r}{2520}$.

Lo que nos dice $k$ es el numero de soluciones para un mismo resto, pues para $k = 0, 1, 2, \dots$ obtenemos distintos valores de $N$, por consiguiente:

$\text{Si } r = 2519 \Rightarrow x < \frac{10^6-2519}{2520} \approx 395,82 \Rightarrow \underbrace{x = 0, 1, \dots, 395}_{396 \text{ valores}}$
$\text{Si } r = 2399 \Rightarrow x < \frac{10^6-2399}{2520} \approx 395,87 \Rightarrow \underbrace{x = 0, 1, \dots, 395}_{396 \text{ valores}}$
$\text{Si } r = 1679 \Rightarrow x < \frac{10^6-1679}{2520} \approx 396,15 \Rightarrow \underbrace{x = 0, 1, \dots, 396}_{397 \text{ valores}}$
$\text{Si } r = 1439 \Rightarrow x < \frac{10^6-1439}{2520} \approx 396,25 \Rightarrow \underbrace{x = 0, 1, \dots, 396}_{397 \text{ valores}}$
$\text{Si } r = 719 \Rightarrow x < \frac{10^6-719}{2520} \approx 396,54 \Rightarrow \underbrace{x = 0, 1, \dots, 396}_{397 \text{ valores}}$
$\text{Si } r = 599 \Rightarrow x < \frac{10^6-599}{2520} \approx 396,58 \Rightarrow \underbrace{x = 0, 1, \dots, 396}_{397 \text{ valores}}$

Por lo tanto, hay un total de $396.2+397.4 = 2380$ números que cumplen las condiciones.

Vieja:

Spoiler: mostrar

Independientes

j = 2
$N \equiv 1 (mod 2)$

j = 3
$N \equiv 2 (mod 3)$

j = 5
$N \equiv 3, 4 (mod 5)$

j = 7
$\boxed{N \equiv 4, 5, 6 (mod 7)}$

Teorema chino del resto

j = 4
$N \equiv 2, 3 (mod 4)$
Pero como $x \equiv 1 (mod 2)$ entonces sabemos que:
$N \equiv 3 (mod 4)$

j = 6
Sabiendo que:
$N \equiv 1 \equiv -1 (mod 2)$
$N \equiv 2 \equiv -1 (mod 3)$

Se llega a que $\boxed{N \equiv -1 \equiv 5 (mod 6)}$ por lo tanto, cumple la consigna.

j = 8
Sabiendo que:
$N \equiv 3 (mod 4)$

Se llega a que:
$N \equiv 3, 7 (mod 8)$

Sin embargo solamente cumple $\boxed{N \equiv 7 (mod 8)}$

j = 9
Sabiendo que:
$N \equiv 2 (mod 3)$

Se llega a que:
$N \equiv 2, 5, 8 (mod 9)$

Sin embargo solamente cumplen los casos $\boxed{N \equiv 5, 8 (mod 9)}$

j = 10
Caso 1)
$N \equiv 1 \equiv 3 (mod 2)$
$N \equiv 3 (mod 5)$

$\therefore N \equiv 3 (mod 10)$
$\Rightarrow \Leftarrow$

Concluimos entonces que $x \not \equiv 3(mod 5)$

Caso 2)
$N \equiv 1 \equiv -1 (mod 2)$
$N \equiv 4 \equiv -1 (mod 5)$

$\therefore \boxed{N \equiv -1 \equiv 9 (mod 10)}$ el cual cumple



Teorema chino del resto final
Sabiendo que:
$N \equiv 4 (mod 5)$
$N \equiv 5, 8 (mod 9)$
$N \equiv 7 (mod 8)$
$N \equiv 4, 5, 6 (mod 7)$

Veamos que con $5, 9, 8$ y $7$ podemos formar todos los demás casos $(2, 3, 4, 6)$. Además, como $5, 9, 8$ y $7$ son todos coprimos entre si, entonces sabemos que hay una única solución para cada resto, precisamente $2$ restos del $9$ y $3$ restos del $7$. Esto nos deja con un aproximado de $\lfloor \frac{10^6}{2520} \rfloor.6 = 2376$ números que satisfacen.

Ahora nos queda ver cuantos números satisfacen entre $2520.396 = 997,920$ y $10^6$ o lo que vendría a ser igual a calcular los casos entre $0$ y $2080$.

Por teorema chino del resto con:
$N \equiv 4 \equiv -1(mod 5)$
$N \equiv 8 \equiv -1(mod 9)$
$N \equiv 7 \equiv -1(mod 8)$
$N \equiv 6 \equiv -1(mod 7)$

Se llega a que $N \equiv -1 \equiv 2519 (mod 2520)$ por lo tanto no hay solución.


En el caso de:
$N \equiv 4 (mod 5)$
$N \equiv 8 (mod 9)$
$N \equiv 7 (mod 8)$
$N \equiv 5 (mod 7)$

Se llega a que $N \equiv 719 (mod 2520)$ cumple


En el caso de:
$N \equiv 4 \equiv (mod 5)$
$N \equiv 5 \equiv (mod 9)$
$N \equiv 7 \equiv (mod 8)$
$N \equiv 6 (mod 7)$

$N \equiv 2399 (mod 2520)$ no cumple


En el caso de:
$N \equiv 4 \equiv (mod 5)$
$N \equiv 5 \equiv (mod 9)$
$N \equiv 7 \equiv (mod 8)$
$N \equiv 6 (mod 7)$

$N \equiv 1679 (mod 2520)$ cumple


En el caso de:
$N \equiv 4 \equiv (mod 5)$
$N \equiv 5 \equiv (mod 9)$
$N \equiv 7 \equiv (mod 8)$
$N \equiv 4 (mod 7)$

$N \equiv 599 (mod 2520)$ cumple

Por lo tanto, hay $4$ números mas que cumplen lo cual nos deja con un total de $\boxed{2380}$ que cumplen las condiciones.