domingo, 18 de enero de 2009

Números autodefinidos

Enunciado

Lo más difícil de este problema es explicar cómo damos con los números que son autodefinidos, y por qué estamos seguros de que no existen más.

Supongamos que empieza uno de esos números por 1. Eso quiere decir que no tiene más que un cero. El siguiente número no puede ser un cero, ya que hay al menos un 1 (el primero). Por lo menos, debe ser un 2, lo que indica que debe haber otro uno más. El tercer número podría ser un 1, ya que hay un 2, y después podría haber un cero y no más números. Ese sería el 1210.

Observa que en estas condiciones, el tercer número no puede ser un 2, ya que debería haber entonces otro 1. Si ese 1 estuviese en el 3, por ejemplo, habría al menos un 3, y sería en quinta posición o superior, lo que indica que habría tres de esos números, que a su vez obligaría a que hubiese muchos más de diez números. Esta especie de reacción en cadena se produce en muchos casos, y me referiré a ella en otras ocasiones.

Empezando con un 1 y un 3, obligas a que haya al menos dos unos más, lo que desata de nuevo una reacción en cadena. De esta manera, no puede empezar con un 1 y otro número mayor.

Si empezamos con un 2, podemos poner un 0 detrás, pero después debe haber en ese caso un 2 (no podemos poner un 1, ni números mayores, por la reacción en cadena), y con otro cero podemos acabar el número. Se trata del 2020.

Con un 2 también, podemos poner después un 1, y también tenemos que poner un 2 en tercer lugar, por las mismas razones. Finalizaremos con los dos ceros que necesitamos, obteniendo el 21200.

Ya no podemos obtener otro número empezando con un 2, porque todos desatan esa situación.

Empezando con un 3, eso obliga a que haya un número distinto de 0 en cuarto lugar. Si este número es un 1, en segundo lugar no puede haber otro 1, pero poner más de un 2 provoca una reacción en cadena, de forma que debe ser un 2. Así obtenemos el 3211000. Cualquier otro número provoca la temida reacción, de forma que no hay más que empiecen por 3.

De manera similar, empezando por 4 obtenemos el 42101000 únicamente, empezando por 5 el 521001000 y empezando por 6 el 6210001000. Si tratamos de empezar por un número mayor obtenemos más de 10 cifras, ya que a los 7 ceros habría que añadir dos unos, un dos y el número en sí mismo.