A igualdade é possível?
Cada uma das células de um tabuleiro 5 x 5 contém um número diferente de moedas de ouro entre 1 e 25, conforme mostrado abaixo.
Um movimento consiste em pegar todas as moedas em duas células adjacentes (vertical, horizontal ou diagonal) e dividi-las igualmente entre essas duas células, colocando uma moeda extra na célula que originalmente tinha mais moedas no caso de o número total de moedas é estranho.
a) É possível que todas as células contenham o mesmo número de moedas (ou seja, 13) após um número finito de lances?
b) Quais são as condições necessárias e suficientes para um tabuleiro 5 x 5 cujas 25 células contêm cada um um número diferente de moedas de ouro entre 1 e 25 para ser convertido em um tabuleiro com o mesmo número de moedas em cada célula após um número finito de movimentos ?
Respostas
Eu descobri a parte a):
A igualdade é realmente possível.
Aqui está o meu embaralhamento na grade:
Aqui está o lapso de tempo:
E aqui está o programa que codifiquei com python para a ferramenta no gif. Basta executar 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 a parte b), posso ou não saber. Eu vou olhar mais fundo nisso.
Esta não é uma resposta completa, mas talvez outra pessoa possa usá-la para uma prova completa.
Parte (a).
Para algumas grades, é possível. O exemplo mais simples simplesmente tem cada par de números que somam$26$adjacentes um ao outro. Por exemplo, cubra o 5x5 com 12 dominós, deixando um quadrado vazio. Colocar$13$ naquele quadrado vazio, e os pares $(1,25)$, $(2,24)$, ..., $(12,14)$no dominó. Ao combinar cada par de dominó, isso obviamente pode se tornar todos$13$ em doze movimentos.
Resposta parcial para a parte (b).
Deixei $x_i$ para $i=1$ para $25$ ser os valores atuais no quadro e considerar a soma da distância quadrada para $13$:
$$D=\sum_{i=1}^{25} (x_i-13)^2$$
É bastante fácil mostrar que cada movimento que realmente muda os valores no tabuleiro reduzirá o valor de $D$:
Prova: Suponha que aplicamos um movimento aos valores$a+b$ e $a-b$. Antes da mudança, eles contribuem$(a+b-13)^2+(a-b-13)^2$ à soma $D$. Após a movimentação, ambas as células têm valor$a$ e contribuir $2(a-13)^2$. Portanto$D$ é reduzido por: $$(a+b-13)^2+(a-b-13)^2-2(a-13)^2 = 2b^2$$
o que é positivo. Você também pode verificar se aplicar um movimento para$a+1+b$ e $a-b$ Irá reduzir $D$ de $2b(b+1)$.
Enquanto houver movimentos reais disponíveis, ou seja, enquanto houver células adjacentes que diferem por$2$ ou mais, $D$pode ser reduzido. Quando$D$ é zero, o quebra-cabeça está resolvido porque todas as células contêm $13$.
No entanto, surge um problema quando todas as células adjacentes diferem por$1$ou menos. Nesse estado, não há mais movimentos reais e não é necessariamente o caso de todas as células serem iguais. Você poderia ter, por exemplo, um$12$ e um $14$ isolados uns dos outros com o resto todos $13$. Você quer evitar isso, é claro, mas ainda não descobri se isso é sempre possível.
Um ponto de partida para a parte (b): vamos considerar algumas placas menores. Vou normalizar o valor médio da moeda para 0 e tentar analisar as configurações iniciais arbitrárias em que a soma das moedas é 0.
2x2:
Em um tabuleiro 2x2, todos os quadrados são vizinhos de todos os outros quadrados. Em qualquer um desses tabuleiros, todas as configurações iniciais podem ser resolvidas - o único tabuleiro onde nenhum movimento pode ser feito é o tabuleiro só com 0s.
1x3:
Uma placa 1x3 é mais interessante. Vamos trabalhar para trás a partir do estado final, (0,0,0). Os únicos predecessores possíveis são (A, -A, 0) e seu reverso, para inteiros diferentes de zero A. Os únicos predecessores possíveis desse estado ocorrem quando A = + - 1, e são da forma (-1, B + 1, -B), onde B é um número inteiro positivo e negação e reverso dessa sequência. Independentemente de B, não há mais predecessores, porque um estado só tem predecessores se tiver duas células adjacentes que diferem por 0 ou 1.
Portanto,
No 1x3, um estado é solucionável se e somente se tiver um 0 em uma célula externa (não central) ou tiver um +/- 1 em uma célula externa e a célula do meio for de sinal oposto.
Esperançosamente, podemos estender a solução 1x3 para uma solução 1x4, ou talvez 4 ciclos. Esse pode ser um problema mais natural de se pensar em gráficos arbitrários do que em gráficos de xadrez especificamente.
Resposta conjecturada para b)
Vamos subtrair 13 de todos os números por conveniência.
Uma posição é estritamente desequilibrada se houver uma divisão em duas peças conectadas de modo que
1. não há sequência de movimentos que transfere massa entre as duas peças 2. as somas $s$ e $-s$ sobre cada uma das duas peças não são zero
Obviamente, uma posição estritamente desequilibrada é invencível.
Uma posição é desequilibrada se houver uma divisão em duas peças conectadas de modo que
as somas $s$ e $-s$ sobre cada uma das duas peças não são zero e não há sequência de movimentos que transfere $s$ ou mais unidades de massa entre os dois.
Como uma posição desequilibrada acabará por simplificar em uma posição estritamente desequilibrada, ela também não pode ser vencida.
Também é óbvio que toda posição invencível acabará se simplificando em uma posição estritamente desequilibrada.
O que gostaríamos de estabelecer é o seguinte
Conjectura: toda posição invencível é desequilibrada.
ou equivalente,
Variante: Se uma posição não estiver desequilibrada, existe um movimento de forma que a posição resultante também não seja desequilibrada.
Isso parece bastante plausível para mim, mas não fui capaz de provar.
Observe que a conjectura é errada para placas muito pequenas, como 4x1: A posição -1,5, -5,1 não é desequilibrada, mas cada um dos três movimentos possíveis cria uma posição desequilibrada devido ao overshooting. Se, no entanto, incorporarmos esse padrão em um espaço maior e zero-pad, o 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
Concluí em 32 movimentos, conforme mostrado na imagem em anexo.
