Skip to content

Solución: ¡cada vez más huéspedes!

by en 08/12/2013

¡Ya estamos aquí, un domingo más!

Llega la hora de resolver nuestro acertijo de la semana. Os contábamos la curiosa historia de la ocupación de un hotel en la que el día de la inauguración llegó un único huésped que pasó una sola noche. Al irse, llegaron dos huéspedes, que estuvieron las dos noches siguientes. Tras ellos, tres huéspedes pasaron tres noches, y así sucesivamente. Las preguntas que os hacíamos consistían en saber el número de huéspedes que dormirían en el hotel en noches determinadas, en concreto en la noche 21, 100 y 100.000 tras la inauguración. También os preguntábamos cuántos huéspedes habría la noche 32.354 si la primera noche tras la inauguración hubiéramos tenido 555 huéspedes (durmiendo 555 noches), en lugar de solo uno.

Jordi (¡¡bienvenido al blog!!) nos dio su solución en forma de una función de C, en lugar de la solución concreta para cada pregunta 🙂 David sospechó que en el código de Jordi había algo mal, y daba sus respuestas… ¡y acertó en ambas cosas! Jordi, tu código tiene un pequeño desfase… si lo ejecutas preguntándole cuántos huéspedes hay la primera noche (y empiezando con un huésped) te dirá que hay… dos 🙂 Para comprobar el código puedes llamar a tu función con los números del 1 al 20 y ver cómo funciona, y notarás un comportamiento diferente al esperado 🙂 En concreto, los dos huéspedes están una única noche (la primera), hay tres huéspedes durante dos noches, cuatro durante tres, etcétera.

Pero vayamos con nuestra solución para el número 21. Sabéis que preferimos obtener las soluciones sin la ayuda del ordenador, de modo que también los no programadores puedan resolverlos y entenderlos. Para eso empezamos haciéndonos una tabla del número de huéspedes que hay cada noche:

oche 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Huésp. 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5

Si continuáramos con la tabla, llegararíamos enseguida a la noche número 21 donde, como nos dijo David, habrá exactamente 6 huéspedes. Con un poco más de paciencia, llegaríamos a la noche 100, nuestra segunda pregunta, en la que habrá 14 personas en nuestro hotel.

Pero se necesita demasiada paciencia para hacer la tabla hasta llegar a la noche número 100.000 como os preguntábamos. Éste es un blog de acertijos programables, por lo que podemos coger nuestro compilador favorito y simular la construcción de la tabla para que sea el ordenador quien haga el tedioso trabajo por nosotros; al fin y al cabo, se trata de sumar 1 + 2 + 3 + 4 + … Pero aunque se pueda resolver así, nos gusta poner acertijos “para todos los públicos” 🙂 sin olvidarnos de aquéllos que no saben programar. De manera que tenemos que buscar una solución menos repetitiva 🙂

Como seguro que muchos os habéis dado cuenta, nuestro acertijo tiene relación con los números triangulares. En efecto, un número triangular es aquél que se forma por la suma de varios números consecutivos, empezando por el 1. Así, el 1 es un número triangular, también lo es el 3 ( = 1 + 2), el 6 (1 + 2 + 3), etcétera:

Números triangulares (imagen de Wikipedia)

En nuestro problema estos números son importantes porque son los días “del cambio” de grupo. La noche 1 es la última que tenemos un solo huésped, la noche 3 (el segundo número triangular) es la última noche que tenemos dos huéspedes, la noche 6 (tercer número triangular) es la última con 3 huéspedes, etcétera.

Es interesante encontrar una manera rápida (sin hacer las sumas) de conseguir un número triangular determinado. Ahora sabemos que el primer número triangular es el 1, que el tercero es el 6 pero… ¿cuál es el décimo número triangular? ¿Y el número 40? Para eso, podemos recordar nuestros conocimientos de matemáticas, o buscar en la wikipedia y encontraremos que:

Triangular(n) = n·(n+1) / 2

Si esto os parece magia, hay una demostración gráfica de esta fórmula muy sencilla. Basta con que, por ejemplo, imaginéis dos triángulos T4 de la figura unidos por un lateral, formando un rectángulo. Ese rectángulo tendrá 4 circulitos en un lado, y 5 en otro, por lo que está compuesto por 20 circulitos; como en total eran dos triángulos, cada uno tiene 10, y eso es justo lo que nos está diciendo la fórmula 🙂

Esto nos permite obtener los números triangulares rápidamente. Y en nuestro acertijo nos viene bien, porque, como hemos visto, los números triangulares son “la frontera” del cambio de número de inquilinos.

Ahora bien… en realidad lo que queremos es justo lo contrario… porque, digamos, el acertijo nos da el número, y nos pregunta qué número triangular es. Por ejemplo nos dice “¿Cuántos huéspedes hay la noche 21?” Y tenemos que averiguar que el número 21 es el sexto número triangular. Dicho de otro modo, de la fórmula:

Triangular(n) = n·(n+1) / 2

conocemos Triangular(n) y desconocemos n. Volviendo a nuestros conocimientos de matemáticas, podemos despejar n y obtendremos una ecuación de segundo grado que nos convertirá directamente el número de noches en el número de huéspedes. Es necesario tener cuidado cuando la respuesta tenga decimales. Por ejemplo, para 21 nos dirá que es el sexto número triangular, pero para 20 nos dirá que es el “número triangular” 5’84. Dado que sabemos que la noche 21 es la última que tenemos 6 huéspedes en el hotel, la noche 20 (“número triangular” 5’84) tendremos también 6 huéspedes, por tanto si tenemos decimales hay que conseguir el número entero siguiente.

Con nuestra nueva herramienta, podemos sacar fácilmente que la noche número 100.000 había 447 huéspedes 🙂

Falta el caso en el que la primera noche empecemos con más de un huésped. Para no tener que usar matemáticas más complicadas lo que podemos hacer es simular que… el hotel lo abrimos antes, y empezamos con un huésped. Por ejemplo, si nos preguntan por la tercera noche si el día de la inauguración teníamos 2 huéspedes, podemos “simular” que abrimos el día antes al real y tuvimos un huésped durmiendo, al que siguieron los dos con los que hemos empezado realmente, y que nos están preguntando por la cuarta noche. Desplazamos así hacia atrás el día de la inauguración, lo que significa que tenemos que sumar al día por el que nos preguntan el número de noches que pasaron los huéspedes “falsos” anteriores a los primeros. En la pregunta que os hacíamos (noche número 32.354 empezando con 555 huéspedes) es similar a que nos pregunten la noche 186.089 empezando con un huésped. El número 186.089 sale de sumar 32.354 más 153.735 que es el número triangular número 554, es decir el número de noches que habrían pasado en nuestro hotel los huéspedes 1 + 2 + 3 + … + 554 que estamos simulando haber tenido antes de inaugurar. La respuesta es 610, como acertó David.

¡Esto ha sido intenso ¿eh?! Intencionadamente no os hemos dado la fórmula final, por si alguno quiere intentarlo 🙂 En este caso, conseguirla no es sólo importante para resolver las preguntas manualmente (sin un ordenador) rápidamente, sino que también es importante en el problema que os poníamos, porque en él los límites son muy altos (pueden preguntarnos por noches que tienen 15 dígitos) y la solución haciendo la suma con un bucle es demasiado lenta hasta con un ordenador 🙂

¡Hasta el próximo!

Anuncios

From → Soluciones

Dejar un comentario

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: