L'égalité est-elle possible?

Oct 30 2020

Chacune des cellules d'un tableau 5 x 5 contient un nombre différent de pièces d'or entre 1 et 25, comme indiqué ci-dessous.

Un mouvement consiste à prendre toutes les pièces dans deux cellules adjacentes (verticalement, horizontalement ou en diagonale) et à les répartir uniformément entre ces deux cellules, en plaçant une pièce supplémentaire dans la cellule qui avait à l'origine le plus de pièces dans le cas où le nombre total de pièces de monnaie est étrange.

a) Est-il possible que toutes les cellules contiennent le même nombre de pièces (c'est-à-dire 13) après un nombre fini de coups?

b) Quelles sont les conditions nécessaires et suffisantes pour qu'un plateau 5 x 5 dont les 25 cellules contiennent chacune un nombre différent de pièces d'or entre 1 et 25 soit convertible en un plateau avec le même nombre de pièces dans chaque cellule après un nombre fini de coups ?

Réponses

10 riskymysteries Oct 30 2020 at 19:32

J'ai compris la partie a):

L'égalité est en effet possible.

Voici mon parcours dans la grille:

Voici le laps de temps:

Et voici le programme que j'ai codé avec python pour l'outil dans le gif. Exécutez simplement ce 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()

Pour la partie b), je peux savoir ou non. Je vais y regarder de plus près.

5 JaapScherphuis Oct 30 2020 at 22:16

Ce n'est pas une réponse complète, mais peut-être que quelqu'un d'autre peut l'utiliser pour une preuve complète.

Partie (a).

Pour certaines grilles, c'est en effet possible. L'exemple le plus simple a simplement chaque paire de nombres qui se résume à$26$adjacents les uns aux autres. Par exemple, couvrez le 5x5 avec 12 dominos, en laissant un carré vide. Mettre$13$ dans ce carré vide, et les paires $(1,25)$, $(2,24)$, ..., $(12,14)$sur les dominos. En combinant chaque paire de dominos, cela peut évidemment devenir tout$13$ en douze coups.

Réponse partielle pour la partie (b).

Laisser $x_i$ pour $i=1$ à $25$ être les valeurs actuelles sur la carte, et considérer la somme de la distance quadratique à $13$:
$$D=\sum_{i=1}^{25} (x_i-13)^2$$
Il est assez facile de montrer que chaque mouvement qui modifie réellement les valeurs du tableau réduira la valeur de $D$:
Preuve: Supposons que nous appliquions un déplacement aux valeurs$a+b$ et $a-b$. Avant le déménagement, ils contribuent$(a+b-13)^2+(a-b-13)^2$ à la somme $D$. Après le déplacement, les deux cellules ont une valeur$a$ et contribuer $2(a-13)^2$. Par conséquent$D$ est réduit de: $$(a+b-13)^2+(a-b-13)^2-2(a-13)^2 = 2b^2$$
ce qui est positif. Vous pouvez également vérifier que l'application d'un déplacement à$a+1+b$ et $a-b$ Réduira $D$ par $2b(b+1)$.

Tant qu'il y a de vrais mouvements disponibles, c'est-à-dire tant qu'il y a des cellules adjacentes qui diffèrent de$2$ ou plus, $D$peut être réduit. Quand$D$ est zéro, le puzzle est résolu car toutes les cellules contiennent $13$.
Un problème se pose cependant lorsque toutes les cellules adjacentes diffèrent de$1$ou moins. Dans cet état, il n'y a plus de vrais mouvements, et ce n'est pas nécessairement le cas que toutes les cellules sont égales. Vous pourriez avoir par exemple un$12$ et un $14$ isolés les uns des autres avec le reste tout $13$. Vous voulez éviter cela bien sûr, mais je n'ai pas encore compris si cela est toujours possible.

2 isaacg Oct 31 2020 at 09:35

Un point de départ pour la partie (b): Considérons quelques planches plus petites. Je vais normaliser la valeur moyenne des pièces à 0 et essayer d'analyser les configurations de départ arbitraires où les pièces totalisent 0.

2x2:

Sur un plateau 2x2, chaque carré est voisin d'un autre carré. Sur ces cartes, toutes les configurations de départ peuvent être résolues - la seule carte où aucun mouvement ne peut être effectué est la carte all 0s.

1x3:

Une carte 1x3 est plus intéressante. Travaillons à rebours à partir de l'état final, (0,0,0). Les seuls prédécesseurs possibles sont (A, -A, 0) et son inverse, pour les entiers non nuls A. Les seuls prédécesseurs possibles de cet état se produisent lorsque A = + - 1, et sont de la forme (-1, B + 1, -B), où B est un entier positif, et négation et inverse de cette séquence. Indépendamment de B, il n'y a plus de prédécesseurs, car un état n'a de prédécesseurs que s'il a deux cellules adjacentes qui diffèrent de 0 ou 1.

Donc,

Dans le 1x3, un état est résoluble si et seulement s'il a soit un 0 sur une cellule extérieure (non centrale), soit il a un +/- 1 sur une cellule extérieure, et la cellule du milieu est de signe opposé.

J'espère que nous pourrons étendre la solution 1x3 à une solution 1x4, ou peut-être à 4 cycles. Cela peut être un problème auquel il est plus naturel de penser pour les graphiques arbitraires que pour les graphiques en damier en particulier.

2 PaulPanzer Nov 01 2020 at 10:57

Réponse hypothétique à b)

Soustrayons 13 de tous les nombres pour plus de commodité.

Une position est strictement déséquilibrée s'il existe une division en deux pièces connectées de telle sorte que

1. il n'y a pas de séquence de mouvements qui transfère la masse entre les deux pièces 2. les sommes $s$ et $-s$ sur chacun les deux morceaux ne sont pas nuls

De toute évidence, une position strictement déséquilibrée est impossible à gagner.

Une position est déséquilibrée s'il existe une division en deux pièces connectées de telle sorte que

les sommes $s$ et $-s$ sur chacune des deux pièces ne sont pas nulles et il n'y a pas de séquence de mouvements qui transfère $s$ ou plusieurs unités de masse entre les deux.

Comme une position déséquilibrée finira par se simplifier en une position strictement déséquilibrée, elle est également impossible à gagner.

Il est également évident que chaque position impossible à gagner finira par se simplifier en une position strictement déséquilibrée.

Ce que nous souhaitons établir est le suivant

Conjecture: chaque position impossible à gagner est déséquilibrée.

ou équivalent,

Variante: Si une position n'est pas déséquilibrée, il existe un mouvement tel que la position résultante n'est pas non plus déséquilibrée.

Cela me semble tout à fait plausible mais je n'ai pas été en mesure de le prouver.

Notez que la conjecture est fausse pour les très petites planches telles que 4x1: La position -1,5, -5,1 n'est pas déséquilibrée mais chacun des trois mouvements possibles crée une position déséquilibrée en raison d'un dépassement. Cependant, si nous intégrons ce motif dans un espace plus grand et un pad zéro, le problème disparaît: