15
$\begingroup$

Each of the cells of a 5 x 5 board contains a different number of gold coins between 1 and 25, as shown below.

A move consists of taking all the coins in two adjacent (either vertically, horizontally, or diagonally) cells and splitting them evenly among those two cells, placing an extra coin in the cell which originally had the most coins in the case that the total number of coins is odd.

a) Is it possible for all the cells to contain the same number of coins (i.e. 13) after a finite number of moves?

b) What are necessary and sufficient conditions for a 5 x 5 board whose 25 cells contain each a different number of gold coins between 1 and 25 to be convertible into a board with the same number of coins in every cell after a finite number of moves?

enter image description here

$\endgroup$
2
  • $\begingroup$ I will put an answer as a comment. From the formula $((n+1)*n )/2$ we obtain twenty-five squares with 13 coins each. From the combinations (25,1) (24,2) (23,3) (22,4) (21,5) (20,6) (19,,7) (18,8) (17,9) (16,10) (15,11) (14,12) 13. we conclude we need only twelve moves. $\endgroup$ – Vassilis Parassidis Oct 31 '20 at 0:35
  • $\begingroup$ Do you have reason to believe that there exists an initial arrangement that cannot be solved? $\endgroup$ – Daniel Mathias Nov 5 '20 at 14:31
10
$\begingroup$

I figured out part a):

Equality is indeed possible.

Here is my shuffling through the grid:

enter image description here

Here is the time lapse:

enter image description here

And here is the program I coded with python for the tool in the gif. Simply run this code:

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()

For part b), I may or may not know. I'll look deeper into it.

$\endgroup$
8
  • 1
    $\begingroup$ PyGame... eurgh. Wish you would've use tkinter or something better for Python graphic-y stuff :):) $\endgroup$ – Voldemort's Wrath Oct 30 '20 at 13:09
  • 1
    $\begingroup$ @Voldemort'sWrath Why don't you think pygame is good for python graphics? $\endgroup$ – risky mysteries Oct 30 '20 at 15:04
  • 1
    $\begingroup$ It's very inefficient and just generally bad. Also Python is not designed for graphical things. $\endgroup$ – Voldemort's Wrath Oct 30 '20 at 15:24
  • 2
    $\begingroup$ @Voldemort'sWrath It worked didn’t it, I thought it worked just fine, pretty good in fact. What difference does it make? $\endgroup$ – Cotton Headed Ninnymuggins Oct 30 '20 at 16:28
  • 2
    $\begingroup$ @Voldemort'sWrath I'm not a programmer, so I wouldn't know ;) $\endgroup$ – Cotton Headed Ninnymuggins Oct 30 '20 at 16:58
5
$\begingroup$

This not a full answer, but maybe someone else can use it for a full proof.

Part (a).

For some grids it is indeed possible. The simplest example simply has every pair of numbers that sums to $26$ adjacent to each other. For example, cover the 5x5 with 12 dominoes, leaving one square empty. Put $13$ in that empty square, and the pairs $(1,25)$, $(2,24)$, ... , $(12,14)$ on the dominoes. By combining each domino pair this obviously can become all $13$ in twelve moves.

Partial answer for part (b).

Let $x_i$ for $i=1$ to $25$ be the current values on the board, and consider the sum of squared distance to $13$:
$$D=\sum_{i=1}^{25} (x_i-13)^2$$
It is fairly easy to show that every move that actually changes the values on the board will reduce the value of $D$:
Proof: Suppose we apply a move to the values $a+b$ and $a-b$. Before the move these contribute $(a+b-13)^2+(a-b-13)^2$ to the sum $D$. After the move both cells have value $a$ and contribute $2(a-13)^2$. Therefore $D$ is reduced by: $$(a+b-13)^2+(a-b-13)^2-2(a-13)^2 = 2b^2$$
which is positive. You can similarly check that applying a move to $a+1+b$ and $a-b$ will reduce $D$ by $2b(b+1)$.

As long as there are real moves available, i.e. as long as there are adjacent cells that differ by $2$ or more, $D$ can be reduced. When $D$ is zero, the puzzle is solved because then all cells contain $13$.
A problem arises however when all adjacent cells differ by $1$ or less. In this state there are no more real moves, and it is not necessarily the case that all cells are equal. You could have for example a $12$ and a $14$ isolated from each other with the rest all $13$. You want to avoid this of course, but I have not yet figured out if that is always possible.

