Skip to content

Solución: escribiendo la descomposición en factores primos

by

Hola!

Tras una semana con el acertijo a la espera de vuestras soluciones, llega la hora de desvelar las respuestas correctas y cómo las hemos conseguido nosotros. En esta ocasión os contábamos que todos los números tienen una única descomposición en factores primos, pero que recolocando los factores el número de formas de escribir cada descomposición varía. Por ejemplo:

6 = 2 × 3 = 3 × 2
12 = 2 × 2 × 3 = 2 × 3 × 2 = 3 × 2 × 2

lo que indica que la descomposición de 6 se puede escribir de 2 formas, y la de 12 de 3. Os preguntábamos por los números más pequeños cuya descomposición en factores primos puede escribirse, exactamente, de 6, 10 y 45 formas. En los comentarios, Ferrán nos dio su solución para 10 y 45 formas y ¡era correcta! incluso aunque nuestro planteamiento del acertijo no era del todo claro y tenía dudas. Os retamos con una pregunta más, 72 formas, y Gualterio la contestó también correctamente. ¡Enhorabuena a ambos! Curiosamente, nadie contestó a la primera pregunta, la de 6 formas…

Veamos cómo resolvimos nosotros el acertijo. Si vuestra solución es diferente, ¡no dudéis en contárnosla!

El primer paso es analizar por qué la descomposición en factores primos del 6 se puede escribir de 2 formas y, después, por qué la de 12 se puede escribir de 3. Para eso, nos apoyamos en la rama de las matemáticas denominada combinatoria que ya ha aparecido en algún otro acertijo. En el caso que nos ocupa, si miramos la descomposición del número 6 vemos que tenemos dos números primos distintos (el 2 y el 3) y queremos saber de cuántas formas diferentes podemos colocarlos. Dicho de otro modo, ¿de cuántas formas puedo colocar n elementos? Esa pregunta la responden las permutaciones. No es muy difícil llegar a la fórmula matemática de… n! o, “factorial de n” que es la multiplicación de todos los números entre 1 y n.

El caso del 12 es más complicado, porque hay factores repetidos. Debido a ello, el concepto de permutación no nos sirve directamente, y hay que complicarlo un poco más con las permutaciones con repetición. De nuevo, volviendo a las matemáticas, si tenemos n elementos, donde hay a iguales entre sí, otros b iguales entre sí, etcétera (con todos ellos sumando n) entonces el número de formas de colocarlos (o sea, las permutaciones con repetición) son:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots}

Con esto, analizamos lo que ocurre con el número 12. Su descomposición en factores primos tiene tres números (2 × 2 × 3), por lo que n es 3. Además, hay dos que se repiten, por lo que a=2 y b=1. Por tanto:

PR^{2,1}_3= {3! \over 2!\cdot 1! \cdot \ldots} = {6 \over 2} = 3

Esto significa que las matemáticas nos dicen que la descomposición de 12 la podemos poner de 3 formas diferentes, tal y como vimos escribiendo a mano todas las opciones.

Vamos ahora con las preguntas. La primera era ¿cuál es el número más pequeño cuya descomposición en factores primos se puede escribir de 6 formas? Es decir, estamos buscando los valores de n, a, b, … tales que:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots} = 6

Esto no tiene una solución sencilla, por lo que nos dedicaremos a tantear. Pero en lugar de ponernos a hacerlo ciegamente, empezaremos descomponiendo en factores primos el número 6, para que su “radiografía” nos dé una pista de con qué números empezar a probar. En concreto, sabemos que 6 = 2 × 3.

Además, nos vamos a apoyar en la descomposición en factores de los factoriales. Por ejemplo:

2! = 2
3! = 3 × 2
4! = 4 × 3 × 2 = 23 × 3
4! = 5 × 4 × 3 × 2 = 23 × 3 × 5

Si lo hacemos con más números, terminaremos sacando la siguiente tabla, donde mostramos el número de veces que aparece cada número primo en los factores de cada factorial (hasta 10):

2 3 5 7
2! 1
3! 1 1
4! 3 1
5! 3 1 1
6! 4 2 1
7! 4 2 1 1
8! 7 2 1 1
9! 7 4 1 1
10! 8 4 2 1

La tabla indica que, por ejemplo, 6! = 24 × 32 × 51

Mirando esta tabla y lo que queremos conseguir:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots} = 6 = 2 \cdot 3

es fácil llegar a la conclusión de que:

6 = 2 \cdot 3 = {3! \over 1! \cdot 1! \cdot 1!}

De aquí, podemos deducir que el número más pequeño cuya descomposición tiene 6 formas de escribirse tiene tres factores diferentes (por los tres unos en el denominador). Para que el número sea lo más pequeño posible, cogemos los factores (primos) más pequeños posibles y por tanto la respuesta es:

21 × 31 × 51 = 30

La segunda pregunta era el número más pequeño cuya descomposición se puede escribir de 10 formas. Sabemos que:

10 = 2 × 5

y queremos escribirlo de la forma:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots} = 10 = 2 \cdot 5

Éste es un poco más complicado, de modo que vamos más despacio. Para el n! del numerador necesitamos encontrar un factorial que incluya en su descomposición un 2 y un 5. Para eso, recurrimos a nuestra tabla y vemos que 5! es 23 × 3 × 5. Por comodidad, representaremos sólo los exponentes, por lo que diremos que 5! es (3, 1, 1). Por su parte, 10 lo representaremos como (1, 0, 1) pues su descomposición es 21×30×51.

Fijaos que en este caso el factorial de 5 incluye más factores que 10, y hay que “quitarlos” dividiendo por a!, b!, etcétera. En concreto, si “restamos” la representación del 5! (3, 1, 1) y del 10 (1, 0, 1) nos queda (2, 1). Tenemos que conseguir esa descomposición usando factoriales para ponerlos en el denominador. Mirando en la tabla, es fácil ver que eso se consigue con 3! y con 2! de modo que ¡ya lo tenemos!:

PR^{3,2}_5= {5! \over 3!\cdot 2!} = 10 = 2 \cdot 5

Es importante asegurarse de que los números del denominador suman lo mismo que el numerador, es decir que n = a + b + …. En este caso esto se cumple. Lo único que falta es sacar el número de la respuesta. Cualquier número que tenga dos factores primos diferentes, uno elevado al cubo (por el 3!) y otro al cuadrado (por el 2!) tendrá exactamente 10 formas de escribir su descomposición. Como queremos el más pequeño, usamos los primos más bajos, y eso nos da:

23 × 32 = 72

tal y como nos dijo Ferrán en los comentarios 🙂

Vamos con el último, el 45 = 3 × 3 × 5. Igual que antes, ésto lo representamos como (0, 2, 1). Fíjate que empezamos con un 0 porque el 2 (el primer número primo) no aparece en la descomposición. Ahora necesitamos buscar en nuestra tabla de la descomposición de factoriales el primero que incluya dos treses y un cinco. Ese resulta ser 6! (4, 2 1). Ahora necesitamos buscar una forma de “quitar” los cuatro doses y para eso la única opción es poner en el denominador cuatro 2!:

PR^{2,2,2,2}_6= {6! \over 2!\cdot 2! \cdot 2! \cdot 2!} = 45

Pero… ¡¡cuidado!! Esta solución no sirve, porque la suma de los denominadores (2+2+2+2) es mayor que el numerador (6) y por tanto no es una fórmula válida para las permutaciones sin repetición. Por tanto hay que probar con un número mayor en el numerador. El problema es que al subir a 7! nos aparece un primo más en la lista que tendremos que quitar, dejando de todos modos los dos treses y el cinco de la descomposición del 45. Analizando la tabla y haciendo pruebas mentalmente, veréis que la única opción válida es:

PR^{8,2}_{10} = {10! \over 8!\cdot 2!} = 45

El número que estamos buscando, por tanto, es 28 × 32 que es 2304, como también nos dijo Ferrán.

Si utilizáis la misma técnica, veréis que la última pregunta que os hacíamos en los comentarios, 72, tiene como respuesta 1920, tal y como nos dijo Gualterio.

Tened en cuenta que nos hemos tomado algunas licencias con las respuestas, porque las preguntas que os hicimos estaban escogidas con cuidado. En realidad en ocasiones no es suficiente con encontrar la primera forma de escribir el número original, sino que es necesario seguir subiendo. Por ejemplo:

720 = {6! \over 1! \cdot 1! \cdot 1! \cdot 1! \cdot 1! \cdot 1!} = {10! \over 7! \cdot 1! \cdot 1! \cdot 1!}

Por tanto, cualquier número con 6 factores diferentes tendrá 720 formas de escribir su descomposición, y, al mismo tiempo, cualquier número con 10 factores de los cuales 7 son el mismo (y los demás son distintos) también. Resulta que con la primera configuración (6 diferentes) el número más pequeño es el 30.030, pero con la segunda (10 factores, 7 de ellos iguales) es el 13.440, que es más pequeño y por tanto preferible. En ninguna de nuestras preguntas ocurre eso (aunque todos se pueden escribir de más formas usando numeradores mayores). No obstante, que pueda ocurrir hace más difícil programar una solución. Pero si te atreves, siempre podrás probarla aquí 🙂

Este ha quedado muy matemático… en el próximo intentaremos compensarlo 🙂

Chao!

Escribiendo la descomposición en factores primos

by

¡Hola!

Vamos con un nuevo acertijo. Esta vez nos vamos a atrever con un acertijo un poquito más complicado que los demás, porque requiere dar varios “pasos mentales” para llegar a la forma de resolverlo. Además, en contra de lo que suele ocurrir, conseguir la solución con la ayuda de un ordenador resulta ser más difícil que hacerlo a mano… de modo que cerrar vuestro editor de código favorito, coged un lápiz y un papel y… ¡manos a la obra!

El planteamiento del acertijo es bastante simple. Es bien sabido que cualquier entero positivo se puede representar de forma única como una multiplicación de números primos. Aunque no es importante para nuestro acertijo, es lo que los matemáticos llaman el teorema fundamental de la aritmética.

Por ejemplo:

6 = 2 × 3
12 = 2 × 2 × 3

Aunque, efectivamente, esta descomposición en factores primos es única, en realidad la mayoría de las veces puede escribirse de más de una forma. Por ejemplo:

6 = 2 × 3 = 3 × 2
12 = 2 × 2 × 3 = 2 × 3 × 2 = 3 × 2 × 2

Vemos que la descomposición del 6 puede escribirse de dos formas, y la del 12 de 3. Además, no hay ningún número menor que 6 cuya descomposición se pueda escribir de 2 formas, ni ninguno menor que 12 que se pueda escribir de 3.

¿Cuál es el número más pequeño cuya descomposición en factores primos puede escribirse de 6 formas? ¿Y de 10? Y… ya que nos ponemos… ¿de 45?

Como siempre, si das con la solución y la programas, puedes probarla aquí. Aunque te recordamos que, en esta ocasión, es más fácil resolverlo a mano (después de pensar un rato) que con un ordenador 🙂

¡Hasta el domingo!

Solución: salvemos al lince ibérico

by

Hola!

Vamos, un domingo más, con la respuesta del acertijo de la semana. En él, os hablábamos de una carretera que cruza el territorio del lince ibérico, en peligro de extinción. Para evitar atropellos, se pusieron vallas en varios tramos. Sin embargo, los linces seguían cruzando la carretera por los tramos no vallados de modo que se ha decidido hacer pequeños túneles o “pasos de fauna”. Se sabe que uno de estos túneles cubre tres tramos, es decir se estima que un lince no cruzará una carretera por la superficie si hay un paso subterráneo en el tramo en el que está o en alguno de los tramos adyacentes. Las preguntas que os hacíamos era cuál es el mínimo número de túneles que hay que hacer para evitar atropellos en diferentes configuraciones de carretera.

Este acertijo surge de uno de los problemas que se pusieron en los regionales de Madrid y Reus de ProgramaMe, y está publicado en ¡Acepta el reto!. Aunque nadie ha puesto su solución en los comentarios, ha habido varias personas que han resuelto el problema en la última semana, de modo que ¡enhorabuena a todos ellos! La próxima vez no seáis tan tímidos, y contarnos vuestra solución aquí 🙂

Vamos con la nuestra. La primera pregunta que os hacíamos era relativa a una carretera con la configuración .... que significa que tiene cuatro tramos, y ninguna valla. Dado que cada túnel cubre tres tramos, es imprescindible hacer dos túneles. Hay varias posiciones válidas para ellos (por ejemplo, si los marcamos con una t podríamos hacerlo t..t, t.t., .tt. o .t.t), pero es imposible evitar el cruce en todos los tramos con un único túnel.

La siguiente pregunta era ..X...X, donde una X representa una valla. En este caso necesitamos un túnel para el primer bloque sin vallas, y un segundo túnel para el segundo. Una configuración podría ser t.X.t.X. Observa que todos los tramos tienen o bien un túnel o valla, o un túnel adyacente.

La última pregunta era un poco más larga, X.XXX....X.X.X. Para cubrir el primer tramo sin valla necesitamos un túnel. La parte más interesante de esta pregunta es darse cuenta de que podemos poner túnel debajo de vallas lo que en este caso nos ahorrará túneles. En concreto, basta con 4 túneles; aunque hay varias formas de conseguirlo, una sería XtXXX.t..T.XtX donde T representa un tramo con túnel y valla.

Todas estas respuestas se pueden deducir con relativa facilidad gracias al sentido común, el problema es cómo programarlo 🙂 Para eso, basta con ir colocando túneles al ir recorriendo los tramos de carretera. En concreto, cuando nos planteamos qué hacer al llegar al tramo i asumiremos que todos los tramos anteriores están ya resueltos (y los linces no cruzarán la carretera por ellos). Si el tramo i tiene valla, entonces no hay nada de lo que preocuparse y pasamos al siguiente. Si no la tiene, entonces colocaremos un túnel en el tramo siguiente (es decir en i+1). Ese túnel cubrirá al tramo actual y a los dos siguientes, a si es que, independientemente de si esos dos tienen valla o no, nos los saltamos sin preocuparnos de ellos, y seguimos buscando. Fíjate que colocar el túnel en el tramo siguiente hace que se aproveche lo más posible. Si lo colocáramos en la posición i (la actual), el túnel estaría cubriendo también el tramo anterior, i-1, que, hemos dicho, estamos suponiendo que ya no será cruzado por ningún lince por nuestros túneles anteriores. Por tanto desaprovecharíamos un poco nuestro túnel recién puesto y la solución podría no ser la óptima.

Surge la pregunta de qué pasa al final de la carretera. Si tenemos una carretera XXX. en nuestra simulación colocaríamos un túnel más allá del final. En realidad la posición exacta de los túneles no nos la preguntan, sólo el número. Lo importante es que aquí necesitamos un único túnel, y eso es justo lo que nuestro algoritmo contestaría 🙂

Esta solución pertenece a la familia de los algoritmos voraces, que ya son viejos conocidos nuestros (sin ir más lejos, usamos uno en el acertijo anterior). En ellos, tomamos una decisión “local” (colocar o no un túnel) sin preocuparnos del problema completo, sólo de una pequeña parte (el tramo actual, no la configuración de toda la carretera). Además, tampoco nos replanteamos en ningún momento las decisiones tomadas por si resultaron no ser una buena idea. Aunque no siempre dan la solución óptima, en el caso del acertijo que nos ocupa sí lo hace, y de una manera muy sencilla de programar por lo que ¡nos lo quedamos!

Como siempre, si quieres programar tu solución y probarla, puedes hacerlo aquí.

¡Hasta el próximo!

Salvemos al lince ibérico

by

Hola!

Vamos con el último acertijo antes de la final nacional de ProgramaMe. Esta vez está sacado de uno de los problemas de los regionales de Madrid y Reus. ¡Si alguno de los finalistas nos lee, así le damos la oportunidad de practicar!

El lince ibérico es una especie en peligro de extinción, por lo que se intenta que la actividad humana afecte a su hábitat lo menos posible. Sin embargo, una carretera cruza su territorio. Para evitar atropellos de linces, se pusieron vallas en algunos tramos que impedían que las cruzaran. Pero el resto de tramos siguen al descubierto y de vez en cuando aparece algún animal muerto por atropello.

Ahora se está planteando la posibilidad de hacer túneles por debajo de la carretera para que los linces crucen sin riesgo. Los ecologistas creen que un túnel en un tramo de carretera será usado por los linces que quieran cruzar en ese tramo y en los dos adyacentes. Así, por ejemplo, si tenemos una carretera con tres tramos sin valla, bastará con hacer un túnel en el tramo central para evitar más atropellos. Por su parte, en la siguiente carretera, donde ‘X‘ indica que ese tramo tiene una valla y ‘.‘ indica que no la tiene:

...X.

necesitaremos hacer dos túneles, uno en el segundo tramo y otro en el último. O en:

XXX.X.

es suficiente hacer un túnel debajo de la última valla para evitar que los linces crucen por los dos tramos al descubierto.

¿Cuál es el mínimo número de túneles que hay que hacer para evitar atropellos en las siguientes carreteras?

  • ....
  • ..X...X
  • X.XXX....X.X.X

¡Cuéntanos tus conclusiones en los comentarios! Y si crees que has encontrado una forma de programar tu solución y quieres probarla, puedes hacerlo aquí.

Solución: anuncios en el paseo marítimo

by

Hola!

Llega el momento de dar la solución a nuestro último acertijo. En él, os hablábamos de una población costera que ha colocado vallas publicitarias a lo largo del paseo marítimo, y de una empresa que quiere conseguir que los viandantes vean su anuncio al menos un número de veces en sus paseos. Para eso, conoce los puntos de inicio y de fin de los recorridos que realizan, y necesita averiguar el mínimo número de vallas que debe alquilar para conseguir su objetivo.

Gualterio nos dio su solución y… ¡acertó! Aunque haya sido en el tiempo de descuento por nuestro retraso en la publicación de la solución 🙂 su contribución es igual de válida de modo que ¡enhorabuena, un acertijo más! 🙂

Pero basta de preámbulos y vamos con la explicación. La primera situación por la que os preguntábamos era fácil. En ella, la empresa quiere que los turistas vean su anuncio al menos 5 veces, y hay sólo dos recorridos a cubrir:

  • Del número 1 al número 10 o, abreviando, (1, 10).
  • Del número 30 al 20: (30,20)

En este caso la respuesta es muy sencilla, dado que los dos recorridos no se solapan. Las vallas que la empresa alquile para que los turistas que hacen el camino (1,10) vean su anuncio no serán vistas por los turistas que hagan el recorrido (30, 20). Por tanto, será necesario alquilar 5 vallas para cada uno, por lo que el mínimo será de 10.

La siguiente pregunta es un poco más complicada. Consistía también en conseguir que los turistas vieran 5 vallas publicitarias, pero ahora los recorridos son (17-21), (10-20), (25-5), donde sí hay solapamiento.

17-21
10-20
25-5

Con la imagen delante, no resulta ya tan complicado. Lo que queremos es minimizar el número de vallas que alquilamos, de modo que queremos coger aquellas que más turistas vean. Claramente en este caso tenemos que coger las cinco vallas del rango 17-21. Las 5 serán vistas por los turistas del último recorrido, (25, 5) de modo que para ellos no hay que alquilar más. Tan sólo nos falta una más para el rango 10-20. Podemos coger la que queramos (por ejemplo la situada en el número 16):

17-21
10-20
25-5
Alq.

Alquilando las vallas marcadas en la última fila, se puede comprobar que todos los turistas ven al menos 5 veces nuestro anuncio.

¿Cómo podemos hacer el cálculo de una manera sistemática? Si el número de recorridos crece, cada vez resultará más complicado utilizar la intuición para colocar las vallas, incluso aunque nos hagamos el dibujo. De hecho, la última pregunta es bastante más larga: 6 vallas y recorridos (7, 10), (25, 33), (32, 62), (50, 20), (44, 9), (50, 86) y (24, 19).

Para resolverlo, lo que hacemos es utilizar un algoritmo voraz diseñado para la ocasión, tal y como ya hicimos en otros acertijos anteriores. Lo que haremos será ir alquilando vallas para conseguir que cada recorrido de un turista tenga nuestros 6 anuncios, de tal manera que garanticemos que, al final, el número de vallas alquiladas sea el mínimo necesario.

¿Y cómo lo conseguimos? La idea principal es ordenar los recorridos por punto de finalización. Da igual lo largo o cortos que sean. Lo importante es dónde acaban. Ten en cuenta que como el orden es importante, usaremos siempre el sentido “de menor a mayor” en los recorridos de manera que, por ejemplo, al recorrido (50, 20) le daremos la vuelta para simular que todos los turistas van en sentido ascendente de la numeración. Esto no es importante para el resultado final, pero sí para que nuestro mecanismo de obtención de la respuesta funcione.

Con esta idea, los recorridos que tenemos que cubrir (ordenados ya de menor a mayor por punto de finalización) son (7, 10), (19, 24), (25, 33), (9, 44), (20, 50), (32, 62), (50, 86). Fijate que, por ejemplo, el recorrido (9, 44) empieza antes que el (25,33). Pero lo analizaremos después porque acaba más tarde.

Ahora empezamos a analizar cada recorrido con el primero, (7, 10). Tenemos que conseguir que los turistas vean 6 vallas, y sin embargo estos turistas sólo recorren 4. Tendremos que alquilarlas todas y conformarnos con eso. Para los turistas (19, 24) nos toca hacer lo mismo: alquilar las 6 vallas de su recorrido.

El acertijo se pone más interesante con el siguiente, (25, 33). Tenemos que alquilar 6 vallas; pero, ¿cuales? Dado que tenemos ordenados los recorridos por finalización nos interesa comprar las vallas del final para que así los siguientes recorridos, que siempre acaban más tarde, tengan posibilidad de ver también las vallas que alquilamos ahora. Es decir, sin saber de antemano qué vendrá después, es mejor alquilar las vallas (28, 33), en lugar de alquilar (25, 30), porque todos los recorridos que vendrán después terminan pasado el número 33, y por tanto hay más probabilidades que vean la valla en la posición 28 que la valla en la posición 25 (dependiendo de dónde empiecen).

Tras haber analizado los tres primeros recorridos, por tanto, hemos alquilado las vallas (7, 10), (19, 24) y (28, 33). El siguiente recorrido que procesamos es (9, 44) pero este recorrido ya tiene dentro más de 6 de nuestros anuncios gracias a las vallas alquiladas antes, por lo que no añadimos ninguna más. Con (20, 50) ocurre igual.

Con el penúltimo recorrido, (32, 62), ocurre algo intermedio. En él son visibles dos vallas ya alquiladas, la 32 y la 33. Quedan 4 más por alquilar. Pero… ¿cuales? Como hemos dicho antes, lo más conservador es alquilarlas al final, en el rango (59, 62). De esa manera los recorridos que vengan después (y que acaban más tarde) podrían aprovecharse de ellas. Y… ¡así es! El último recorrido, (50, 86) ve esas 4 vallas también. Si hubiéramos alquilado vallas por detrás del 50 no las habríamos reutilizado.

Sólo falta alquilar dos vallas más para el último recorrido (en 85 y 86) y habremos terminado. Al final hemos alquilado (7, 10), (19, 24), (28, 33), (59, 62) y (85, 86), que hacen un total de 22 vallas. Podemos conseguir que los turistas vean nuestras 6 vallas alquilando otras, pero nunca podremos conseguirlo con menos de 22 vallas 🙂

Ahora que os hemos contado el truco del acertijo, quizá queráis intentar programarlo. Si lo hacéis y queréis probar vuestra solución, podéis hacerlo aquí.

¡Hasta el próximo!

Anuncios en el paseo marítimo

by

Hola!

Andamos un poco liados con los preparativos para ProgramaMe, y no hacemos más que acumular retrasos con los acertijos 😦 Para que no paséis toda esta semana sin algo en que entreteneros :-p, y aunque sea un día extraño, vamos a proponeros hoy un acertijo. Pero para dar tiempo a que lo penséis, os contaremos nuestra solución al final de la semana que viene, en lugar de este domingo.

En un intento de recaudar dinero, el ayuntamiento de un pueblo costero ha decidido poblar todo el paseo marítimo de vallas publicitarias, para desesperación de los vecinos. Ha colocado una delante de cada portal, que están numerados consecutivamente (no sólo usando los números pares o impares) al haber únicamente casas en un lado.

Una empresa local ha decidido que, para aprovechar la afluencia de turistas durante el verano, va a contratar algunas de esas vallas para hacer una campaña agresiva de publicidad. En concreto, ha analizado los “puntos calientes” del paseo marítimo (como hoteles y grandes edificios residenciales por un lado, y heladerías o chiringuitos por otro) para tener los puntos de origen y destino de los turistas. Tienen así un conjunto de recorridos habituales de sus potenciales clientes.

Ahora quieren conseguir que todos los turistas vean su anuncio un número mínimo de veces (para convencerles por aburrimiento). Pero no quieren gastarse demasiado dinero en contratar vallas publicitarias, a si es que quieren conseguirlo con el menor presupuesto posible. Por ejemplo, imaginemos que sabemos que los turistas hacen tres posibles recorridos:

  • Del número 1 al 15. Por abreviar, (1, 15)
  • (13, 30)
  • (27, 45)

La empresa quiere conseguir que todos vean el anuncio al menos 7 veces; en estas condiciones el mínimo número de vallas que hay que contratar es de 14, siempre que se escojan con inteligencia.

¿Cuál sería ese mínimo en las siguientes situaciones?

  • 5 vallas y recorridos (1, 10) y (30, 20).
  • 5 vallas y recorridos (17-21), (10-20), (25-5)
  • 6 vallas y recorridos (7, 10), (25, 33), (32, 62), (50, 20), (44, 9), (50, 86) y (24, 19)

El último es bastante más largo que los otros dos… la idea es que los dos primeros sirvan para encontrar un modo sistemático de dar con la respuesta, y el último se use para probarlo 🙂

Ten en cuenta que los turistas se desplazan en los dos sentidos por el paseo marítimo, de ahí que en algunos casos vayan en sentido decreciente de la numeración. Además, algunos recorridos son demasiado cortos como para conseguir ver el mínimo número de vallas. En ese caso, la empresa anunciante se conforma con que vean sólo anuncios suyos y no de otras empresas.

Si das con las respuestas… ¡cuéntalas en los comentarios! Y, como siempre, si programas la solución y quieres probarla, puedes hacerlo aquí.

¡Hasta la semana que viene!

Solución: K bits a uno

by

¡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!