Provincial Urbana/Salado/Fortines 2012 N3 P2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
hayequipo
Mensajes: 21
Registrado: Mar 20 Sep, 2011 10:26 am
Nivel: Exolímpico

Provincial Urbana/Salado/Fortines 2012 N3 P2

Mensaje sin leer por hayequipo »

Definimos $f(n)$ en los enteros no negativos de la siguiente manera: $f(0)=0$, $f(1)=0$, $f(2)=1$ y para $n\geq 3$, sea $f(n)$ el menor entero positivo que no divide a $n$.
Sea $F(n)=f(f(f(n)))$. Sea $S$ la suma de los primeros valores de $F$ aplicada a los números del $1$ al $2012$ inclusive, es decir,$$S=F(1)+F(2)+F(3)+\cdots +F(2012).$$Calcular el valor de $S$.
ivandiaz95
Mensajes: 16
Registrado: Vie 02 Sep, 2011 6:06 pm
Nivel: Exolímpico
Ubicación: Rosario, Santa Fe

Re: Provincial Urbana/Salado/Fortines 2012 N3 P2

Mensaje sin leer por ivandiaz95 »

Spoiler: mostrar
Primero hay que darse cuenta de que $f(f(2))=0$;
por lo que $n \equiv 1 (mod 2) \Rightarrow F(n)=0$, o sea si $n$ es impar, como $2$ es el menor numero que no lo divide:
$F(n)=f(f(f(n)))=f(f(2))=f(0)=0$
Entoces decartás de la suma a los impares.

Ahora con los pares.
*Para que un numero par no sea divisible por 3, no debe ser multiplo de 6

Entonces suponiendo que $n$ es un par no multiplo de 3, entonces el menor numero que no divide a $n$ es 3
$F(n)=f(f(f(n)))=f(f(3)) = f(2) = 1$
Todos los pares no múltiplos de 6 te dan 1 si le aplicas F;
Hay $2012/2 - 2012/6 = 671$ (redondeando a menor entero) no multiplos de 6

El el caso para los multiplos de $6$, se pueden formar de 2 formas;
1) $n=k\cdot 3\cdot 2$ con k impar
2) $n=2k\cdot 3\cdot 2$ con k impar

En el primer caso, veremos que $f(n)$ será 4 porque $k$ es impar. Entonces $F(n)=f(f(4))=f(3)=2$

En el segundo caso decimos que ademas de ser múltiplo de 6, lo es también de 12
Entonces con los multiplos de 12 sería: (sindo n multiplo de 12)
$f(n)=f(2k\cdot 3\cdot 2)$
Lo que podemos ver es que, $f(n)$ no será 2,3,4,6 ni ningún componente de k.
Lo que si sabemos es que si $f(n)$ es impar: $F(n)=f(f(impar))=f(2)=1$

Y si $f(n)$ es par, $f(f(n))$ será 3, esto de debe a que $f(n)$ no puede ser un múltiplo de 3 porque $n$ es multiplo de 3

Entonces $F(n)= f(3)= 2$.

Ahora solo queda botener $S$

S= Suma de todos los F(pares no multiplos de 6) + Suma de todos los F(multiplos de 12) + Suma de todos los F(multiplos de 6 y no de 12)

Como cada 12 elementos tenemos un multiplo de 12 y otro de 6 solo no de 12 a partir de 6; tenemos $2+1=3$ cada 12

$3(2012-6)/12 = 501,5$ por lo que ese $,5$ representa 6 elementos, pero necesitamos 7 para contar al multiplo de 12 (que da 2)
6,7,8,9,10,11,12,13,14,15,16,17
18,19,20,21,22,23,24,25,26,27,28,29
30,31,32,33,34,35,36,37,38,39,40,40
etc....
Entonces:
$S = 671 + 501 + 1 = 1173$
Creo que ese era el resultado, tenga dudas, no me acurdo si me había dado
Spoiler: mostrar
1173
o
Spoiler: mostrar
1175
:)
Última edición por ivandiaz95 el Vie 25 Oct, 2013 12:33 pm, editado 3 veces en total.
Avatar de Usuario
Vladislao

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
FOFO Pascua 2017 - Jurado-FOFO Pascua 2017
Mensajes: 808
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Provincial Urbana/Salado/Fortines 2012 N3 P2

