El problema de las 100 puertas y los divisores de un número natural

En matemáticas hay conceptos sencillos de comprender y de manejar y conceptos con los que es muy complicado trabajar; por otra parte, hay temas de los que se puede sacar mucha chicha, y también los hay del tipo contrario, de los que se puede tirar poco.

Pero sencillo no es ni mucho menos sinónimo de simple. Un concepto sencillo, como puede ser el de divisor de un número natural, puede dar lugar a problemas maravillosos, cuyo resultado sorprende por su belleza y cuya explicación termina por elevarlos a la categoría de maravilla matemática.

Todo esto lo digo por un problema que me envió Fernando hace unas semanas. Él conocía la solución, pero la había obtenido de manera informática, y no sabía cómo meter mano matemáticamente a dicho problema. Eso es lo que vamos a hacer en este post.

El tema va de puertas, como puede verse en el título del post. A mí me llegó planteado con 100 puertas, pero se puede plantear con el número de puertas que queramos. Vamos a introducir el problema poco a poco. Comencemos con 5 puertas:

Supongamos que tenemos 5 puertas numeradas del 1 al 5 que están todas cerradas. Realizaremos, para cada puerta, el siguiente proceso: cambiar de estado todas las puertas cuyo número sea múltiplo de la puerta en la que estemos en ese momento.

Para que se entienda comencemos con este ejemplo (A=abierta, C=cerrada):

  • Nos ponemos en la puerta 1 y abrimos todas las que tengan un número múltiplo de 1. Es decir, en este caso las abrimos todas. Tenemos A A A A A.
  • Nos ponemos en la puerta 2 y cambiamos de estado todas las que tienen como número un múltiplo de 2, es decir, cerramos la 2 y la 4 (estaban abiertas). Ahora tenemos A C A C A.
  • Nos colocamos en la 3 y cambiamos todas las múltiplo de 3, es decir, cerramos la 3. Queda A C C C A.
  • Vamos a la 4 y cambiamos las múltiplo de 4, en este caso solamente la 4. Nos queda A C C A A.
  • Por último, nos vamos a la 5 y cambiamos todas las múltiplo de 5, esto es, únicamente la 5. Y así llegamos a la formación final: A C C A C.

En este ejemplo han quedado abiertas la puerta 1 y la puerta 4.

Realicemos el mismo procedimiento para 10 puertas (podéis hacerlo en un papel antes de seguir leyendo):

  • Puerta 1: A A A A A A A A A A.
  • Puerta 2: A C A C A C A C A C.
  • Puerta 3: A C C C A A A C C C.
  • Puerta 4: A C C A A A A A C C.
  • Puerta 5: A C C A C A A A C A.
  • Puerta 6: A C C A C C A A C A.
  • Puerta 7: A C C A C C C A C A.
  • Puerta 8: A C C A C C C C C A.
  • Puerta 9: A C C A C C C C A A.
  • Puerta 10: A C C A C C C C A C.

En este caso quedan abiertas la puerta 1, la puerta 4 y la puerta 9.

¿Vais oliendo ya lo que ocurre? Seguro que sí. ¿Qué ocurriría si tuviéramos 20 puertas?…

…¡Exacto! Quedarían abiertas la 1, la 4, la 9 y la 16. ¿Y con 30 puertas? Pues sí, la 1, la 4, la 9, la 16 y la 25

…¿Y con 100? Pues, evidentemente, la 1, la 4, la 9, la 16, la 25, la 36, la 49, la 64, la 81 y la 100.

Es decir, mediante este procedimiento las puertas que quedan abiertas corresponden sola y exclusivamente a las que tienen como número un cuadrado perfecto. No me negaréis que el resultado obtenido tiene una belleza numérica digna de mención.s

Bien, cuando he escrito las puertas que quedarían abierta si partimos de 100 he dicho evidentemente. ¿Es este resultado tan evidente? ¿Qué conceptos están involucrados en él? Pues únicamente el que aparece en el título, que también se comenta al principio del post: divisor de un número natural. Concretamente el número de divisores de un número natural.

Dado un número natural N, se dice que otro número natural a es un divisor de N si existe un tercer número natural c que cumple que a \cdot c=N. Por ejemplo, 5 es divisor de 55 porque 5·11=55, pero 5 no es divisor de 71 porque no existe ningún número natural que dé 71 al multiplicarlo por 5.

En nuestro problema de las puertas, todas comienzan cerradas y cambian de estado cuando nos colocamos delante de un divisor del número de dicha puerta. Por ejemplo, la secuencia que se sigue en la puerta 18 es la siguiente: se abre con el 1, se cierra con el 2, se abre con el 3, se cierra con el 6, se abre con el 9 y se cierra con el 18, por lo que la puerta 18 termina cerrada. Y con la puerta 16 la secuencia es: se abre con el 1, se cierra con el 2, se abre con el 4, se cierra con el 8 y se abre con el 16. En este caso, la puerta 16 queda abierta.

¿Qué ocurre exactamente? Pues muy sencillo: si un número natural tiene un número par de divisores la puerta termina cerrada, mientras que si tiene un número impar de divisores la puerta queda abierta. Por tanto hemos llegado a la clave: ¿cuántos divisores tiene un número natural? ¿cómo contarlos?.

Para contar el número de divisores de un número natural lo primero que haremos será descomponer ese número como producto de sus factores primos (operación que todos hemos hecho en el colegio). Si nuestro número es N, en su descomposición habrá un cierto números de factores primos, digamos k (que simbolizaremos como p_1, \ldots , p_k), cada uno de ellos elevado a una cierta potencia (a las que llamaremos n_1, \ldots , n_k). Vamos, que la descomposición quedaría así:

N=p_1^{n_1} \cdot \ldots \cdot p_k^{n_k}

Analicemos qué ocurre con el primer factor primo, p_1, en relación con el número de divisores de N. Si lo eliminamos completamente de la descomposición, el número resultante es un divisor de N, por lo que ya tenemos uno. Si dejamos solamente p_1 junto al resto de la descomposición, nos queda otro divisor, por lo que ya llevamos dos divisores. Si dejamos p_1^2 tenemos otro divisor más, con lo que tendríamos ya tres divisores. Y si seguimos aumentando la potencia de p_1 obtenemos en cada caso un divisor de N. ¿Cuántos hay de este tipo? Pues tantos como indica el exponente y uno más, que sale de eliminar la potencia completamente. Por tanto tendríamos por ahora n_1+1 divisores.

Esta operación la podemos hacer con todos los números primos que aparecen en la descomposición, por lo que tendríamos n_2+1 divisores del tipo anterior relativos a p_2, y n_3+1 divisores de este tipo para p_3, y así sucesivamente hasta llegar al último, p_k, para el que tenemos n_k+1 divisores.

Pero no todos los divisores de N tendrán alguna de estas formas. Por ejemplo, si eliminamos completamente p_1, quitamos un p_2, quitamos dos p_4 y dejamos el resto, el resultado es otro divisor de N que no es de ninguno de los tipos anteriores. ¿Cómo cuento todos estos que no he contado todavía?

Es sencillo comprobar que el número total de divisores de un número natural como el N anterior es

(n_1+1) \cdot (n_2+1) \cdot \ldots \cdot (n_k+1)

es decir, el producto de todas las cantidades de divisores del tipo anterior correspondientes a todos los factores de N.

Bien, si esa es la cantidad de divisores de un número natural, lo que necesitamos para saber si la puerta correspondiente a ese número quedará abierta o cerrada es comprobar si ese número de divisores es par o impar. Si cualquiera de los factores (n_i+1) es par, entonces el producto total, es decir, el número de divisores, será par, por lo que la puerta de ese número quedará cerrada. Si todos los factores (n_i+1) son impares, entonces el producto será impar y la puerta quedará abierta. ¿Qué debe ocurrir para que todos los factores sean impares? Pues, evidentemente, que todos los n_i sean pares, es decir, que todos los factores primos de la descomposición de N aparezcan un número par de veces. Pero como todos sabemos esto ocurre sola y exclusivamente para los cuadrados perfectos. Esto explica por qué con el procedimiento anterior obtenemos este precioso resultados: las únicas puertas que quedan abiertas son las que corresponden a los cuadrados perfectos.


Esta entrada es mi tercera colaboración a la Edición 2.5 del Carnaval de Matemáticas, que en esta ocasión organiza Mago Moebius.


La imagen la he tomado de la cuenta de Flickr de peaceshooter.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

14 Comentarios

  1. Muy bien explicado!

    De todos modos, quizá el cálculo final se hace demasiado complicado. Además del “como todos sabemos esto ocurre sola y exclusivamente para los cuadrados perfectos.”

    Propongo una prueba alternativa, más sencilla.

    La idea es no calcular el numero de divisores (ni siquiera abstractamente) si no estudiar directamente su paridad. Qualquier divisor entero d de N aparece emparejado con otro divisor entero, que es N/d. Eso implica que existen un numero par de ellos. La unica excepción es que N sea un cuadrado perfecto, pues entonces d=N/d, y no aparece dos veces. Pero eso sólo puede ocurrir para un divisor, de manera que en ese caso habrá un numero impar de divisores.

    A parte de este detalle, interesante reflexión sobre los temas aparentemente sencillos pero que dan para mucho…

    Publica una respuesta
  2. Muchas gracias por dar solución al problema! Ahora me ha quedado clarísimo.

    Publica una respuesta
  3. Gran artículo, no por sencillo tiene que ser aburrido. 😀

    El método me recuerda a la criva de Eratóstenes ¡sólo que para cuadrados perfectos en lugar de primos!

    Publica una respuesta
  4. no creo que se le pueda calificar a algo tan bello como un problema

    Publica una respuesta
  5. Llevo tiempo visitando este blog,pues siempre encuentro cosas muy interesantes..Te sugeriría que abrieras una nueva entrada para enunciar el teorema que esta implícito en este resultado y lo pusieras en alguna categoria de demostraciones del blog, pues es un resúltado interesante.Demostrar que la cantidad de divisores de cualquier natural n es (n_{1}+1)(n_{2}+2)\ldots(n_{k}+1). Ojalá no ignores mi sugerencia.

    PD: Espero pronto mandarte un artículo muy interesante relacionado con los números primos y la conjetura de Goldbach :).

    Publica una respuesta

Trackbacks/Pingbacks

  1. El carnaval de Matemáticas día a día… « Juegos topológicos - [...] El problema de las 100 puertas y los divisores de un número natural. [...]
  2. El problema de las 100 puertas y los divisores de un número natural - [...] El problema de las 100 puertas y los divisores de un número natural gaussianos.com/el-problema-de-las-100-puertas-y-los-divis...  por…
  3. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: En matemáticas hay conceptos sencillos de comprender y de manejar y conceptos con los…
  4. Resumen de la Edición 2.5 del Carnaval de Matemáticas « Juegos topológicos - [...] El problema de las 100 puertas y los divisores de un número natural “Gaussianos” nos propone un curioso juego…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *