El juego del triángulo rectángulo

Question

El juego del triángulo rectángulo

rompecabezas
teoría de juego
Matemáticas

Anónimo

Estoy buscando una comprensión más profunda, particularmente la estrategia óptima y la puntuación máxima en función del tamaño de la cuadrícula, del siguiente juego (para un jugador) jugado con un $n$ por $m$ cuadrícula :

ingrese la descripción de la imagen aquí ( $6 \times 6$ ejemplo)

Normas

Comience con una cuadrícula hecha de $n$ por $m$ cuadrados y ejecutar tantos movimientos como puedas

Un movimiento consiste en hacer un solo corte recto que corta un triángulo rectángulo con la condición de que el corte debe comenzar y terminar en un punto de la cuadrícula.

Tu puntuación es el número de movimientos que has hecho.

Ejemplo 1: estrategia "ingenua"

La estrategia ingenua consiste en elegir siempre el movimiento que corta el triángulo rectángulo más pequeño posible.

Para rejillas más grandes que $2 \times 2$ , la estrategia ingenua termina el juego después de cuatro movimientos:

ingrese la descripción de la imagen aquí

Ejemplo 2: Un mejor intento

La siguiente ejecución del juego, aunque comienza cortando la mitad de la cuadrícula, contiene veinte movimientos:

ingrese la descripción de la imagen aquí

notas

Aunque todos los ejemplos utilizan un $6 \times 6$ cuadrícula cuadrada , también estoy particularmente interesado en tableros rectangulares no cuadrados (donde las unidades de la cuadrícula siguen siendo cuadrados, por supuesto).
Los triángulos cortados en los juegos de ejemplo son todos isósceles. ¡Tenga en cuenta que esto no es requerido por las reglas!
Dado que el triángulo más pequeño que se puede cortar legalmente es la mitad de una unidad de cuadrícula, $2nm$ es un límite superior trivial para la puntuación máxima.
Sin relación con la pregunta original, este juego para un solo jugador también se puede convertir en un interesante juego para dos jugadores : los jugadores se alternan haciendo movimientos; el último jugador en hacer un movimiento legal gana.

La función de puntuación máxima

Dejar $f(n,m)$ denota la puntuación máxima (número de movimientos) alcanzable con un $n \times m$ red.

Se sabe lo siguiente sobre $f$ :

$f(n,m) = f(m,n)$ (simetría)

$f(n,m) \leq 2nm-1$ (ver el comentario de hardmath)

$f(n,1) = 2n-1$ (ver el comentario de hardmath)

$f(n,2) = 3n$ (se puede obtener con un poco de pensamiento)

$f(1,1) = 1$ (corolario de la fórmula anterior)

$f(2,2) = 6$ (corolario de la fórmula anterior)

$f(3,3) = 11$ (obtenido por ensayo y error manual)

$f(4,4) = 16$ (obtenido por prueba y error manual, corregido por el comentario de hardmath)

$f(n,m) \ge 2\min(n,m) + 3\max(n,m) - 4$ (ver el comentario de hardmath), en particular

$f(n,n) \ge 5n - 4$

Tenga en cuenta que el último límite es realmente estricto para $1 \le n \le 4$ , por lo que este límite (y la estrategia asociada) ya podría ser la respuesta a toda la pregunta.

gerry myerson

Tal vez puedas encontrar el máximo para

1 \times 1, 2 \times 2, 3 \times 3, \dots

$1\times1,2\times2,3\times3,\dots$ hasta que tenga suficiente para buscarlo en la Enciclopedia en línea de secuencias enteras.

matemáticas duras

Cada remanente sucesivo del tablero es necesariamente una forma convexa, producida a partir de la etapa anterior por "un solo corte recto que ... debe comenzar y terminar en un punto de cuadrícula". Si no contamos la eliminación de un solo triángulo rectángulo final con tal corte, entonces el límite superior trivial es realmente

2 n m - 1

$2nm-1$ , alcanzable si una de las dimensiones es

1

$1$ .

matemáticas duras

Sugiere una estrategia (en la Q original de un jugador) de acortar la dimensión más corta (digamos

n \geq 2

$n \ge 2$ ) hasta 2 por una secuencia de

2 (n - 2)

