Skip to content

Solución: K bits a uno

by en 12/05/2014

¡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 {6 \choose 3}. La fórmula general para calcular el valor es:

{a \choose b} = {{a!} \over {b! \cdot (a-b)!}}

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

{6 \choose 3} = {{6!} \over {3! \cdot (6-3)!}} = {{6!} \over {3! \cdot 3!}}=20
{8 \choose 5} = {{8!} \over {5! \cdot (8-5)!}} = {{8!} \over {5! \cdot 3!}}=56
{20 \choose 7} = {{20!} \over {7! \cdot (20-7)!}} = {{20!} \over {7! \cdot 13!}}=77.520

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!

Anuncios

From → Soluciones

2 comentarios
  1. ¿Cómo se podrían guardar los datos en una tabla?

    • Hola Mario,

      Si estás pensando en programarlo, la idea es tener un array bidimensional, donde uno de los índices será el número total de bits, y otro el número total de bits a uno. Fíjate que aunque sea un array bidimensional, sólo rellenarás la mitad (un “triángulo”) dado que la respuesta es inmediata si hay menos bits en el número que bits a 1 (es decir, si nos preguntan ¿cuántos números diferentes hay de 4 bits que tengan 10 bits a 1?).
      Si no estás pensando en programarlo (o si quieres hacer pruebas antes) puedes incluso rellenar la tabla en una hoja de cálculo, y debería quedarte algo así:

      Nº de bits totales
      ↓ A uno 1 2 3 4 5
      0 1 1 1 1 1
      1 1 2 3 4 5
      2 1 3 6 10
      3 1 4 14
      4 1 5

      Lo interesante es que para rellenar las celdas que no son “casos base” (las que no son “1”), se utilizan dos de las que tiene al lado a la izquierda.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: