Números de Aure

Update: Los números de Aure también se llaman A131689
Update: Los números de Aure aparecen en el último libro de Paenza, Cómo, esto también es matemática?. Mirá la página 224.

La oficina de Agustina tiene en la puerta un teclado donde hay que ingresar una clave para poder entrar. Pensando en esto (y otras cosas donde hay que ingresar claves numéricas, como los cajeros automáticos) se me ocurrió el siguiente problema:

Hay que elegir un número de 6 dígitos (en base 10, con posibles 0s
adelante) como clave para ingresar en un pinpad para ingresar a una "habitación segura".
Pero un atacante tiene la posibilidad de leer huellas digitales y por lo tanto sabe que teclas apretaste pero no en que orden ni con que repetición (o sea, no puede distinguir las claves "111112" y "122222").

¿Cómo se debe elegir la clave de tal manera que el atacante tenga la mayor dificultad posible para adivinarla?

Este problema lo postié en los news internos del laburo y Charles, un compañero de laburo, se mandó una explicación buenísima en dos mensajes. Abajo pongo textuales los mails:

Primer mail:

Con 6 digitos hay 6! = 720 posibilidades.

Con 5 digitos, una forma de contar es así: supongamos que los digitos son 1,2,3,4,5 y que el 5 está repetido dos veces, lo contamos como 1,2,3,4,5a,5b y despues dividimos por las permutaciones de 5a y 5b. Eso da 6! / 2!, y como hay 5 posibilidades para el digito repetido el
resultado es:
6! / 2! * 5 = 1800 posibilidades.

Con 4 digitos, puede haber un digito repetido tres veces, por ejemplo 1,2,3,4a,4b,4c
Posibilidades 6! / 3! * 4 = 480
Puede haber dos digitos repetidos dos veces cada uno, por ejemplo 1,2,3a,3b,4a,4b
Posibilidades 6! / (2! * 2!) * Combinatorio(4,2) = 1080 El Combinatorio(4,2) es la cantidad de formas de elegir 2 elementos entre 4, es 4! / (2!*2!) = 6
En total: 1560 posibilidades con 4 digitos

Con 3 digitos, las estructuras son 1,2,3a,3b,3c,3d da 6! / 4! * 3 = 90
1,2a,2b,3a,3b,3c da 6! / (3! * 2!) * (3*2) = 360 1a,1b,2a,2b,3a,3b da 6! / (2! * 2! * 2!) = 90
Total: 540 posibilidades con 3 digitos

Con 2 digitos, las estructuras son 1,2a,2b,2c,2d,2e da 6! / 5! * 2 = 12
1a,1b,2a,2b,2c,2d da 6! / (4! * 2!) * 2 = 30 1a,1b,1c,2a,2b,2c da 6! / (3! * 3!) = 20
Total: 62 posibilidades con 2 digitos

Con 1 digito, hay 6! / 6! = 1 posibilidad (claro ;-)

Conclusión: hay que usar 5 digitos!

Segundo mail:

Me quedé pensando en tratar de sacar una relación de recurrencia...
Llamemos "número de Aure" A(k,n) a la cantidad de claves de n digitos que usen exactamente k digitos distintos. Por ejemplo 1,2,2,3,3 es una clave de 5 digitos que usa 3 digitos distintos.

Yo lo pienso como cantidad de claves con k digitos distintos en n lugares.

Los casos faciles:
A(1,n) = 1 para todo n
A(k,n) = 0 si k > n

Ahora la recurrencia: si tengo una clave con n-1 lugares, hay dos opciones: ya se usaban los k digitos en los n-1 lugares, o solo se usaban k-1 digitos distintos y agregué el k-ésimo digito en el ultimo lugar.

Si ya se usaban k digitos en n-1 lugares, tengo k posibilidades para el n-esimo lugar (repetir uno de los k digitos).

Si se usaban exactamente k-1 digitos en n-1 lugares, entonces estoy agregando un digito nuevo en el n-ésimo lugar. Tengo k opciones para el digito nuevo.

Luego A(k,n) = k * A(k,n-1) + k * A(k-1,n-1)

A(k,n) = k * ( A(k,n-1) + A(k-1,n-1) )

Es como un triangulo de Pascal con un multiplicador k.

Las primeras filas dan:

       k=1     k=2     k=3     k=4     k=5     k=6
n=1     1       0
n=2     1       2       0
n=3     1       6       6       0
n=4     1       14      36      24      0
n=5     1       30      150     240     120     0
n=6     1       62      540     1560    1800    720     0

Sorprendentemente, volvió a dar los mismos números ;-)

La problema de Aure se puede reformular como "qué k maximiza A(k,6)?"

En fin, el problema parece que dio para mucho :D, y tengo mis propios números con una serie que tiene un sentido y una "aplicación".

Happy hacking,
Aureliano.