$2(n-2)$ se mueve (dividiendo cada fila a lo largo de una diagonal), luego obteniendo

3 m

$3m$ sale del resto

2 \times m

$2 \times m$ forma. De este modo

f (n, m) \geq 2 n + 3 m - 4

$f(n,m) \ge 2n + 3m - 4$ cuando

m \geq n \geq 2

$m \ge n \ge 2$ .

usuario139000

No estoy seguro de haberte entendido correctamente. digamos que tenemos un

3 \times 4

$3 \times 4$ red. No hay forma de acortar la dimensión más corta (

3

$3$ ) Abajo a

2

$2$ sin afectar también a la otra dimensión.

usuario139000

Tenga en cuenta también que su fórmula implica que

f (4, 4) \geq 16

$f(4,4)\geq 16$ , mientras que mis ensayos indican fuertemente que

f (4, 4) = 15

$f(4,4)=15$ .

matemáticas duras

podemos reducir

3 \times 4

$3\times 4$ a

2 \times 4

$2\times 4$ en 2 movimientos, despegando la fila "superior" por bisección a lo largo de su diagonal.

usuario139000

Ah, ¿te refieres a cortar dos triángulos delgados no isósceles? Cierto, ¡eso funciona!

gontalo

Pregunta: Usted dice que el corte debe comenzar y terminar en un punto de la cuadrícula, pero ¿ese punto de la cuadrícula debe tener la forma que ha cortado hasta ahora o puede estar afuera?

frentos

he verificado

f (m, n) = 2 m + 3 n - 4

$f(m,n) = 2m + 3n - 4$ como un límite estricto para

2 \leq m \leq n \leq 10

$2 \le m \le n \le 10$ a través de una búsqueda exhaustiva.

Renders de Jens

@Frentos, ¿qué quiere decir con "límite estricto"? Quieres decir

f (m, n) \geq 2 m + 3 n - 4

$f(m,n)\geq2m+3n-4$

frentos

@JensRenders:

f (m, n) \geq 2 m + 3 n - 4

$f(m,n)\ge2m+3n-4$ fue establecido como límite por el usuario hardmath. He comprobado que la igualdad en el valor extremo, es decir

f (m, n) = 2 m + 3 n - 4

$f(m,n)=2m+3n-4$ , se mantiene para

2 \leq m \leq n \leq 10

$2 \le m \le n \le 10$ .

Tintorero Franklin Pezzuti

¿Podría tal vez establecer una relación de recurrencia averiguando la relación entre

f (m, n)

$f(m,n)$ y

f (m, n + 1)

$f(m,n+1)$ ?

vepir

@FranklinPezzutiDyer Bien por

2 \leq m \leq n

$2\le m \le n$ , los comentarios anteriores observaron una estrategia recursiva que da

f (m, n) \geq 2 + f (m - 1, n)

$f(m,n)\ge 2+f(m-1,n)$ . Pero, ¿alguien puede probar que esta estrategia es óptima? (¿Se mantiene la igualdad?) Aplicar hasta

m = 2

$m=2$ usar

f (2, n) = 3 n

$f(2,n)=3n$ , que finalmente da como resultado

f (m, n) \geq 2 (m - 2) + 3 n

$f(m,n)\ge 2(m-2)+3n$ como ya se discutió. El problema ahora es probar que se mantiene la igualdad (la estrategia es óptima) o encontrar un contraejemplo (una mejor estrategia).

Respuestas (1)

El juego del triángulo rectángulo

