Blogia
Tio Petros

Mil interruptores y 999 fusilados.

- Para pensar
Retomamos el tema matemático en el blog con dos acertijos para hacer boca.

Hemos hablado bastante de combinatoria, definiéndola como el arte o la técnica de contar. Así dicho parece una sosada, pero resulta que contar objetos puede ser verdaderamente difícil. Como siempre, el conjunto N nos sorprende por su hondura y dificultad. El ser humano seguramente está capacitado para comprender todos los secretos físicos del universo, pero no lo está para responder a todas las preguntas que N nos plantea.

Así dicho puede parecer una exageración pero no lo es. Es fácil comprender que el conjunto de preguntas independientes relativas a N es infinito (numerable pero infinito), de manera que simplemente no tendremos tiempo para responderlas a todas.

Contar viene a ser equivalente a averiguar el cardinal de un subconjunto de N. Cuando es difícil hacerlo directamente y no conocemos otro atajo mejor, suele ser una buena idea preguntarse por la forma que deben tener los elementos de este subconjunto a medir.

Algo así ocurre con estos dos problemas. El primero es de conteo, y el segundo nos pide el puesto de un elemento distinguido de un conjunto ordenado:

PROBLEMA UNO

Tenemos mil interruptores numerados del 1 al 1000, todos ellos en posición de apagado. Mil operarios, también numerados, pasar por ellos uno tras otro, de manera que el operario n sólo actúa sobre los interruptores múltiplos de n.
Actuar sobre un interruptor significa encenderlo si estaba apagado o apagarlo si estaba encendido.¿Cuántos interruptores quedan encendidos al final?

PROBLEMA DOS

Estamos en un grupo de mil personas que van a ser fusiladas por un procedimiento curioso: puestas en fila, el ejecutor volará la tapa de los sesos de uno de cada dos reos, empezando por el primero. Reagrupados los supervivientes y manteniendo el orden, volverá a ejecutar a uno de cada dos empezando por el primero, y así sucesivamente hasta que sólo quede uno. Qué puesto de la fila elegiria el lector?

Como siempre, lo de menos es la respuesta. Lo que importa es el método.

12 comentarios

raul -

Interesante, pero para solcionar el problema 1, sólo habrá que pensar en la cantidad impar de divisores que tienen los números que son solución, es decir los cuadrados perfectos? y qué pasa si un alumno no tiene esa herramienta disponible, no lo podrá resolver?, alguien me ayuda a pensar si hay otra forma de resolver el problema?

Klapaucius -

En el campo de prisioneros de Paracuellos , durante la guerra civil, se seguía una rutina macabramente parecida para los fusilamientos. Un día faltó un fusilando para cumplir la orden que apremiaba y la fortuna quiso que del resto de prisioneros sólo uno estuviese fumando. El oficial de turno vio la papeleta resuelta, y el pobre fumador acabó fusilado sin comerlo ni beberlo.

El desafortunado era el abuelo de una amiga, y no he podido evitar acordarme de la historia al leer el problema, confio en que me perdonen el haber sacado los pies del tiesto.

Tio Petros -

Efectivamente. Lo habeis expresado muy bien. Como habréis notado, el segundo es susceptible de generalización: el caso en el que el ejecutor mate a uno de cada n empezando por el primero, y así sucesivamente hasta que sólo quede uno...

Carlos -

Veamos el siguiente, que también se me han adelantado (me acabo de dar cuenta ahora, uno tiene esto sin actualizar y pasa lo que pasa) :

Tenemos una fila de 1000 personas. En la primera ronda, fusilan al primero, al tercero , ... , hasta el 999. Es decir, eliminamos las filas no congruentes con 0 módulo 2.
En la segunda ronda, eliminamos el 2, el 6, ... , 998 , que son las filas no congruentes con 0 módulo 4.
En general, en la ronda k-ésima , nos quedan las filas congruentes con 0 módulo 2^(k-1) . Dado que tenemos 1000, sucesimaente tendremos 500, 250, 125 ,62 , 31, 15 , 7 , 3, 1 . Es decir, tenemos 10 rondas.
El número resultante será el congruente con 0 módulo 2^ 9 , que es 512.
Por lo tanto , el afortunado es el número 512

Carlos -

Vaya, se me han adelantado con el primero, de todos modos , voy a expresarlo formalmente para que así se pueda entender mejor.

Dado un número n , podemos descomponerlo, en virtud del teorema fundamental de la aritmética, en producto de primos p_k elevados a un exponente n_k mayor o igual que cero. Es decir : n=( p_1^n_1)* .... * (p_k^n_k ) . Consideraremos al 1 como a cualquier primo elevado a cero.

