Un Problema de la Final de una Olimpiada Española, Resuelto por Gp20 Opciones

[Rurouni Kenshin]

Problema:

Sea la función f:N ----->N, que cumple para s,n naturales las siguientes condiciones:

a) f(1) = f(2^s) = 1
b) si n < 2^s; entonces f(2^s + n) = f(n) +1

i) Calcular el valor máximo de n cuando es menor o igual a 2001
ii) hallar el menor n tal que f(n) = 2001

Solución: i) Primero que todo, fijémonos que este problema tiene relación con el sistema binario (para el que no sepa lo que es, es un sistema de numeración equivalente al decimal, con la diferencia que cada posición representa una potencia más de 2; de esta forma el número 8 = 1*2^3 + 0*2^2 + 0*2^1 + 0*2^0 se escribe 1000; y el 524 se escribe 1000001100). Luego, fijémonos que la función de cualquier número es equivalente a la cantidad de unos que hay en su notación binaria (así tenemos que f(8 ) = 1 y f(524) = 3).

Entonces, para maximizar nuestra función, debemos encontrar el número que tenga la mayor cantidad de unos en su notación binaria y que a la vez sea menor que 2001. De esta forma llegamos a que el número buscado es 1023 (que en notación binaria es igual a 111111111). Luego, f(1023) = 10.

ii) Para resolver esto, sabemos que el menor número en su notación binaria que satisaface la condición es aquel que tiene 2001 unos de forma continuada. Luego, este número es:

screen.width*0.6) {this.resized=true; this.width=screen.width*0.4; this.alt='Pincha Aqui para ver esta imagen en su tamaño original';}" onmouseover="if(this.resized) this.style.cursor='hand';" onclick="if(this.resized) {window.open('http://img152.imageshack.us/img152/6272/suma0ug.png');}" />
(fácilmente demostrable por inducción).


Resuelto por Gp20