Solución: K bits a uno

¡Hola!

Llega el momento de dar la solución a nuestro acertijo de la semana. En él os preguntábamos cuántos números de 6 bits tienen exactamente 3 bits a 1, y cuántos de 8 tienen 5. Gualterio nos dió sus respuestas: 20 y 56 respectivamente. Y no sólo acertó, sino que se atrevió a dar respuesta a una pregunta más, la cantidad de números de 20 bits con 7 bits a 1. ¡Siempre que da su respuesta nos hace a nosotros otra pregunta! 🙂 Efectivamente, en ese caso 77.520 números diferentes con exactamente 7 bits a 1. Pero, ¿cómo se resuelve sin tener que escribir todas las configuraciones?

Vamos a contaros dos posibles formas de afrontar el problema. El primero es el modo «matemático» que es cómodo para ser resuelto a mano; el segundo es el «de programador» que permite solucionar el acertijo sin necesidad de saberse las matemáticas que hay por debajo. Como siempre, nos gusta que nuestros acertijos puedan ser resueltos a mano, de forma que empezaremos con el primero.

La pregunta entra dentro del campo de las matemáticas conocida como combinatoria, que estudia la «enumeración de configuraciones que satisfacen ciertas condiciones establecidas». Da respuestas a preguntas como «¿cuántas posibles quinielas se pueden hacer?» o «¿de cuántas formas se pueden sentar un grupo de personas alrededor de una mesa?».

En el caso que nos ocupa, la pregunta es la cantidad de números de 6 bits que tienen exactamente 3 bits a 1. Podemos ver este problema como que tenemos «6 objetos» (el bit a 1 en la primera posición del número, el bit a 1 en la segunda posición del número, etcétera), y queremos saber el número de formas de coger 3 de esos objetos, sin importar el orden. Es decir, la opción de decir «voy a poner a 1 el bit 2, el 4 y el 5» es la misma que la opción «voy a poner a 1 el bit 5, el 4 y el 2», porque el resultado será el mismo. Dicho de otro modo, ¿de cuántas formas posibles podemos escoger 3 objetos de un total de 6, sin importar el orden?

A esto los matemáticos lo conocen como combinaciones y se escribe como . La fórmula general para calcular el valor es:

Una vez que sabemos esto, es fácil averiguar las respuestas a las preguntas:

Pero… ¡ten cuidado! Aunque este mecanismo es suficiente para resolver nuestras preguntas, si intentas usarlo para resolver el problema original en ¡Acepta el reto! tendrás problemas. Los factoriales crecen muy deprisa y tendrás desbordamientos. Y hacer el módulo 1.000.000.007 que pide el ejercicio no es tan fácil a la hora de dividir, y te tocará buscar los inversos en ese módulo… y eso ¡se complica! De modo que aunque las matemáticas nos han venido bien para resolver el acertijo a mano, para usarlas en la solución programada tendríamos que complicarlas un poco más y es preferible ver la solución para programadores…

En concreto, revisemos la pregunta. ¿Cuántos números hay de 6 bits con 3 bits a 1? Podemos resolverlo recursivamente (con una recurrencia) si en cada paso establecemos el valor de un bit y dejamos la responsabilidad del resto en la llamada recurvisa. En concreto, la respuesta a nuestra pregunta es:

• La cantidad de números de 5 bits que tengan 3 bits a uno (en el bit actual hemos escrito un 0), más
• La cantidad de números de 5 bits que tengan 2 bits a uno (en el bit actual hemos escrito un 1).

Programar esto no es difícil; falta añadir los casos base y el módulo 1.000.000.007 que nos pide el problema en Acepta el reto. La única pega es que es muy lento (por la recursión doble) de modo que lo mejor es guardarlo en una tabla y… ¡lo tendréis resuelto!

Intentadlo, que no es muy difícil, enviad vuestra solución aquí y nos contáis cómo os fue.

¡Hasta el próximo!