$\endgroup$
1
  • 1
    $\begingroup$ The problem with that semi-invariant is that it can't tell apart an isolated 12/14 from an adjacent 12/14. For a full solution one probably needs to find something that somehow factors in spatial arrangement. $\endgroup$ – Paul Panzer Oct 30 '20 at 15:47
2
$\begingroup$

A starting point for part (b): Let's consider some smaller boards. I'm going to normalize the average coin value to 0, and try to analyze arbitrary starting configurations where the coins sum to 0.

2x2:

On a 2x2 board, every square neighbors every other square. On any such boards, all starting configurations are solvable - the only board where no moves can be made is the all 0s board.

1x3:

A 1x3 board is more interesting. Let's work backwards from the final state, (0,0,0). The only possible predecessors are (A,-A,0) and its reverse, for nonzero integers A. The only possible predecessors of that state occur when A=+-1, and are of the form (-1,B+1,-B), where B is a positive integer, and negation and reverse of that sequence. Regardless of B, there are no more predecessors, because a state only has predecessors if it has two adjacent cells that differ by 0 or 1.

Thus,

In the 1x3, a state is solvable if and only if it either has a 0 on an outside (non-center) cell, or it has a +/-1 on an outside cell, and the middle cell is of opposite sign.

Hopefully we can extend the 1x3 solution to a 1x4 solution, or maybe a 4-cycle. This might be a problem that is more natural to think about for arbitrary graphs than for checkerboard graphs specifically.

$\endgroup$
2
$\begingroup$

Conjectured answer to b)

Let us subtract 13 from all numbers for convenience.

A position is strictly unbalanced if there exists a split into two connected pieces such that

1. there is no sequence of moves that transfers mass between the two pieces 2. the sums $s$ and $-s$ over each the two pieces are not zero

Obviously, a strictly unbalanced position is unwinnable.

A position is unbalanced if there exists a split into two connected pieces such that

the sums $s$ and $-s$ over each of the two pieces are not zero and there is no sequence of moves that transfers $s$ or more units of mass between the two.

As an unbalanced position will eventually simplify into a strictly unbalanced one it is also unwinnable.

It is also obvious that every unwinnable position will eventually simplify into a strictly unbalanced one.

What we would like to establish is the following

Conjecture: Every unwinnable position is unbalanced.

or, equivalently,

Variant: If a position is not unbalanced there exists a move such that the resulting position also is not unbalanced.

This feels quite plausible to me but I haven't been able to prove it.

Note that the conjecture is wrong for very small boards such as 4x1: The position -1,5,-5,1 is not unbalanced but each of the three possible moves creates an unbalanced position due to overshooting. If we, however, embed this pattern in a larger space and zero-pad, the problem goes away:

-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 
$\endgroup$
6
  • $\begingroup$ I like the idea, but I don't think it quite works. I think the following is a counterexample. On a diagonal, place 1,1,-4,1,1. Fill the rest with 0s. It's possible to balance either pair of ones, but it's not possible to balance both simultaneously - after the first move, it becomes unbalanced. However, if we allow the regions to be disconnected in the definition of unbalanced, I think that fixes it. $\endgroup$ – isaacg Nov 3 '20 at 7:04
  • $\begingroup$ @isaacg I don't think that's a counterexample: Choose as the two regions a square that reaches from the corner to the -4 excluding the four 1's and the L-shaped complement. $\endgroup$ – Paul Panzer Nov 3 '20 at 7:39
  • $\begingroup$ @isaacg That said I wouldn't insist on connectedness. I'd be happy with whichever makes proving the conjecture easier. $\endgroup$ – Paul Panzer Nov 3 '20 at 7:52
  • $\begingroup$ Actually, now that I look into it further, I think that this is a counterexample, even to the disconnected version of unbalancedness. Take a look at this sequence of moves, which I believe shows that this is not unbalanced relative to your square region, or any other region that includes the 4 but no 1s: docs.google.com/spreadsheets/d/… $\endgroup$ – isaacg Nov 3 '20 at 15:02
  • $\begingroup$ @isaacg Well done! But still no counterexample I believe because we can fatten the square by one column and one row, so it includes the two 1's closest to the -4. $\endgroup$ – Paul Panzer Nov 3 '20 at 15:49
2
+50
$\begingroup$

I completed it in 32 moves, as shown in the attached image.

enter image description here

$\endgroup$
1
  • $\begingroup$ A separate question asking for minimum moves is here. $\endgroup$ – Daniel Mathias Nov 5 '20 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.