Mensaje sin leer por Vladislao »

Una solución casosa.
Spoiler: mostrar
Lema 1: [math] siempre que [math].

Demostración:

Es claro que si [math], como [math] es el menor entero que no divide a [math], tenemos en particular que todos los números naturales menores ó iguales a [math] dividen a [math]. Como corolario de ésto, se sigue que los primero [math] números naturales son divisores de [math], y por ende, el mínimo común múltiplo de estos números divide a [math]. Pero, como [math], entonces, debe ser que [math] divide a [math], pero [math] es menor que [math], absurdo.

Casos:

1) Si [math], entonces [math], donde además [math] es tal que [math] no es múltiplo de [math]. En particular, [math], y [math] no múltiplo de 3. Es decir, [math] puede ser [math] y [math].

2) Si [math], entonces [math], donde [math] es tal que [math] no es múltiplo de 8. Es decir [math] donde [math] es impar. En total hay [math] valores posibles para [math].

3) Si [math], entonces [math], donde [math] es tal que [math] no es múltiplo de 7. O sea [math], donde [math] no es múltiplo de 7. Como [math], se tiene que [math]. Como los únicos múltiplos de 7 menores que 33 son 7, 14, 21 y 14, en total [math] puede tomar [math] valores.

4) Si [math], entonces [math] y [math] son divisores de [math], y por ende [math], lo cual es absurdo.

5) Si [math], entonces [math], donde [math] es tal que [math] no es múltiplo de 5. O sea, [math] y [math] no es múltiplo de 5. Como [math], debe ser [math], como hay 33 múltiplos de 5 menores que 167, en total [math] puede tomar 134 valores.

6) Si [math], entonces [math] donde [math] es impar. De manera análoga, debe ser [math] y como [math] es impar, [math] puede tomar [math] valores.

7) Si [math], entonces [math] donde [math] no es múltiplo de 3. De manera análoga, se ve que [math], y hay 335 números que son múltiplos de 3 menores que 1006, luego [math] puede tomar 670 valores, dado que [math] no tendría sentido.

8) Si [math] entonces [math] es impar. O sea, [math] puede tomar 1006 valores.

Ahora, [math], donde [math]. Además, [math] y [math]. Luego, de ésto, es sencillo concluir que la suma buscada es:

[math].
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 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
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 610
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Provincial Urbana/Salado/Fortines 2012 N3 P2

Mensaje sin leer por Turko Arias »

Casi nadie lo hizo a este problem, y la mayoría de los que lo hicieron tuvieron el error de no darse cuenta que
Spoiler: mostrar
$F(2)=0$
y les dio
Spoiler: mostrar
$1776$.
Me gustó la solución "casosa" esa jajaj yo lo hice así
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1124
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Re: Provincial Urbana/Salado/Fortines 2012 N3 P2

Mensaje sin leer por drynshock »

POR FAVOR AYUDA, me tienen secuestrado en Av Santa Fe 3312 piso 9 - CABA y me hacen trabajar las 24 hs del día para subir estos problemas.
Spoiler: mostrar
Tenemos $S = F(1) + F(2) + ... + F(2012)$, notemos que $f(2k+1) = 2$ ya que $2k + 1 \equiv 1 (mod 2)$. Luego nos queda que $F(2k+1) = f(f(2)) = f(1) = 0$, por lo que todos los términos impares se cancelan, dejándonos con $S = F(2) + F(4) + ... + F(2012)$.

Ahora veamos que en la nueva suma $F'(n) = F(\frac{n}{2})$. Como todos los términos que nos quedaron en la suma son pares, entonces $min$ divisor de $(n) \neq 2$, por lo que sabemos que podemos dividir por 2 si alterar el resultado. La nueva suma: $S = F'(1) + F'(2) + ... + F'(1006)$.

Ahora tenemos que ver cuantos de estos NO son divisibles entre 3. La cuenta seria: $1006 - \lfloor \frac{1006}{3} \rfloor = 671$, es decir, al total le sacamos los múltiplos de 3 y eso nos da los que no son múltiplos de 3. Llamemos $k$ a los números que no son múltiplos de 3, luego $F'(k) = f(f(3)) = f(2) = 1$, lo cual nos deja con un total de $671$ números con un valor de 1 cada uno, por lo que la suma quedaría: $S = 671 + F'(3) + F'(6) + ... + F'(1005)$
Spoiler: mostrar
PARA PARA PARA, seguro no te diste cuenta que hay un caso especial donde esto no se cumple. Precisamente para $F'(1) = F(2) = f(f(f(2))) = 0$ por lo que la suma en este caso no da 1, si no que da 0. Entonces la suma real es: $S = 670 + F'(3) + F'(6) + ... + F'(1005)$
Viendo que $S = 670 + F'(3) + F'(6) + ... + F'(1005)$, ahora podemos hacer $F''(n) = F'(\frac{n}{3})$, lo cual nos deja con $S = 670 + F''(1) + F''(2) + ... + F''(335)$. Podemos repetir el proceso de calcular cuantos no son múltiplos de 4 en este caso, notemos que todos estos $F''(k) = F(6k)$ por lo cual si $k \equiv 0 (mod 2) \Rightarrow 4 | n$. Entonces la cuenta nos queda: $335 - \lfloor \frac{335}{2} \rfloor = 168$ números que no son múltiplos de 4, luego $F'' = f(f(4)) = f(3) = 2$, por lo tanto la suma queda: $S = 670 + 168.2 + F''(2) + F''(4) + ... + F''(334)$.

Repetimos el proceso: $F'''(n) = F''(\frac{n}{2})$, $S = 670 + 168.2 + F'''(1) + F'''(2) + ... + F'''(167)$. Sacamos los que no son múltiplos de 5: $167 - \lfloor \frac{167}{5} \rfloor = 134$. $F''' = f(f(5)) = f(2) = 1$, luego $S = 670 + 168.2 + 134 + F'''(5) + F'''(10) + ... + F'''(165)$.

