Dado un entero positivo [math]N, se dice que [math]N es fofeable si, al reemplazar [math]N sucesivamente por [math]N-p_N, donde [math]p_N es el primo más grande que satisface [math]p_N\leq{N}, se obtiene el [math]1. Por ejemplo el [math]4 es fofeable ya que [math]4\rightarrow{1} pero el [math]3 no ya que [math]3\rightarrow{0}. Demostrar que entre los primeros [math]2^{2017} enteros positivos, hay entre [math]2^{2015} y [math]2^{2016} números fofeables.
Parte [math]1: Ver que no hay dos números consecutivos fofeables
Si [math]N es fofeable, entonces [math]N+1 no es fofeable. Cuando aplicamos el procedimiento con [math]N+1, tenemos dos posibles situaciones.
En algún momento antes del último paso llegamos a un primo, lo que nos lleva a [math]0, entonces [math]N+1 no es fofeable.
No llegamos nunca a un primo antes del último paso, entonces en cada paso le restamos el mismo número que a [math]N, por lo que en el último paso llegamos a [math]1+1=2, que es primo, lo que nos lleva a [math]0, entonces [math]N+1 no es fofeable.
Por lo tanto, si [math]F es la cantidad de números fofeables hasta [math]x, entonces [math]F\leq \frac{x}{2}. Notemos que hay grupos de [math]3 números consecutivos no fofeables (por ejemplo [math]15, [math]16 y [math]17), entonces [math]F<\frac{x}{2}
Parte [math]2: Ver que en cualquier grupo de [math]4 números consecutivos hay al menos uno fofeable.
Sea [math]S_N la suma de todos los números que le restamos a [math]N. [math]N es fofeable si [math]N-S_N=1. Si [math]N-p_N es fofeable entonces [math]N-p_N-S_{N-p_N}=1, pero [math]S_{N-p_N}=S_N-p_N, entonces [math]N-p_N-S_{N-p_N}=N-p_N-S_N+p_N=N-S_N=1, entonces [math]N es fofeable.
Vamos a demostrar por inducción fuerte que en cualquier grupo de [math]4 números consecutivos (comenzando en [math]M\equiv 1(4)) al menos uno es fofeable.
Sea [math]N>12 un número fofeable y [math]N\equiv 2(4). Supongamos como hipótesis inductiva que en cualquier grupo de [math]4 números consecutivos hasta [math]N hay al menos uno fofeable (se cumple para algún caso ya que los números [math]1,4,6,8,12 son fofeables). Si [math]N+5 es fofeable entonces se sigue cumpliendo que en cualquier grupo de [math]4 números consecutivos (comenzando en [math]M\equiv 1(4)) hay al menos uno fofeable (podemos armar los grupos [math]N-1,N,N+1,N+2 y [math]N+2,N+3,N+4,N+5 por ejemplo, que con certeza contendrán un [math]1\pmod 4). Supongamos que ninguno de [math]N+1,N+2,N+3,N+4,N+5 es fofeable, entonces ninguno de [math]N+1,N+2,N+3,N+4 puede ser primo, ya que si [math]x es primo entonces [math]x+1 es fofeable. Como no hay dos primos consecutivos (ya que [math]N>12); [math]p_{N+1}=p_{N+2},p_{N+2}=p_{N+3},p_{N+3}=p_{N+4}; entonces [math]p_{N+1}=p_{N+2}=p_{N+3}=p_{N+4}. Entonces al aplicar la operación nos quedan los números [math]N+1-p_{N+1},N+2-p_{N+2}=N+2-p_{N+1},N+3-p_{N+3}=N+3-p_{N+1},N+4-p_{N+4}=N+4-p_{N+1}. Que son [math]4 números consecutivos menores que [math]N, por lo que alguno de ellos es fofeable, entonces alguno de [math]N+1,N+2,N+3,N+4 es fofeable, y claramente uno de ellos es [math]1\pmod 4. Esto completa la inducción.
Por lo tanto, si [math]F es la cantidad de números fofeables hasta [math]x, entonces [math]F\geq \frac{x}{4}. Notemos que hay grupos con más de un número fofeable (por ejemplo [math]1 y [math]4 están en el mismo grupo y son fofeables), entonces [math]F>\frac{x}{4}
De lo demostrado en las dos partes se tiene que si [math]F es la cantidad de números fofeables hasta [math]x, entonces [math]\frac{x}{4}<F<\frac{x}{2}.
En particular hasta [math]x=2^{2017} hay [math]2^{2015}=\frac{2^{2017}}{4}=\frac{x}{4}<F<\frac{x}{2}=\frac{2^{2017}}{2}=2^{2016}
Por lo tanto, entre los primeros [math]2^{2017} enteros positivos hay entre [math]2^{2015} y [math]2^{2016} números fofeables.
Notemos trivialmente que [math]1 es fofeable, y que [math]N es fofeable si y sólo si [math]N-p_N es fofeable.
Para ver la segunda afirmación, notemos que si [math]N es fofeable, quiere decir que al restarle repetidas veces [math]p_N obtenemos al número [math]1. Al restarle [math]p_N la primera vez, obtenemos entonces que si a [math]N-p_N le aplicamos esta operación repetidas veces, eventualmente llegaremos a [math]1, por lo que [math]N-p_N es fofeable.
Además, si [math]N no es fofeable, al aplicarle la operación suficientes veces, eventualmente llegaremos a [math]0, por lo que al aplicarle la operacíón la primera vez llegaremos a [math]N-p_N y [math]N-p_N será no fofeable.
Por cuestiones de definición, vamos a decir además que el [math]0 es no fofeable.
Lema 1: No existen dos enteros positivos consecutivos fofeables.
Demostración: Supongamos que existen. Sean entonces [math]m el menor entero positivo tal que [math]m y [math]m+1 son fofeables, notemos que el mayor primo menor o igual a [math]m es el mismo que el mayor primo menor o igual a [math]m+1, ya que sino [math]m+1 sería primo y no fofeable. Sea entonces [math]p este primo, tenemos que tanto [math]m-p como [math](m+1)-p son fofeables, lo que contradice la minimalidad de [math]m, ya que [math]m no puede ser [math]1 y para todo [math]m mayor a [math]1, [math]p_M es mayor a [math]0.
Luego, agrupando los números del [math]1 al [math]2^{2017} en parejas de enteros consecutivos, obtenemos que hay [math]2^{2016} parejas de enteros consecutivos en donde a lo sumo un entero es fofeable, por lo que existen a lo sumo [math]2^{2016} enteros positivos fofeables.
Para optimizar ahora las cota por arriba, notemos que tanto el [math]9 como el [math]10 son no fofeables ([math]9-7=2, [math]2-2=0 y [math]10-7=3, [math]3-3=0), por lo que al menos una de las [math]2^{2016} parejas de enteros consecutivos no tiene a ningún número fofeable y como mucho hay [math]2^{2016}-1 números fofeables.
Vamos a demostrar ahora que para todo [math]n mayor a [math]0, existen al menos [math]\left \lceil \frac{n+1}{4} \right \rceil números fofeables entre [math]0 y [math]n. Para ver esto, supongamos que existe [math]m tal que entre [math]0 y [math]n la proporción de números fofeables en el rango entre [math]0 y [math]n es menor a [math]\frac{1}{4} tomemos el menor de estos [math]m. Es fácil checkear a mano viendo si los primeros números son fofeables o no, que [math]m tiene que ser mayor a [math]5. Sean [math]p_1, p_2, \dots p_k entonces todos los primos mayores a [math]3 y menores a [math]m, dividamos ahora a los números entre [math]0 y [math]m en los conjuntos [math]C_0, C_1 \dots C_k, C_{k+1}, en donde [math]C_0 contiene los enteros del [math]0 al [math]3, [math]C_i los enteros del [math]p_{i-1}+1 al [math]p_i para todo [math]i entre [math]1 y [math]k, y [math]C_{k+1} contiene los enteros entre [math]p_{k+1}+1 y [math]m (es posible que este conjunto este vacío).
Notemos que como la proporción de números fofeables entre [math]0 y [math]n es menor a [math]\frac{1}{4}, la proporción de números fofeables en alguno de los [math]C_i también debe serlo. Luego, separemos en casos según cual sea el conjunto que cumple esto.
Veamos que el conjunto [math]C_0 no puede cumplir esto, ya que entre los enteros positivos [math]0, [math]1, [math]2 y [math]3, el [math]1 es fofeable.
Si el conjunto [math]C_i cumple esto, con [math]i entre [math]1 y [math]k, tenemos que (usando que [math]n es fofeable si y solo si [math]n-p_n es fofeable, y que tanto [math]0 como [math]p_i son fofeables) el conjunto de números entre [math]0 y [math]p_i - p_{i-1} - 1 tiene proporción de números fofeables menor a [math]\frac{1}{4}, lo que contradice la minimalidad de [math]m. Absurdo.
Si el conjunto [math]C_{k+1} cumple esto, tenemos que el conjunto de números entre [math]1 y [math]m-p_k tiene proporción de números fofeables menor a [math]\frac{1}{4}, por lo que añadiendo el [math]0, que no es fofeable, a este conjunto, tenemos que la proporción de números fofeables en el conjunto de números entre [math]0 y [math]m-p_k es también menor a [math]\frac{1}{4}.
Luego, tenemos en particular que entre [math]0 y [math]2^{2017} hay al menos [math]2^{2015}+1 números fofeables, y como [math]0 no es fofeable, tenemos que entre [math]1 y [math]2^{2017} hay al menos [math]2^{2015}+1 números fofeables, lo que implica lo pedido.
El [math]208 está en el grupo [math]205,206,207,208, y tenemos que [math]207 es fofeable ya que [math]207\rightarrow 207-199=8\rightarrow 8-7=1
En el grupo [math]209,210,211,212, tenemos que [math]211 es primo, por lo tanto [math]212 es fofeable
Vamos a probar que de cada 2 números consecutivos, como mucho 1 es fofeable y que para cada entero positivo [math]n, si [math]f(n) es la cantidad de enteros menores o iguales a n que son fofeables, [math]\frac{f(n)}{n+2}\geq\frac{1}{4}, para todo número no-primo y [math]\frac{f(n)}{n+1} \geq \frac{1}{4}, para [math]n primo.
Vamos a llamar "fofear un número" cuando le restamos el mayor primo menor o igual que el número. Llamamos [math]P(n) o [math]p(n) al mayor primo menor o igual que [math]n.
Consideremos la pareja (1,2). Si fofeamos el 2, obtenemos 0 y se cumple que en la pareja (1,2), como mucho un número es fofeable. Ahora asumamos que en toda pareja [math](k,k+1) hay como mucho un numero fofeable, para [math]1 \leq k < n. Ahora consideremos la pareja [math](n,n+1). Si o [math]n o [math]n+1 son primos, acabamos. Si no, digamos [math]n= N+ p(n), para cierto [math]N. Es obvio que [math]N<n, ya que [math]p(n) \geq 2. Ahora fofeamos [math]n y [math]n+1 y obtenemos [math](N,N+1). Pero como [math]N<n, por hipótesis, uno de esos dos no es fofeable, de donde o [math]n o [math]n+1 no es fofeable y esto completa la inducción.
Si ahora consideramos las parejas [math](1,2), (3,4), \ldots , (2^{2017}-1,2^{2017}), tenemos que como mucho la mitad de esos números son fofeable. Para ver que es estríctamente menos que la mitad, solo falta encontrar una pareja en que nigún número sea fofeable, como lo es [math](9,10). En fin, [math]f(2^{2017}) < \frac{2^{2017}}{2}=2^{2016}.
Ahora la parte díficil.
Primero probaremos que [math]\frac{f(n)}{n+2} es mayor o igual que [math]\frac{1}{4} para [math]n=1,4 y que [math]\frac{f(n)}{n+1}\geq \frac{1}{4} para [math]n=2,3,5.
Ahora asumamos que para todo [math]k \leq n \geq 5 se verifica que o [math]\frac{f(k)}{k+2} \geq \frac{1}{4} para [math]k no-primo y que para todo [math]k primo, [math]\frac{f(k)}{k+1} \geq \frac{1}{4}
Caso [math]n+1 primo:
Como [math]n no es primo, porque no es posible tener dos primos consecutivos (excepto el 2 y el 3), tenemos que [math]\frac{f(n+1)}{(n+1)+1}=\frac{f(n)}{n+2}\geq \frac{1}{4}, ya que tenemos que [math]\frac{f(n)}{n+2}
\geq \frac{1}{4} por hipótesis y que [math]f(n+1)=f(n) porque [math]n+1 no es fofeable, por ser primo.
Caso [math]n+1 no primo:
Sea [math]n+1=P(n+1)+N Y consideremos el rango de números del [math]1 a [math]P(n+1) y de [math]P(n+1)+1 a [math]P(n+1)+N por separados. En el primero rango, hay [math]P(n+1) números y por hipótesis [math]\frac{f(P(n+1))}{P(n+1)+1}\geq\frac{1}{4}. En los números de [math]P(n+1)+1 a [math]P(n+1)+N, hay [math]N números y si los fofeamos todos, obtenemos los números del [math]1 al [math]N, de donde hay [math]f(N) números fofeables en el rango [math]P(n+1)+1 a [math]P(n+1)+N. Pero, aún si [math]N es primo o no, [math]\frac{f(N)}{N+1}\geq \frac{1}{4}. Ahora sumamos este resultado con el otro (Es sabido que si [math]\frac{a}{b},\frac{c}{d} \geq x, pues [math]\frac{a+c}{b+d} \geq x) Se obtiene [math]\frac{f(P(n+1))+f(N)}{P(n+1)+N+2}\geq \frac{1}{4}. El numerador de esto ya vimos es [math]f(n+1), de donde se obtiene, [math]\frac{f(n+1)}{(n+1)+2}\geq \frac{1}{4}, como queríamos probar.
Ahora bien, como [math]\frac{f(n)}{n}>\frac{f(n)}{n+1}\geq\frac{1}{4}, sigue que [math]f(n)>\frac{n}{4}, específicamente, [math]2^{2015} < f(2^{2017}) < 2^{2016}, que es lo que se nos pedía.