Tal vez puedas encontrar el máximo para $1\times1,2\times2,3\times3,\dots$ hasta que tenga suficiente para buscarlo en la Enciclopedia en línea de secuencias enteras.
Cada remanente sucesivo del tablero es necesariamente una forma convexa, producida a partir de la etapa anterior por "un solo corte recto que ... debe comenzar y terminar en un punto de cuadrícula". Si no contamos la eliminación de un solo triángulo rectángulo final con tal corte, entonces el límite superior trivial es realmente $2nm-1$ , alcanzable si una de las dimensiones es $1$ .
Sugiere una estrategia (en la Q original de un jugador) de acortar la dimensión más corta (digamos $n \ge 2$ ) hasta 2 por una secuencia de $2(n-2)$ se mueve (dividiendo cada fila a lo largo de una diagonal), luego obteniendo $3m$ sale del resto $2 \times m$ forma. De este modo $f(n,m) \ge 2n + 3m - 4$ cuando $m \ge n \ge 2$ .
No estoy seguro de haberte entendido correctamente. digamos que tenemos un $3 \times 4$ red. No hay forma de acortar la dimensión más corta ( $3$ ) Abajo a $2$ sin afectar también a la otra dimensión.
Tenga en cuenta también que su fórmula implica que $f(4,4)\geq 16$ , mientras que mis ensayos indican fuertemente que $f(4,4)=15$ .
podemos reducir $3\times 4$ a $2\times 4$ en 2 movimientos, despegando la fila "superior" por bisección a lo largo de su diagonal.
Ah, ¿te refieres a cortar dos triángulos delgados no isósceles? Cierto, ¡eso funciona!
Pregunta: Usted dice que el corte debe comenzar y terminar en un punto de la cuadrícula, pero ¿ese punto de la cuadrícula debe tener la forma que ha cortado hasta ahora o puede estar afuera?
he verificado $f(m,n) = 2m + 3n - 4$ como un límite estricto para $2 \le m \le n \le 10$ a través de una búsqueda exhaustiva.
@Frentos, ¿qué quiere decir con "límite estricto"? Quieres decir $f(m,n)\geq2m+3n-4$
@JensRenders: $f(m,n)\ge2m+3n-4$ fue establecido como límite por el usuario hardmath. He comprobado que la igualdad en el valor extremo, es decir $f(m,n)=2m+3n-4$ , se mantiene para $2 \le m \le n \le 10$ .
¿Podría tal vez establecer una relación de recurrencia averiguando la relación entre $f(m,n)$ y $f(m,n+1)$ ?
@FranklinPezzutiDyer Bien por $2\le m \le n$ , los comentarios anteriores observaron una estrategia recursiva que da $f(m,n)\ge 2+f(m-1,n)$ . Pero, ¿alguien puede probar que esta estrategia es óptima? (¿Se mantiene la igualdad?) Aplicar hasta $m=2$ usar $f(2,n)=3n$ , que finalmente da como resultado $f(m,n)\ge 2(m-2)+3n$ como ya se discutió. El problema ahora es probar que se mantiene la igualdad (la estrategia es óptima) o encontrar un contraejemplo (una mejor estrategia).

Piedra · Answer 1

Dado que el tablero mxn puede no estar necesariamente cuadrado, tal vez para los tableros no cuadrados, debe usar un método que lo trate como un tablero no cuadrado. Estoy implicando que algunos de los triángulos que se cortan probablemente no sean isósceles debido a las diferentes dimensiones y, de hecho, la forma más óptima puede ser cortar triángulos en la proporción del rectángulo.

Otra posibilidad es seccionar el tablero rectangular en tablero cuadrado y no cuadrado. Luego, usa el método óptimo para resolver el cuadrado y luego continúa cortando triángulos rectángulos en la sección izquierda sobre la sección no cuadrada.

Espero que esto proporcione una idea de este problema.

El juego del triángulo rectángulo

Anónimo

Normas

Ejemplo 1: estrategia "ingenua"

Ejemplo 2: Un mejor intento

notas

La función de puntuación máxima

gerry myerson

matemáticas duras

matemáticas duras

usuario139000

usuario139000

matemáticas duras

usuario139000

gontalo

frentos

Renders de Jens

frentos

Tintorero Franklin Pezzuti

vepir

Respuestas (1)

Piedra

¿Ganar un juego restringido de Nim?

¿Un juego de probabilidad muy fascinante sobre cómo maximizar la codicia?

Estrategia óptima para 2 jugadores Variación del juego Lights Out

Divertidos acertijos matemáticos para niños.

Campos de interés en teoría de juegos para una disertación de matemáticas

Pregunta de la escuela de 7 años

¿Cuál es la forma óptima de jugar un juego asimétrico de piedra, papel o tijera?

Condiciones suficientes puede llenar una cuadrícula dado el contenido de la fila y la columna

¿Por qué es óptimo desertar siempre en el dilema del prisionero iterado con un número finito conocido de iteraciones?

Fibonacci nim estrategias ganadoras en diferentes situaciones