Denotamos al estado apagado con un 0 , y al encendido con un 1. Trabajamos por tanto con el anillo cociente Z/2Z . Es evidente que en cada divisor de un número dado, cambia su estado, que no es más que sumar 1 al estado anterior (por trabajar en este anillo). Por lo tanto, el estado final no es más que la clase módulo 2 del número de divisores de dicho número , y como sabemos que el número de divisores D= (n_1+1)*....*(n_k+1) , tendremos que el interruptor n- ésimo se encuentra en estado [D](mod2) .
Ahora bien, dado que D es producto de factores de la forma j+1 , basta que exista un h impar para que D sea par, y por tanto, congruente 0 módulo 2,es decir, para que el interruptor esté apagado.
La condición, por lo anterior , para que el interruptor esté encendido es que n_j sea par para todo j , es decir, que el número n sea un cuadrado perfecto.
Pero 32*32 = 1024 , entonces, hay 31 interruptores encendidos.

Matías -

Cierto icp, tienes razón, es más fácil pensarlo así ^^. Entonces los menores a 1000 serían todos aquellos cuadrados de los naturales menores a la raíz de 1000. sqrt(1000) = 31.622.

Por lo tanto quedarían 31 interruptores encendidos. ¿Está bien hecho?

Matías -

En cuanto al segundo problema se trabaja por ingeniería inversa y sale fácil en log_2(1000) = 9 disparos.

Haciendo los cálculos se puede ver que la cantidad de reos que quedan después de cada disparo son:

1000 -> 500 -> 250 -> 125 -> 62 -> 31 -> 15 -> 7 -> 3 -> 1

Si yo quedo en el último disparo quiere decir que cuando se hizo el disparo anterior yo estaba 2do en la fila. Si yo ya estaba 2º cuando se hizo ese disparo, cuando se hizo el anterior estaba 4º. Y así sucesivamente.

Es fácil observar que siempre he de estar en una posición par, de lo contrario sería eliminado. Por lo que lo que debo hacer es ubicarme en una pocisión potencia de 2, como son 10 disparos tengo que estar yo en 2^(10-1) (para que quede 1, de lo contrario no quedaría ninguno). Entonces tengo que estar en la posición 512.

De esa forma mi posición sería la siguiente después de cada disparo:

512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Es poco matemática; pero creo que válida ¿no?

icp -

Se me ocurre un atajo (o vamos eso creo) al razonamiento, y es que los divisores de un número dado n se pueden agrupar siempre por parejas ( d, n/d) con d el más pequeño de los 2, excepto en el caso en que sea cuadrado perfecto en cuyo caso uno de sus divisores (su raíz cuadrada) quedaría "sin pareja".

icp -

"Y un número tiene factores pares sólo si es divisible por algún cuadrado perfecto".
Cierto pero lo que tú estás buscando son los números tal que TODOS sus factores en la descomposición tienen exponente par ( de lo contrario como has dicho tendría un número par de divisores). Y los que cumplen eso no son los divisibles por algún cuadrado perfecto, sino precisamente los cuadrados perfectos.

matias -

Por falta de sustento teórico no puedo resolver exactamente el primer acertijo pero sí puedo decir cómo lo solucionaría (en caso de poder hacerlo).

Si cada operario va a cambiar el estado sólo de aquellos interruptores múltiplos de su cardinalidad entonces es fácil ver que el estado de cada interruptor depende de la cantidad de divisores que tenga el número de orden del interruptor. Si dicha cantidad es par entonces el interruptor quedará tal como estaba originalmente, de lo contrario quedará encendido.

Sabiendo el orden de cada factor en la descomposición de un número en sus factores primos sabemos que la cantidad de divisores de un número es el producto de dichos órdenes aunmentados en uno. Por ejemplo:

250 = 2x5^3
cantidad de divisores = (1+1)x(3+1) = 8

De ahí podemos saber que si la factorización de un número contiene algún orden impar, automáticamente el número de divisores es par. Y un número tiene factores pares sólo si es divisible por algún cuadrado perfecto. Ahora es cuestión de contar estos últimos. ^_^;

mewt -

Estadistica? que estadistica? El primero es claramente de teoria de numeros, y el segundo de computacion ;-)

PS: Ya vuelvo a tener blog, ahora a ver si entre las clases de holandes y los seminarios me da tiempo a escribir algo :-P

Lola -

Clujeeeee....esta es la tuya....demuestra que preparar las clases de estadística sirve para algo :)