Bombillas e interruptores

Question

Hay 40 bombillas en una habitación de una casa grande y 40 interruptores en una centralita cerca de la entrada, lejos de la habitación y sin contacto visual con ella. Cada uno de los interruptores corresponde a una bombilla. Sólo podemos ver el estado (encendido, apagado) de cada bombilla si nos acercamos a la habitación. Queremos averiguar qué interruptor está conectado a cada bombilla. ¿Cuál es el número mínimo de veces que tendremos que ir andando a la habitación de las bombillas?

Entiendo que debe haber un patrón dejando de lado algunas de las bombillas cada vez, de forma única. Supongo que algo que tiene que ver con la factorización primaria de 40.

Answer 1

sugerencia

Si hubiera $2^n$ bombillas que se necesitan $n$ conmutaciones, por lo que se necesitarían 6 conmutaciones porque $40>2^5$

Tienes que demostrar que siempre que tengas más de $2^n$ necesitas más de n swithcings, y aquí tienes un método en 6 pasos para descubrir los 40.

Que los interruptores sean $S_1,S_2,...,S_{40}$ y $s(ak+b)$ sea la conmutación de todos los interruptores con índice $i=ak+b$ , donde $a,k,b\in Z$

1. $s(2k)$
2. $s(4k)$ y $s(4k-1)$
3. $s(8k)$ y $s(8k-2)$ y $s(8k-1)$ y $s(8k-3)$
4. $s(16k)$ y $s(16k-1)$ y $s(16k-2)$ ... y $s(16k-7)$
5. $s(32k)$ y $s(32k-1)$ y $s(32k-2)$ ... y $s(32k-15)$
6. $s(64k)$ y $s(64k-1)$ y $s(64k-2)$ ... y $s(32k-31)$

EDIT - esto que escribí se mantiene con la preposición de que todas las bombillas estaban apagadas al principio. Si no fuera el caso, entonces se necesitaría un paseo más a la habitación. Así que n+1, o en este caso particular 7 veces visitar la habitación.

Si aún no has probado el enunciado, este problema es como asignar un número binario a cada bombilla y a cada interruptor. Así que cada vez que tocas un interruptor añades 1 a la matriz de sus bits, y si te saltas un interruptor le añades cero. Lo mismo para las bombillas cuando cambian de estado se añade 1, y si permanece igual se añade 0. Al final cada interruptor se ajusta a la bombilla con el mismo número binario.

Así que para que cada interruptor tenga un número diferente se necesita al menos $n$ dígitos para cada uno de ellos.