Problema 2 de la fase nacional de la 56 Olimpiada Matemática Española (2020)
Se dirige a una edad de: 16-17 años

Consideramos la sucesión de números enteros f(n), con n mayor o igual que 1, definida por las siguientes condiciones:

f(1) = 1.

Si n es par, f(n) = f(n/2).

Si n es impar y f(n – 1) es impar, entonces f(n) = f(n – 1) – 1.

Si n es impar y f(n – 1) es par, entonces f(n) = f(n – 1) + 1.

a) Calcula f(2²⁰²⁰ – 1).

b) Demuestra que la sucesión no es periódica, es decir, que no existen enteros positivos t y n₀ que cumplan que si n es mayor que n₀, entonces f(n + t) = f(n).

Solución:

Este es un problema en el que es muy importante generalizar con rigor, para lo cual vamos a estudiar los primeros elementos de la sucesión.

También es útil haber tenido un contacto previo con los números binarios, ya que la importancia de la paridad en la definición de la sucesión sugiere que van a tener una gran importancia.

Los primeros elementos formarían la cadena siguiente:

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, …

Aparentemente no hay ninguna regularidad, pero si los relacionamos con su expresión binaria, podemos observar un hecho curioso.

Voy a construir una sucesión muy parecida, a la que llamaré la sucesión g, pero en lugar de restar 1 a f(n – 1), le voy a sumar 1.

Y voy a representar cada término de la sucesión junto a su posición, y la representación en números binarios de esa posición.

1 – 1 – 1
2 – 10 – 1 (como 1)
3 – 11 – 2 (2 + 1)
4 – 100 – 1 (como 2)
5 – 101 – 2 (1 + 1)
6 – 110 – 2 (como el 3)
7 – 111 – 3 (2 + 1)
8 – 1000 – 1 (como el 4)
9 – 1001 – 2 (1 + 2)
10 – 1010 – 1 (como el 5)

Es evidente que la sucesión se parece mucho, sólo que en este caso, a diferencia de f, g tiene valores mayores. Está claro que f no crece, porque la única manera de aumentar es sumando a un valor anterior, pero si ese valor es 1, en f restamos, y volvemos a 0.

Y en f tampoco bajamos de cero, porque si el valor es 0, es par, luego sumamos.

Básicamente, la f es como la g en el sentido de que si g es par, f vale 0, y si g es impar, f vale 1. La sucesión f es la llamada paridad de g.

Pues bien, si os dais cuenta, g representa el número de cifras 1 en la representación binaria.

Claramente, si n es par, su cantidad de cifras 1 es la misma que la de n/2, ya que multiplicar por 2 equivale a añadir un 0 como última cifra.

Y si es impar, tiene un 1 más que el número anterior, ya que un “0” del final del número lo cambiamos por un “1”.

Lo que quiero decir es que f sólo puede valer 0 o 1, y consiste en que vale 0 si la cantidad de 1 de la representación en binario de un número tiene una cantidad par de 1, y 1 si la representación en binario de un número tiene una cantidad impar de 1 entonces vale 1.

Podemos demostrarlo con los argumentos dados antes, por recursividad, tal y como está bien definida la función.

Observando esto, está claro que f(2²⁰²⁰ – 1) vale 0, ya que es un número que está formado por 2020 unos.

Una forma directa de demostrarlo puede ser probando por inducción que 2ⁿ – 1 vale 0 si n es par y 1 si n es impar. Como siempre es impar, se basa en el número anterior, que será 2ⁿ – 2 = 2(2^{n – 1} – 1), que por hipótesis de inducción ya tiene la propiedad buscada.

Ver que no es periódica es bastante más complicado. Si hemos dado con la analogía de que el valor de f depende del número de cifras en formato binario, podemos observar que cuando pasamos de una potencia a otra de 2, vuelve a repetir la misma secuencia, pero invertida.

Por ejemplo, 1, 1, 0, 1, 0, 0, 1, 1 son los 8 primeros, y los de 9 a 15 son 0, 0, 1, 0, 1, 1, 0. Sin embargo, las potencias de 2, tanto 8 como 16, siempre valen 1. Con lo que las secuencias se van haciendo cada vez más largas.

