L'uguaglianza è possibile?

Oct 30 2020

Ciascuna delle celle di una scacchiera 5 x 5 contiene un numero diverso di monete d'oro compreso tra 1 e 25, come mostrato di seguito.

Una mossa consiste nel prendere tutte le monete in due celle adiacenti (verticalmente, orizzontalmente o diagonalmente) e dividerle equamente tra quelle due celle, posizionando una moneta extra nella cella che originariamente aveva il maggior numero di monete nel caso in cui il numero totale di monete è strano.

a) È possibile che tutte le celle contengano lo stesso numero di monete (cioè 13) dopo un numero finito di mosse?

b) Quali sono le condizioni necessarie e sufficienti per un tabellone 5 x 5 le cui 25 celle contengono ciascuna un diverso numero di monete d'oro compreso tra 1 e 25 per essere convertibile in un tabellone con lo stesso numero di monete in ogni cella dopo un numero finito di mosse ?

Risposte

10 riskymysteries Oct 30 2020 at 19:32

Ho capito la parte a):

L'uguaglianza è davvero possibile.

Ecco il mio trascinamento nella griglia:

Ecco il lasso di tempo:

Ed ecco il programma che ho codificato con python per lo strumento nella gif. Esegui semplicemente questo codice:

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

Per la parte b), posso o non posso saperlo. Lo guarderò più a fondo.

5 JaapScherphuis Oct 30 2020 at 22:16

Questa non è una risposta completa, ma forse qualcun altro può usarla per una prova completa.

Parte (a).

Per alcune griglie è effettivamente possibile. L'esempio più semplice ha semplicemente ogni coppia di numeri che somma$26$adiacenti l'uno all'altro. Ad esempio, copri il 5x5 con 12 tessere del domino, lasciando un quadrato vuoto. Mettere$13$ in quella piazza vuota, e le coppie $(1,25)$, $(2,24)$, ..., $(12,14)$sui domino. Combinando ogni coppia di domino questo ovviamente può diventare tutto$13$ in dodici mosse.

Risposta parziale per la parte (b).

Permettere $x_i$ per $i=1$ per $25$ essere i valori correnti sulla lavagna e considerare la somma della distanza al quadrato $13$:
$$D=\sum_{i=1}^{25} (x_i-13)^2$$
È abbastanza facile mostrare che ogni mossa che cambia effettivamente i valori sulla scacchiera ridurrà il valore di $D$:
Dimostrazione: Supponiamo di applicare una mossa ai valori$a+b$ e $a-b$. Prima del trasloco questi contribuiscono$(a+b-13)^2+(a-b-13)^2$ alla somma $D$. Dopo lo spostamento, entrambe le celle hanno valore$a$ e contribuisci $2(a-13)^2$. Perciò$D$ è ridotto di: $$(a+b-13)^2+(a-b-13)^2-2(a-13)^2 = 2b^2$$
il che è positivo. Allo stesso modo puoi verificare che l'applicazione di una mossa a$a+1+b$ e $a-b$ ridurrà $D$ di $2b(b+1)$.

Finché ci sono mosse reali disponibili, cioè finché ci sono celle adiacenti che differiscono di$2$ o più, $D$può essere ridotto. quando$D$ è zero, il puzzle è risolto perché quindi tutte le celle contengono $13$.
Tuttavia, sorge un problema quando tutte le celle adiacenti differiscono di$1$o meno. In questo stato non ci sono più mosse reali e non è detto che tutte le celle siano uguali. Potresti avere ad esempio un file$12$ e a $14$ isolati gli uni dagli altri con il resto tutti $13$. Ovviamente vuoi evitarlo, ma non ho ancora capito se è sempre possibile.

2 isaacg Oct 31 2020 at 09:35

Un punto di partenza per la parte (b): consideriamo alcune schede più piccole. Normalizzerò il valore medio della moneta a 0 e cercherò di analizzare configurazioni iniziali arbitrarie in cui la somma delle monete è 0.

2x2:

Su una scacchiera 2x2, ogni quadrato confina con ogni altro quadrato. Su qualsiasi scheda di questo tipo, tutte le configurazioni di partenza sono risolvibili: l'unica scheda in cui non è possibile effettuare mosse è la scheda tutti 0.

1x3:

Una scheda 1x3 è più interessante. Lavoriamo all'indietro dallo stato finale, (0,0,0). Gli unici possibili predecessori sono (A, -A, 0) e il suo inverso, per interi diversi da zero A. Gli unici possibili predecessori di quello stato si verificano quando A = + - 1, e sono nella forma (-1, B + 1, -B), dove B è un numero intero positivo e negazione e inversione di quella sequenza. Indipendentemente da B, non ci sono più predecessori, perché uno stato ha predecessori solo se ha due celle adiacenti che differiscono di 0 o 1.

Quindi,

Nella 1x3, uno stato è risolvibile se e solo se ha uno 0 su una cella esterna (non centrale), o ha un +/- 1 su una cella esterna, e la cella centrale è di segno opposto.

Speriamo di poter estendere la soluzione 1x3 a una soluzione 1x4, o forse a 4 cicli. Questo potrebbe essere un problema a cui è più naturale pensare per i grafici arbitrari che per i grafici a scacchiera in particolare.

2 PaulPanzer Nov 01 2020 at 10:57

Risposta ipotizzata a b)

Sottraiamo 13 da tutti i numeri per comodità.

Una posizione è strettamente sbilanciata se esiste una divisione in due pezzi collegati tale che

1. non c'è sequenza di mosse che trasferisce la massa tra i due pezzi 2. le somme $s$ e $-s$ sopra ciascuno i due pezzi non sono zero

Ovviamente una posizione strettamente sbilanciata è impossibile da vincere.

Una posizione è sbilanciata se esiste una divisione in due pezzi collegati tale che

le somme $s$ e $-s$ su ciascuno dei due pezzi non sono zero e non c'è sequenza di mosse che trasferisce $s$ o più unità di massa tra le due.

Poiché una posizione sbilanciata alla fine si semplificherà in una posizione strettamente sbilanciata, è anche impossibile vincere.

È anche ovvio che ogni posizione impossibile da vincere finirà per semplificarsi in una rigorosamente sbilanciata.

Quello che vorremmo stabilire è quanto segue

Congettura: ogni posizione impossibile da vincere è sbilanciata.

o, equivalentemente,

Variante: se una posizione non è sbilanciata, esiste una mossa tale che anche la posizione risultante non è sbilanciata.

Mi sembra abbastanza plausibile, ma non sono stato in grado di dimostrarlo.

Nota che la congettura è sbagliata per tavole molto piccole come 4x1: la posizione -1,5, -5,1 non è sbilanciata ma ognuna delle tre possibili mosse crea una posizione sbilanciata a causa di overshooting. Se, tuttavia, incorporiamo questo modello in uno spazio più ampio e zero pad, il problema scompare: