Tablero :
Acorazado (Puede colocarse en forma vertical u horizontal)
¿Y cuántos necesitaríamos si el tablero fuera de ocho por ocho?
Un problema del libro Algorithmic Puzzles
Si lo quieres compartir o guardar
viernes, 4 de abril de 2014
1296 - Jugando a la batalla naval
¿Cuál es el menor número de tiros que hay que hacer en un juego de batalla naval en un tablero de 10 x10 para asegurarse tocar al menos en una casilla a un acorazado (ocupa cuatro casillas consecutivas)?
Tablero :
Acorazado (Puede colocarse en forma vertical u horizontal)
¿Y cuántos necesitaríamos si el tablero fuera de ocho por ocho?
Un problema del libro Algorithmic Puzzles
Tablero :
Acorazado (Puede colocarse en forma vertical u horizontal)
¿Y cuántos necesitaríamos si el tablero fuera de ocho por ocho?
Un problema del libro Algorithmic Puzzles
Suscribirse a:
Enviar comentarios (Atom)
Entradas
De 10*10 creo que 24, p ej : A4 A8 B3 B7 C2 C6 C10 D1 D5 D9 E4 E8 F3 F7 G2 G6 G10 H1 H5 H9 I4 I8 J3 J7...
ResponderEliminarDE 8*8 SON 16, pej A1 A5; B4 B8 C3 C7 D2 D6 E1 E5 F4 F8 G3 G7 H2 H6
Coincido con Pablo, de 8x8 son 16 ya que necesariamente debe haber dos en cada fila y eso hace un mínimo teórico de 2*8=16. Al existir soluciones de 16, ese es el mínimo real.
ResponderEliminarDe 10x10 el mínimo teórico sería 20, ya que se puede comprobar una fila o una columna con solo dos intentos. Pero eso hace que si se cubren las filas queden huecos en las columnas, y viceversa. El mínimo que encuentro es 24.
Creo que para NxN, con N>3, se puede hacer con 2*entero((N+1)/4)*(N-2*entero((N+1)/4)) intentos.
ResponderEliminarPara 10x10 el mínimo teórico es 24.
ResponderEliminarDividimos el cuadrado de 10x10 en el máximo posible de cuadrados de 4x4, y obtenemos 4. Cada uno de los cuadrados de 4x4 necesita como mínimo 4 intentos, luego para comprobar los 4 necesitamos 16 intentos.
El resto que no queda dentro de los cuadrados de 4x4 lo dividimos en el máximo posible de rectángulos de 2x4. Cada uno necesita como mínimo 2 intentos, luego para comprobar los 4 necesitamos 8 intentos.
El resto que queda es un rectángulo de 2x2, que puede comprobarse sin ningún intento si los intentos de los cuadrados y rectángulos anteriores lo hacen.
Por tanto el mínimo teórico es 4*4+4*2+0 = 24. Como existen soluciones con 24, ese es el mínimo real.
Mediante este sistema se puede comprobar que la fórmula anterior, 2*entero((N+1)/4)*(N-2*entero((N+1)/4)) intentos, es el mínimo real para los cuadrados de lado 4N, 4N+1 y 4N+2. En los cuadrados de lado 4N+3 hacen falta 2 intentos más de los que dice el sistema, ya que el cuadrado de 3x3 que queda al final, que en teoría no necesita ningún intento si se aprovechan los anteriores, en la práctica necesita 2 intentos más. La fórmula sigue siendo correcta pero haría falta una demostración rigurosa para cuadrados de lado 4N+3.