Para probar que no es periódica (como casi siempre que queremos ver que algo no sucede) lo mejor suele ser proceder por reducción al absurdo, es decir, suponer que sí lo es y llegar a una contradicción.

Supongamos que sí es periódica, por lo que existe un valor n₀ y un valor t, como dice el enunciado, de forma que f(n + t) = f(n) para cada n mayor que n₀.

Para llegar a un absurdo sin mucha dificultad, podemos pensar en los dígitos en binario de t. Necesitamos tomar una n que podamos manejar con claridad. Puesto que tenemos que negar esta propiedad, trataremos de llegar a una situación que no pueda darse esta igualdad.

Imaginemos que t es un número binario, como por ejemplo 1 100 111. En este caso, tiene 5 cifras 1, con lo que f(t) = 1. Pero ese no significa mucho para nosotros. Sin embargo, si tomamos el valor 1 000 000, sabemos que al sumarlo a t obtendremos 10 100 111, es decir, obtendremos la misma cantidad de unos, es decir, que f(n + t) = 1. Y si tomamos el valor 11 000 000, al sumarlo obtendremos el valor para n + t (en binario) de 100 100 111, es decir, que volveremos a tener el mismo valor para la cantidad de cifras 1 que t. La diferencia entre 1 000 000 y 11 000 000 es que mientras que f en el primero da 1, f en el segundo da 0, y en ambos casos f(n + t) debería ser f(n), luego es imposible.

Ahora bien, ¿cómo nos aseguramos que eso no pasa hasta un cierto valor suficientemente grande?, pues tomamos el valor n₀ y usamos una potencia suficientemente grande. Imagina que nos dicen que n₀ fuese 101 110 001. Pues usamos como candidatos a n los números 1 001 000 000 (cuyo valor de f es 0) y 1 011 000 000, que tiene un valor de f de 1. en ambos casos, al sumar t nos da la misma cantidad de 1 en binario (1 más que t), y por lo tanto el valor de f(n + t) debería ser el mismo, lo que es imposible.

¿Cómo se puede hacer de manera formal?

Habría que demostrar que si 2^p es mayor que un cierto valor x, f(2^p + x) = 1 – f(x). Es fácil de ver si aplicamos la hipótesis de inducción y desglosamos los casos en que x es par o impar. Eso quiere decir que si sumamos potencias suficientemente grandes a un valor, f cambia su valor al opuesto (de 1 a 0 y de 0 a 1).

Además, si tenemos el valor p que cumple que 2^p <= t < 2^{p + 1} (es decir, la última cifra binaria de p), se tiene que f(t) = f(2^p + t). Probar esto es más complicado, salvo que se conozca muy bien el sistema binario.

Tratemos de probarlo por inducción sobre t. Está claro que para t = 1 se cumple (el valor correspondiente de p es 0). Supongamos que es cierto hasta un cierto valor t – 1 y tratemos de ver que es cierto para t. Habrá que diferenciar dos casos, aquel en el que tienen el mismo p y el que tienen diferente p. Si tienen el mismo p, puesto que se define f por recursión es muy sencillo apoyarnos en la hipótesis de inducción. Si no tienen el mismo valor de p, es porque coincide que t es exactamente 2^{p + 1} , y entonces tenemos que f(t) = 1, y f(2^{p + 1} + t) = f(2^{p + 2}) = 1.

Una vez que hemos averiguado estas propiedades con sumas de potencias grandes de 2 y t, elegimos un valor de p de forma que 2^p <= t < 2^{p + 1} y un valor de q que al menos sea tres unidades mayor que p y que 2^q sea también mayor que n₀. A partir de ahí y las propiedades que hemos trabajado, concluiremos que f(2^q + 2^p) es diferente de f(2^q + 2^{p + 1} + 2^p), pero que f(2^q + 2^p + t) = f(2^q + 2^{p + 1} + 2^p + t), por la elección de p, y los dos posibles candidatos para n son mayores que n₀.

Como veis, no es un trabajo sencillo, y eso sin contar la presión de tiempo que supone el concurso (aproximadamente una hora por problema).