¿Es posible la igualdad?
Cada una de las celdas de un tablero de 5 x 5 contiene un número diferente de monedas de oro entre 1 y 25, como se muestra a continuación.
Un movimiento consiste en tomar todas las monedas en dos celdas adyacentes (ya sea vertical, horizontal o diagonalmente) y dividirlas uniformemente entre esas dos celdas, colocando una moneda extra en la celda que originalmente tenía más monedas en el caso de que el número total de monedas es impar.
a) ¿Es posible que todas las celdas contengan el mismo número de monedas (es decir, 13) después de un número finito de movimientos?
b) Cuáles son las condiciones necesarias y suficientes para que un tablero de 5 x 5 cuyas 25 celdas contengan cada una un número diferente de monedas de oro entre 1 y 25 sea convertible en un tablero con el mismo número de monedas en cada celda después de un número finito de movimientos ?
Respuestas
Descubrí la parte a):
De hecho, la igualdad es posible.
Aquí está mi barajar a través de la cuadrícula:
Aquí está el lapso de tiempo:
Y aquí está el programa que codifiqué con python para la herramienta en el gif. Simplemente ejecute este código:
import pygame
# You can change the grid & size to whatever you like
grid = [[7, 24, 12, 8, 11],
[13, 21, 3, 20, 19],
[10, 22, 15, 2, 9],
[23, 1, 6, 16, 17],
[5, 25, 14, 4, 18]]
size = 60
pygame.init()
pygame.font.init()
font = pygame.font.SysFont("Arial", size-10)
wn = pygame.display.set_mode((600, 600))
class Square():
def __init__(self, pos, num):
self.x = pos[0]
self.y = pos[1]
self.num = num
self.color = (255, 255, 255)
self.rect = pygame.Rect(self.x, self.y, size-5, size-5)
def clear(self):
self.color = (255, 255, 255)
def draw(self):
pygame.draw.rect(wn, self.color, self.rect)
text = font.render(str(self.num), True, (0, 0, 0))
if len(str(self.num)) == 1:
wn.blit(text, (self.x+size*.25, self.y*.98))
else:
wn.blit(text, (self.x+size*.055, self.y*.98))
class Box():
def __init__(self, grid, cor):
y1 = cor[0]-1 if cor[0] else 0
y2 = len(grid)+2 if cor[0] > len(grid)+2 else cor[0]+2
x1 = cor[1]-1 if cor[1] else 0
x2 = len(grid[0])+2 if cor[1] > len(grid[0])+2 else cor[1]+2
self.box = [c for r in grid[y1:y2] for c in r[x1:x2] if c != grid[cor[0]][cor[1]]]
def color(self, color):
for square in self.box:
square.color = color
def avg(n1, n2):
n = n1 + n2
if n % 2:
if n1 > n2:
return n // 2 + 1, n // 2
return n // 2, n // 2 + 1
return n // 2, n // 2
squares = [[Square((i*size, j*size), col) for j, col in enumerate(row)] for i, row in enumerate(grid)]
clicked = []
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
if event.type == pygame.MOUSEBUTTONDOWN:
for row in squares:
for square in row:
if square.rect.collidepoint(pygame.mouse.get_pos()):
if not clicked:
clicked.append(square)
square.color = (150, 255, 255)
x, y = clicked[0].x, clicked[0].y
box = Box(squares, (x//size, y//size))
box.color((255, 255, 150))
else:
if square in box.box:
clicked.append(square)
if square == clicked[0]:
box.color((255, 255, 255))
clicked[0].clear()
clicked.clear()
if len(clicked) == 2:
clicked[0].num, clicked[1].num = avg(clicked[0].num, clicked[1].num)
box.color((255, 255, 255))
clicked[0].clear()
clicked.clear()
for row in squares:
for square in row:
square.draw()
pygame.display.update()
Para la parte b), puede que lo sepa o no. Lo miraré más profundamente.
Esta no es una respuesta completa, pero tal vez alguien más pueda usarla para una prueba completa.
Parte (a).
Para algunas cuadrículas, es posible. El ejemplo más simple simplemente tiene cada par de números que suman$26$adyacentes entre sí. Por ejemplo, cubra el 5x5 con 12 fichas de dominó, dejando un cuadrado vacío. Poner$13$ en ese cuadrado vacío, y las parejas $(1,25)$, $(2,24)$, ..., $(12,14)$en las fichas de dominó. Al combinar cada par de dominó, esto obviamente puede convertirse en todo$13$ en doce movimientos.
Respuesta parcial para el inciso b).
Dejar $x_i$ para $i=1$ a $25$ ser los valores actuales en el tablero, y considerar la suma de la distancia al cuadrado $13$:
$$D=\sum_{i=1}^{25} (x_i-13)^2$$
Es bastante fácil mostrar que cada movimiento que realmente cambia los valores en el tablero reducirá el valor de $D$:
Prueba: Supongamos que aplicamos un movimiento a los valores$a+b$ y $a-b$. Antes de la mudanza estos contribuyen$(a+b-13)^2+(a-b-13)^2$ a la suma $D$. Después del movimiento, ambas celdas tienen valor.$a$ y contribuir $2(a-13)^2$. Por lo tanto$D$ se reduce en: $$(a+b-13)^2+(a-b-13)^2-2(a-13)^2 = 2b^2$$
lo cual es positivo. De forma similar, puede comprobar que aplicando un movimiento a$a+1+b$ y $a-b$ se reducirá $D$ por $2b(b+1)$.
Siempre que haya movimientos reales disponibles, es decir, siempre que haya celdas adyacentes que difieran en$2$ o más, $D$puede ser reducido. Cuando$D$ es cero, el rompecabezas se resuelve porque entonces todas las celdas contienen $13$.
Sin embargo, surge un problema cuando todas las celdas adyacentes difieren en$1$o menos. En este estado no hay más movimientos reales y no es necesariamente el caso de que todas las celdas sean iguales. Podrías tener, por ejemplo, un$12$ y un $14$ aislados unos de otros con el resto todos $13$. Quiere evitar esto, por supuesto, pero aún no he descubierto si eso siempre es posible.
Un punto de partida para la parte (b): consideremos algunas tablas más pequeñas. Voy a normalizar el valor medio de la moneda a 0 e intentar analizar configuraciones iniciales arbitrarias donde las monedas suman 0.
2x2:
En un tablero de 2x2, cada cuadrado es vecino a cada otro cuadrado. En cualquiera de estos tableros, todas las configuraciones iniciales se pueden resolver: el único tablero donde no se pueden realizar movimientos es el tablero de todos los ceros.
1x3:
Un tablero de 1x3 es más interesante. Trabajemos hacia atrás desde el estado final, (0,0,0). Los únicos predecesores posibles son (A, -A, 0) y su reverso, para enteros distintos de cero A. Los únicos predecesores posibles de ese estado ocurren cuando A = + - 1, y son de la forma (-1, B + 1, -B), donde B es un número entero positivo y la negación y el reverso de esa secuencia. Independientemente de B, no hay más predecesores, porque un estado solo tiene predecesores si tiene dos celdas adyacentes que difieren en 0 o 1.
Así,
En 1x3, un estado se puede resolver si y solo si tiene un 0 en una celda exterior (no central), o tiene un +/- 1 en una celda exterior, y la celda del medio es de signo opuesto.
Con suerte, podemos extender la solución 1x3 a una solución 1x4, o tal vez a una de 4 ciclos. Este podría ser un problema en el que es más natural pensar en gráficas arbitrarias que específicamente en gráficas de tablero de ajedrez.
Respuesta conjeturada a b)
Restemos 13 de todos los números por conveniencia.
Una posición está estrictamente desequilibrada si existe una división en dos piezas conectadas de manera que
1. no hay una secuencia de movimientos que transfiera masa entre las dos piezas 2. las sumas $s$ y $-s$ sobre cada una las dos piezas no son cero
Obviamente, una posición estrictamente desequilibrada es imposible de ganar.
Una posición está desequilibrada si existe una división en dos piezas conectadas de manera que
las sumas $s$ y $-s$ sobre cada una de las dos piezas no son cero y no hay una secuencia de movimientos que transfiera $s$ o más unidades de masa entre los dos.
Como una posición desequilibrada eventualmente se simplificará en una estrictamente desequilibrada, también es imposible de ganar.
También es obvio que cada posición que no se puede ganar eventualmente se simplificará en una estrictamente desequilibrada.
Lo que nos gustaría establecer es lo siguiente
Conjetura: Toda posición imposible de ganar está desequilibrada.
o equivalente,
Variante: si una posición no está desequilibrada, existe un movimiento tal que la posición resultante tampoco está desequilibrada.
Esto me parece bastante plausible, pero no he podido probarlo.
Tenga en cuenta que la conjetura es incorrecta para tableros muy pequeños como 4x1: la posición -1,5, -5,1 no está desequilibrada, pero cada uno de los tres movimientos posibles crea una posición desequilibrada debido al sobreimpulso. Sin embargo, si incrustamos este patrón en un espacio más grande y cero pad, el problema desaparece:
-1 5 -5 1 -1 3 -5 1 -1 3 -3 1
-> -> ->
0 0 0 0 0 2 0 0 0 2 -2 0
-1 3 -3 1 -1 3 -3 1 -1 3 -1 -1
-> -> ->
0 0 0 0 0 0 0 0 0 0 0 0
-1 1 1 -1 -1 1 0 0 0 0 0 0
-> ->
0 0 0 0 0 0 0 0 0 0 0 0
Lo completé en 32 movimientos, como se muestra en la imagen adjunta.