Repetimos, $F^{IV}(n) = F'''(\frac{n}{5})$, $S = 670 + 168.2 + 134 + F^{IV}(1) + F^{IV}(2) + ... + F^{IV}(33)$. Notemos que los no múltiplos de 6 ya fueron considerados al quitar los de $2$ y $3$, por lo que pasamos a sacar directamente los que no son múltiplos de 7: $33 - \lfloor \frac{33}{7} \rfloor = 29$. $F^{IV} = f(f(7)) = f(2) = 1$, luego $S = 670 + 168.2 + 134 + 29 + F^{IV}(7) + F^{IV}(14) + ... + F^{IV}(28)$.

$F^{V}(n) = F^{IV}(\frac{n}{7})$, $S = 670 + 168.2 + 134 + 29 + F^{V}(1) + F^{V}(2) + ... + F^{V}(4)$. Para quitar los no múltiplos de 8 simplemente dividimos por 2 ya que antes quitamos los no múltiplos de 4: $4 - \lfloor \frac{4}{2} \rfloor = 2$. $F^{V} = f(f(8)) = f(3) = 2$, luego $S = 670 + 168.2 + 134 + 29 + 2.2 + F^{V}(1) + F^{V}(2)$

Finalmente, nos queda quitar los no múltiplos de 9, pero como ya quitamos los de 3 antes, simplemente dividimos por 3. En este caso como solamente tenemos $F^{V}(1) + F^{V}(2)$ es fácil notar que ninguno es múltiplo de 9 y por lo tanto $F^{VI} = f(f(9)) = f(2) = 1$, luego $S = 670 + 168.2 + 134 + 29 + 2.2 + 2 \Rightarrow $

$$\boxed{S = 1175}$$

$\blacksquare Q.E.D \square .$
Y todos los fines de demostración que se puedan imaginar
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
Avatar de Usuario
biank
Mensajes: 38
Registrado: Vie 02 Dic, 2022 9:57 pm
Nivel: 3

Re: Provincial Urbana/Salado/Fortines 2012 N3 P2

Mensaje sin leer por biank »

Spoiler: mostrar
Lemma: $f(n) = p^k$ con $p$ primo para $n > 2$.
Spoiler: mostrar
Supongamos que $f(n) = c$ donde $c$ es un número con al menos dos factores primos.
Entonces es divisible por algún primo $p$. Sea $k$ el máximo natural tal que $p^k \mid c$

$c = p^k \cdot m$.
$p^{k + 1} \nmid n \Rightarrow p^{k + 1} \nmid p^k \cdot m \Rightarrow p \nmid m \Rightarrow \gcd(p^k, m) = 1 \Rightarrow \operatorname{lcm}(p^k, m) = p^k \cdot m = c$

Como $p^k < c$ y $m < c$, por definición de $f(n)$ ambos deben dividir a $n$.
Si $a \mid n$ y $b \mid n \Rightarrow \operatorname{lcm}(a, b) \mid n$. Entonces si $p^k \mid n$ y $m \mid n \Rightarrow m \mid n$ lo cual es una contradicción, por lo que la suposición inicial era falsa y $f(n)$ no puede tener dos o más factores primos, por lo que $f(n) = p^k$ con $p$ primo.
$n \equiv 1 \mod 2$
Spoiler: mostrar
$n = 1 \Rightarrow F(n) = f(f(f(1))) = f(f(0)) = f(0) = 0$
$n > 1 \Rightarrow f(n) = 2 \Rightarrow F(n) = f(f(2)) = f(1) = 0$
$n \equiv 0 \mod 2$
Spoiler: mostrar
$n = 2 \Rightarrow F(n) = f(f(f(2))) = f(f(1)) = f(0) = 0$
Recordemos que $f(n) = p^k$.
$p\neq 2$
Spoiler: mostrar
$F(n) = f(f(f(n))) = f(f(p^k))$ y como $p \equiv 1 \mod 2 \Rightarrow p^k \equiv 1 \mod 2 \Rightarrow f(n) = 2$
$F(n) = f(2) = 1$
$p=2$
Spoiler: mostrar
$F(n) = f(f(f(n))) = f(f(p^k))$ y como $p^k$ es una potencia de dos el menor número que no lo divide es $3$.
$F(n) = f(3) = 2$.
Entonces hay $3$ tipos de números y la suma va a ser $S=0A + 1B + 2C$ donde $A + B + C = 2012$ y $A$ son la cantidad de impares (más el 2 que también da $F(0) = 0$), $B$ es la cantidad de pares mayores a 2 tal que $f(n) = p^k$ con $p \neq 2$ y $C$ es la cantidad de pares tal que $f(n) = p^k$ con $p = 2$.
$0A + 1B + 2C = (B + C) + C = (2012 - A) + C$. La cantidad de números que $F(n) = 0$ es $A = \frac{2012}{2} + 1 = 1007$.

Ahora para contar los pares tal que $f(n) = p^k$ con $p = 2$ veamos que para que $f(n) = x$ debe suceder que $x \equiv 0 \mod \operatorname{lcm}(1, 2, \cdots, x - 1)$ pero $x \not\equiv 0 \mod \operatorname{lcm}(1, 2, \cdots, x)$
$k > 1$ porque como $n$ es par, $2^1 \mid n$
$k < 4$ ya que $\operatorname{lcm}(1, 2, \cdots, 2^4 - 1) > 2012$
Entonces solo quedan los casos $f(n) = 4$ y $f(n) = 8$
$f(n) = 4$
Spoiler: mostrar
$\operatorname{lcm}(1,2,3) = 6$, $\operatorname{lcm}(1,2,3,4) = 12$
$x \equiv 0 \mod 6$, $x \not\equiv 0 \mod 12$
Cantidad: $\lfloor \frac{2012}{6} \rfloor - \lfloor \frac{2012}{12} \rfloor = 168$
$f(n) = 8$
Spoiler: mostrar
$\operatorname{lcm}(1,2,3,4,5,6,7) = 420$, $\operatorname{lcm}(1,2,3,4,5,6,7,8) = 840$
$x \equiv 0 \mod 420$, $x \not\equiv 0 \mod 840$
Cantidad: $\lfloor \frac{2012}{420} \rfloor - \lfloor \frac{2012}{840} \rfloor = 2$
Por lo que $C=168+2=170$ y $S=2012-1007+170=1175$
Responder