Возможно ли равенство?
Каждая из ячеек доски 5 x 5 содержит разное количество золотых монет от 1 до 25, как показано ниже.
Ход состоит из взятия всех монет в два смежных (либо вертикально, горизонтально или по диагонали) клеток и расщепления их поровну между этими двумя клетками, помещая дополнительную монету в клетке , которые первоначально имели самые монеты в том случае, когда общее число монет нечетное.
а) Возможно ли, чтобы все ячейки содержали одинаковое количество монет (например, 13) после конечного числа ходов?
б) Каковы необходимые и достаточные условия для того, чтобы доска 5 x 5, каждая из 25 ячеек которой содержала разное количество золотых монет от 1 до 25, могла быть преобразована в доску с одинаковым количеством монет в каждой ячейке после конечного числа ходов. ?
Ответы
Я разобрался в части а):
Равенство действительно возможно.
Вот моя перетасовка по сетке:
Вот промежуток времени:
А вот программа, которую я написал на Python для инструмента на гифке. Просто запустите этот код:
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()
Что касается части b), я могу знать или не знать. Я посмотрю на это глубже.
Это не полный ответ, но, возможно, кто-то другой сможет использовать его для полного доказательства.
Часть (а).
Для некоторых сеток это действительно возможно. В простейшем примере каждая пара чисел в сумме равна$26$рядом друг с другом. Например, накройте поле 5x5 12 костяшками домино, оставив один квадрат пустым. Положить$13$ в этом пустом квадрате, а пары $(1,25)$, $(2,24)$, ..., $(12,14)$на домино. Комбинируя каждую пару домино, очевидно, можно получить все$13$ за двенадцать ходов.
Частичный ответ по части (б).
Позволять $x_i$ за $i=1$ к $25$ быть текущими значениями на доске и считать сумму квадратов расстояния до $13$:
$$D=\sum_{i=1}^{25} (x_i-13)^2$$
Довольно легко показать, что каждый ход, который фактически изменяет значения на доске, уменьшает значение $D$:
Proof: Допустим, мы применяем перемещение к значениям$a+b$ и $a-b$. Перед переездом они вносят свой вклад$(a+b-13)^2+(a-b-13)^2$ к сумме $D$. После хода обе ячейки имеют значение$a$ и внести свой вклад $2(a-13)^2$. Следовательно$D$ уменьшается на: $$(a+b-13)^2+(a-b-13)^2-2(a-13)^2 = 2b^2$$
что положительно. Аналогичным образом вы можете проверить, что применяя ход к$a+1+b$ и $a-b$ уменьшит $D$ по $2b(b+1)$.
Пока доступны реальные ходы, т.е. пока есть соседние ячейки, которые отличаются на$2$ или больше, $D$можно уменьшить. когда$D$ равен нулю, головоломка решена, потому что тогда все ячейки содержат $13$.
Однако проблема возникает, когда все соседние ячейки отличаются на$1$или менее. В этом состоянии больше нет реальных ходов, и не обязательно, что все клетки равны. Вы могли бы, например,$12$ и $14$ изолированы друг от друга с остальными $13$. Конечно, вы хотите этого избежать, но я еще не понял, всегда ли это возможно.
Отправная точка для части (b): давайте рассмотрим доски меньшего размера. Я собираюсь нормализовать среднюю стоимость монеты до 0 и попытаться проанализировать произвольные стартовые конфигурации, в которых сумма монет равна 0.
2x2:
На доске 2x2 каждый квадрат соседствует с каждым другим квадратом. На любых таких досках все исходные конфигурации решаемы - единственная доска, на которой нельзя делать ходы, - это доска со всеми нулями.
1x3:
Доска 1x3 интереснее. Давайте работать в обратном направлении от конечного состояния (0,0,0). Единственными возможными предшественниками являются (A, -A, 0) и его обратная сторона для ненулевых целых чисел A. Единственные возможные предшественники этого состояния возникают, когда A = + - 1, и имеют форму (-1, B + 1, -B), где B - положительное целое число, и отрицание и обратная последовательность этой последовательности. Независимо от B, предшественников больше нет, потому что у состояния есть предшественники, только если у него есть две соседние ячейки, которые отличаются на 0 или 1.
Таким образом,
В 1x3 состояние разрешимо тогда и только тогда, когда оно либо имеет 0 на внешней (не центральной) ячейке, либо имеет +/- 1 на внешней ячейке, а средняя ячейка имеет противоположный знак.
Надеюсь, мы сможем расширить решение 1x3 до решения 1x4 или, может быть, до 4-цикла. Это может быть проблемой, о которой более естественно думать для произвольных графов, чем для графов шахматной доски конкретно.
Предполагаемый ответ на вопрос b)
Для удобства вычтем 13 из всех чисел.
Позиция строго несбалансирована, если существует разделение на две соединенные части, такое что
1. нет последовательности ходов, которые передают массу между двумя частями 2. суммы $s$ и $-s$ по каждой две части не равны нулю
Очевидно, что в строго неуравновешенной позиции невозможно выиграть.
Позиция несбалансирована, если существует разделение на две соединенные части, так что
суммы $s$ и $-s$ по каждой из двух частей не равны нулю, и нет последовательности ходов, которая передает $s$ или больше единиц массы между ними.
Поскольку неуравновешенная позиция в конечном итоге превратится в строго несбалансированную, ее также нельзя выиграть.
Также очевидно, что любая невыигрываемая позиция со временем упростится до строго несбалансированной.
Мы хотели бы установить следующее
Гипотеза: любая невыигрываемая позиция несбалансирована.
или, что то же самое,
Вариант: если позиция не разбалансирована, существует такой ход, при котором результирующая позиция также не разбалансирована.
Мне это кажется вполне правдоподобным, но я не смог это доказать.
Обратите внимание, что эта гипотеза неверна для очень маленьких досок, таких как 4x1: позиция -1,5, -5,1 не является несбалансированной, но каждый из трех возможных ходов создает несбалансированную позицию из-за перескока. Однако если мы вставим этот шаблон в большее пространство и с нуля, проблема исчезнет:
-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
Я выполнил его за 32 хода, как показано на прикрепленном изображении.
