Eşitlik mümkün mü?
5 x 5'lik bir tahtanın her bir hücresi, aşağıda gösterildiği gibi 1 ile 25 arasında farklı sayıda altın para içerir.
Bir hareket , tüm madeni paraları iki bitişik (dikey, yatay veya çapraz olarak) hücreye alıp bu iki hücre arasında eşit olarak bölmek ve toplam sayı olması durumunda başlangıçta en fazla bozuk paraya sahip olan hücreye fazladan bir bozuk para koymaktan oluşur. paralar tuhaf.
a) Sonlu sayıda hamle sonrasında tüm hücrelerin aynı sayıda jeton (yani 13) içermesi mümkün müdür?
b) 25 hücresinde her biri 1 ile 25 arasında farklı sayıda altın sikke içeren 5 x 5'lik bir tahtanın, sınırlı sayıda hareketten sonra her hücrede aynı sayıda madeni para bulunan bir tahtaya dönüştürülebilmesi için gerekli ve yeterli koşullar nelerdir? ?
Yanıtlar
A) bölümünü anladım:
Eşitlik gerçekten mümkündür.
İşte benim ızgarada karıştırmam:
İşte zaman atlama:
Ve işte gifteki araç için python ile kodladığım program. Sadece şu kodu çalıştırın:
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ölüm b) için bilebilirim veya bilmeyebilirim. Daha derinlemesine bakacağım.
Bu tam bir cevap değil, ama belki bir başkası tam bir kanıt için kullanabilir.
Bölüm (a).
Bazı şebekeler için bu gerçekten mümkündür. En basit örnek, toplamı olan her sayı çiftine sahiptir.$26$birbirine bitişik. Örneğin, 5x5'i 12 domino ile kaplayın ve bir kareyi boş bırakın. Koymak$13$ o boş karede ve çiftler $(1,25)$, $(2,24)$, ..., $(12,14)$dominolarda. Her bir domino çiftini birleştirerek, bu açıkça$13$ on iki hamlede.
(B) bölümü için kısmi cevap.
İzin Vermek $x_i$ için $i=1$ -e $25$ tahtadaki mevcut değerler olsun ve mesafenin karesinin toplamını düşünün $13$:
$$D=\sum_{i=1}^{25} (x_i-13)^2$$
Tahtadaki değerleri gerçekten değiştiren her hareketin değerini düşüreceğini göstermek oldukça kolaydır. $D$:
Kanıt: Değerlere bir hareket uyguladığımızı varsayalım$a+b$ ve $a-b$. Taşınmadan önce bunlar katkıda bulunur$(a+b-13)^2+(a-b-13)^2$ toplamına $D$. Hareketten sonra her iki hücrenin de değeri var$a$ ve katkıda bulun $2(a-13)^2$. Bu nedenle$D$ şu oranda azaltılır: $$(a+b-13)^2+(a-b-13)^2-2(a-13)^2 = 2b^2$$
bu olumlu. Benzer şekilde bir hamle uygulayıp uygulamadığını kontrol edebilirsiniz.$a+1+b$ ve $a-b$ Azaltacak $D$ tarafından $2b(b+1)$.
Mevcut gerçek hareketler olduğu sürece, yani birbirlerinden farklı olan bitişik hücreler olduğu sürece$2$ yada daha fazla, $D$azaltılabilir. Ne zaman$D$ sıfır, bulmaca çözüldü çünkü tüm hücreler $13$.
Bununla birlikte, tüm bitişik hücreler birbirinden farklı olduğunda bir sorun ortaya çıkar.$1$veya daha az. Bu durumda artık gerçek hareketler yoktur ve tüm hücrelerin eşit olması zorunlu değildir. Örneğin bir$12$ ve bir $14$ geri kalanıyla birbirinden izole $13$. Elbette bundan kaçınmak istiyorsunuz, ancak bunun her zaman mümkün olup olmadığını henüz anlamadım.
Bölüm (b) için bir başlangıç noktası: Şimdi daha küçük tahtaları ele alalım. Ortalama jeton değerini 0'a normalleştireceğim ve madeni paraların toplamının 0 olduğu keyfi başlangıç yapılandırmalarını analiz etmeye çalışacağım.
2x2:
2x2'lik bir tahtada, her kare diğer bir kareye komşu. Bu tür kartlarda, tüm başlangıç yapılandırmaları çözülebilir - hiçbir hareketin yapılamadığı tek kart, tüm 0'lar kartıdır.
1x3:
1x3 tahta daha ilginçtir. Son durumdan (0,0,0) geriye doğru çalışalım. Olası tek öncüller (A, -A, 0) ve sıfır olmayan tamsayılar için tersidir. Bu durumun olası tek öncülleri A = + - 1 olduğunda ve (-1, B + 1, -B), burada B pozitif bir tam sayıdır ve bu dizinin olumsuz ve tersi. B'den bağımsız olarak, daha fazla öncül yoktur, çünkü bir durumun yalnızca 0 veya 1 farklılık gösteren iki bitişik hücreye sahip olması durumunda öncülleri vardır.
Böylece,
1x3'te, bir durum ancak ve ancak bir dış (merkez olmayan) hücrede bir 0'a sahipse veya bir dış hücrede bir +/- 1'e sahipse ve orta hücre zıt işarete sahipse çözülebilir.
Umarım 1x3 çözümü 1x4 çözüme veya belki 4 döngüye genişletebiliriz. Bu, özellikle dama tahtası grafiklerinden ziyade gelişigüzel grafikler için düşünülmesi daha doğal bir sorun olabilir.
B) 'ye varsayılan cevap
Kolaylık sağlamak için tüm sayılardan 13 çıkaralım.
Bir pozisyon, birbirine bağlı iki parçaya bölünme varsa , kesinlikle dengesizdir .
1. iki parça arasında kütleyi aktaran hareketler dizisi yoktur 2. toplamlar $s$ ve $-s$ her birinin üzerinde iki parça sıfır değil
Açıkçası, kesinlikle dengesiz bir pozisyon kazanılamaz.
Bir pozisyon dengesizdir , öyle ki iki bağlantılı parçaya bölünme varsa,
toplamlar $s$ ve $-s$ iki taştan her birinin üzerinde sıfır değildir ve transfer eden hareketler dizisi yoktur. $s$ veya ikisi arasında daha fazla kütle birimi.
Dengesiz bir pozisyon, sonunda kesinlikle dengesiz bir pozisyona dönüşeceğinden, aynı zamanda kazanılamaz.
Ayrıca, kazanılamaz her pozisyonun eninde sonunda kesinlikle dengesiz bir pozisyona dönüşeceği de açıktır.
Kurmak istediğimiz şey şudur:
Varsayım: Kazanılamayan her konum dengesizdir.
Veya eşdeğer olarak,
Varyasyon: Bir pozisyon dengesiz değilse, ortaya çıkan pozisyon da dengesiz olmayacak şekilde bir hareket vardır.
Bu bana oldukça makul geliyor ama bunu ispatlayamadım.
4x1 gibi çok küçük tahtalar için varsayımın yanlış olduğuna dikkat edin: -1,5, -5,1 konumu dengesiz değildir, ancak olası üç hareketin her biri, aşırı atış nedeniyle dengesiz bir konum oluşturur. Bununla birlikte, bu kalıbı daha geniş bir alana ve sıfır pedine yerleştirirsek, sorun ortadan kalkar:
-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
Ekteki resimde görüldüğü gibi 32 hamlede tamamladım.
