Buscando en internet encontras que estas cajas fuertes se abren de la siguiente manera:
Antes de marcar la combinación de tres números, se debe apretar el botón rojo.
Empezando con el dial en cero, hay que girar el dial en el sentido de las agujas del reloj hasta el primer número de la combinación, luego retornar el dial en sentido inverso hasta el cero, luego hay que llevar el dial nuevamente hasta el segundo número y volver a cero, y finalmente llevar el dial hasta el tercer número de forma tal que al marcar este número la puerta de la caja se abrirá inmediatamente.
Hay 40 números en el dial incluyendo el cero. Las combinaciones no pueden tener el cero como uno de sus números.
a) ¿Cuál es el máximo número de intentos requeridos para abrir la caja fuerte?
b) Si no hubiera que apretar el botón rojo antes de los tres números, ¿Cuál sería el máximo de número de intentos? Si alguien sabe como minimizar el números de intentos por favor expliquemelo, a ver si aprendo (No sé la respuesta)
Si lo quieres compartir o guardar
Entradas
a)El nº máximo de combinaciones a probar es 40x40x40=64.000
ResponderEliminarEsto supone 64.000x3 giros del dial. O sea, 192.000 giros de dial.
b) Al no tener que apretar el botón rojo, la prueba de la primera combinación supone 3 giros de dial, pero probar la siguiente combinación supone 1 solo giro de dial añadido. O sea, con 4 giros de dial probamos 2 combinaciones. Mientras que al tener que pulsar el botón rojo, para probar 2 combinaciones necesitamos 2x3 giros de dial.
De ahí a mostrar el camino óptimo va un trecho. Creo que el tema va por encontrar un camino hamiltoniano entre grupos de 2 dígitos. Además entre todas las combinaciones todos los grupos de 2 dígitos se repiten el mismo nº de veces:80.
Vicente iq.
Vicente :
EliminarCon respecto a la primer parte el resultado es otro, solo diré que releas el enunciado y como pista que tienes que ver que es un problema con la etiqueta "Pensamiento lateral"
Con respecto a la segunda parte, creo que como tu dices con 4 giros tenemos 2 combinaciones, pero con 5 tenemos 3 (1,2,3 - 2,3,4 - 3,4,5) , con 6, 4 , etc
De ahí a saber combinarlos para minimizar los giros es otra cosa
ok Claudio. Revisaré la parte a). No me había fijado en la etiqueta que comentas !!.
EliminarVicente iq.
b) El problema se reduce a buscar la cadena de longitud mínima que contenga todas las combinaciones posibles de 3 números entre 40.
ResponderEliminarNo conozco ningún algoritmo para esto, que aplique algún tipo de simplificación, pero puede que exista. Seguro se puede calcular por fuerza bruta con backtracking o con otros métodos. Me parece un problema de tipo NP-Completo.
Vicente iq.
Para el caso de combinaciones de 3 números, pero solo utilizando números de 1 al 3 (no del 1 al 40), el total de combinaciones posibles es de 27.
ResponderEliminarLa cadena de longitud máxima sería de 27x3=81 dígitos.
La cadena de longitud mínima sería de 27-2=25 dígitos.
La menor que he encontrado es una de longitud 31 que contiene las 27 combinaciones:
1,1,1,3,3,3,1,3,2,2,2,1,2,1,3,1,2,3,2,1,1,2,2,3,1,1,2,3,3,2,3
Y repite 2 combinaciones 2 veces: la 1,2,3 y la 1,1,2.
Seguro que se puede mejorar.
Vicente iq.
Perdón, la longitud mínima para 27 combinaciones es de 27+2=29, no 27.
EliminarPara 40 debe ser 40+2=42.
Vicente iq.
Solución óptima con 29 dígitos al problema de 3 nºs:
Eliminar1,1,1,2,1,1,3,1,2,2,1,2,3,1,3,2,1,3,3,2,2,2,3,2,3,3,3,1,1
Vicente iq.
Para la primer parte es importante la palabra "INMEDIATAMENTE"
ResponderEliminarno soy capaz, Claudio.
Eliminar:(
Vicente iq.
Para la parte A, el número de intentos necesarios es 1600?
ResponderEliminarMatías Benzo.
Matías : Exacto.
EliminarPregunta tonta: ¿por qué 1600 y no 1521? Si hay 40 números incluyendo al 0, pero el 0 no puede ser parte de la combinación ¿No sería 39 x 39 entonces?
EliminarCoki :Tal como lo redacté tenes razón, son 39 números
EliminarA veces me pica un huevo
Eliminarbuena información lo aplicare
ResponderEliminarPara hallar la cadena de longitud mínima se sigue el siguiente proceso (vamos a verlo para N=3):
ResponderEliminarSe comienza con la combinación más baja, tomaremos la 111.
La combinación siguiente es la 112, que modifica el dígito 3º. Aumentamos en 1 el dígito 3º por lo que probamos la 112.
La combinación siguiente es la 113, que modifica el dígito 3º. Aumentamos en 1 el dígito 3º por lo que probamos la 113.
La combinación siguiente es la 121, que modifica el dígito 2º (y también el 3º, pero consideramos solo el que está más a la izquierda). Aumentamos en 1 el dígito 2º por lo que probamos la 123.
La combinación siguiente es la 122, que modifica el dígito 3º. Aumentamos en 1 el dígito 3º por lo que probamos la 121 (después de 3 va 1).
La combinación siguiente es la 123, que modifica el dígito 3º. Aumentamos en 1 el dígito 3º por lo que probamos la 122.
La combinación siguiente es la 131, que modifica el dígito 2º. Aumentamos en 1 el dígito 2º por lo que probamos la 132.
La combinación siguiente es la 132, que modifica el dígito 3º. Aumentamos en 1 el dígito 3º por lo que probamos la 133.
La combinación siguiente es la 133, que modifica el dígito 3º. Aumentamos en 1 el dígito 3º por lo que probamos la 131.
La combinación siguiente es la 211, que modifica el dígito 1º. Aumentamos en 1 el dígito 1º por lo que probamos la 231.
Después de 27 modificaciones volvemos a la inicial. La serie es:
111-112-113-123-121-122-132-133-131-231-232-233-213-211-212-222-223-221-321-322-323-333-331-332-312-313-311-111
Para cualquier otro número de pruebas se procede igual. El primer valor no tiene que ser el 111, vale cualquiera porque es cíclico.
Este método se me ocurrió hace años buscando la combinación de un mando a distancia de garaje. Tenía ocho pines que podían estar en 0 o 1. Empecé a cambiarlos como si escribiera números en binario, sin fijarme en los valores que iban saliendo. En apenas cinco minutos probé todas las combinaciones, aunque antes abrí la puerta y averigüé la correcta.
Claudio, te he contestado a un problema que no es el que pedías. Ahora sí contesto el que es.
ResponderEliminarPara hallar la cadena de longitud mínima se sigue el siguiente proceso (lo voy a hacer para N=3).
Se ponen todas las combinaciones ordenadas en una lista:
1-1-1, 1-1-2, 1-1-3, 1-2-1, ... , 3-3-2, 3-3-3.
Ahora se escribe en primer lugar el valor más alto, en este caso 3, tres veces, y se tacha la combinación 3-3-3 de la lista:
3-3-3-
A continuación se pone la primera combinación de la lista, 1-1-1:
3-3-3-1-1-1-
Se tachan las combinaciones usadas de la lista, que son 3-3-1, 3-1-1 y 1-1-1. Se pone la siguiente combinación sin tachar de la lista, la 1-1-2. Como la cadena actualmente acaba en 1-1- lo aprovechamos y se pone solo el 2:
3-3-3-1-1-1-2-
Se tacha las combinación usada de la lista, que es 1-1-2. Se pone la siguiente combinación sin tachar de la lista, la 1-1-3.
3-3-3-1-1-1-2-1-1-3-
Se tachan las combinaciones usadas de la lista, que son 1-2-1, 2-1-1, y 1-1-3. Se pone la siguiente combinación sin tachar de la lista, la 1-2-2:
3-3-3-1-1-1-2-1-1-3-1-2-2-
Se continúa hasta usar todas las combinaciones:
3-3-3-1-1-1-2-1-1-3-1-2-2-1-2-3-1-3-2-1-3-3-2-2-2-3-2-3-3-
Con los números hasta 40 empezaría así:
40-40-40-1-1-1-2-1-1-3-1-1-4-1-1-5-1-1-6-1-1-7-...
Quién me ayuda a abrir una caja fuerte, no sé la combinación ni su longitud, mi correo es nainru@hotmail.com. Gracias,
ResponderEliminar