Plansza i kamyki

[mol_ksiazkowy]

Na każdym polu kwadratowej szachownicy jest kamyk. Jeden Ruch to przesunięcie dwóch kamyków z pól oddalonych od siebie o dwa (w jednym rzędzie lub kolumnie) na pole pomiędzy nimi (na jednym polu może być dowolna ilość kamyków). Czy można tak ustalić kolejność Ruchów, by wszystkie kamyki znalazły się na jednym polu ?

[arek1357]

Czy ma ktoś sposób zejścia do jednego pola na szachownicy: 4x4

[kerajs]

Czy ma ktoś sposób zejścia do jednego pola na szachownicy: 4x4

Takie zejście nie jest możliwe.
Każdemu kamykowi przypisuję dwa indeksy: numer wiersza i kolumny na szachownicy ponumerowanej w pionie i poziomie od 1 do n (kamyki mają indeksy jak elementy w macierzy). Każdy ruch w poziomie powiększa o 1 pierwszy indeks jednego z kamieni i zmniejsza o 1 pierwszy indeks drugiego z kamieni, ergo: niezależnie od ilości ruchów suma pierwszych indeksów wszystkich kamieni się nie zmienia (gdyż i ruchy w pionie nie wpływają na pierwszy indeks). Jeśli istnieje pole na którym możliwe jest zgromadzenie wszystkich kamieni to musi ono mieć oba indeksy równe \(\displaystyle{ \frac{ n\sum_{i=1}^{n}i }{n^2}= \frac{n+1}{2}}\), czyli jest polem będącym środkiem szachownicy.
Dlatego w szachownicy 4x4, jak i każdej 2Nx2N zejście nie jest możliwe.


Jak znajdę trochę czasu to napiszę jak postępować aby wszystkie kamienie zeszły na środek dowolnej szachownicy (2N+1)x(2N+1)

[pesel]

Jeśli istnieje pole na którym możliwe jest zgromadzenie wszystkich kamieni to musi ono mieć oba indeksy równe , czyli jest polem będącym środkiem szachownicy.

No ale czy jeżeli istnieje pole będące środkiem szachownicy to da się na nim zgromadzić wszystkie kamienie?

[arek1357]

Sprawdzić dla szachownicy 5x5 , nie schodzi mi na jedno pole w przypadku 3x3 ładnie schodzi

[kerajs]

Sprawdzić dla szachownicy 5x5 , nie schodzi mi na jedno pole w przypadku 3x3 ładnie schodzi

W dowolnym rzędzie kamienie mają indeksy: (1,k), (2,k), (3,k), (4,k), (5,k) co uproszczę do:
1,2,3,4,5
Pierwszy ruch między kamieniami z pola 2 i 4 przesuwa je na pole 3 dając indeksy:
1,3,3,3,5
Kolejne ruchy:
2,2,3,3,5
2,2,3,4,4
2,3,3,3,4
3,3,3,3,3

Postępując tak z każdym rzędem, dostaje się po pięć kamieni na polach trzeciej kolumny.
Ta sama sekwencja ruchów użyta pięciokrotnie dla drugich indeksów sprowadzi wszystkie kamienie na pole (3,3)

Jeśli istnieje pole na którym możliwe jest zgromadzenie wszystkich kamieni to musi ono mieć oba indeksy równe , czyli jest polem będącym środkiem szachownicy.

No ale czy jeżeli istnieje pole będące środkiem szachownicy to da się na nim zgromadzić wszystkie kamienie?

Gdy pisałem cytowane zdanie, będące jedynie odpowiedzią na pytanie Arka, to jeszcze nie wiedziałem czy we wszystkich szachownicach o nieparzystym boku można kamienie sprowadzić na środkowe pole. Ostatnie zdanie poprzedniego postu dopisałem później, najwyraźniej tuż przed Pańskim postem.




W szachownicy (2N-1)x(2N-1) kamienie w dowolnym rzędzie mają indeksy: (1,k), (2,k),..., (N-4), (N-3,k), (N-2,k), (N-1,k), (N,k), (N+1,k), (N+2,k), (N+3,k), (N+4),..., (2N-2,k), (2N-1,k) co uproszczę do:
1,2,...,N-4,N-3,N-2,N-1,N,N+1,N+2,N+3,N+4,...,2N-2,2N-1

Pierwszy ruch między kamieniami z pola N-1 i N+1 przesuwa je na pole N dając indeksy:
1,2,...,N-4,N-3,N-2,N,N,N,N+2,N+3,N+4,...,2N-2,2N-1
Kolejne ruchy (po dwa symetryczne względem N):
1,2,...,N-4,N-3,N-1,N-1,N,N+1,N+1,N+3,N+4,...,2N-2,2N-1
1,2,...,N-4,N-2,N-2,N-1,N,N+1,N+2,N+2,N+4,...,2N-2,2N-1
1,2,...,N-3,N-3,N-2,N-1,N,N+1,N+2,N+3,N+3,...,2N-2,2N-1
.....
1,3,3,...,N-4,N-3,N-2,N-1,N,N+1,N+2,N+3,N+4,...,2N-3,2N-3,2N-1
2,2,3...N-4,N-3,N-2,N-1,N,N+1,N+2,N+3,N+4,...,2N-3,2N-2,2N-2
Ta procedura przesunęła skrajne kamienie na pole o 1 bliższe środka

Ukryta treść:    

N=9
1,2,3,4,5,6,7,8,9
1,2,3,5,5,5,7,8,9
1,2,4,4,5,6,6,8,9
1,3,3,4,5,6,7,7,9
2,2,3,4,5,6,7,8,8

Powtarzając powyższą procedurę (odpowiednio pomniejszoną o ostatnie ruchy) odpowiednią ilość razy, można przesunąć dwa skrajne kamienie na środek rzędu.

Ukryta treść:    

2,2,3,5,5,5,7,8,8
2,2,4,4,5,6,6,8,8
2,3,3,4,5,6,7,7,8

2,3,3,5,5,5,7,7,8
2,3,4,4,5,6,6,7,8

2,3,4,5,5,5,6,7,8

Taka seria procedur daje (pomijając dwa nadmiarowe kamienie na środkowym polu w rzędzie) rząd kamieni o długości 2N-3.
Po N-1 seriach procedur wszystkie kamienie trafią na środkowe pole w rzędzie.

Ukryta treść:    

2,3,5,5,5,5,5,7,8
2,4,4,5,5,5,6,6,8
3,3,4,5,5,5,6,7,7
3,3,5,5,5,5,5,7,7
3,4,4,5,5,5,6,6,7
3,4,5,5,5,5,5,6,7

3,5,5,5,5,5,5,5,7
4,4,5,5,5,5,5,6,6
4,5,5,5,5,5,5,5,6

5,5,5,5,5,5,5,5,5

Postępując tak z każdym rzędem, dostaje się po 2N-1 kamieni na polach N-tej kolumny.
Te same sekwencje procedur użyte 2N-1 krotnie dla drugich indeksów sprowadzą wszystkie kamienie na środkowe pole szachownicy.

[arek1357]

Najkrócej można by rzec, że po każdym cyklu ruchowym poziomo lub pionowo kamyki muszą być ustawione symetrycznie względem prostych przechodzących przez środek planszy, każdy cykl redukuje z kamyków dwie skrajne krawędzie..., a te co zostają muszą być ułożone symetrycznie i wtedy mamy gwarancję sukcesu...
Tak się dziać może tylko przy N nieparzystych...

[pesel]

Wydaje mi się, że można to zagadnienie uogólnić na prostokątną planszę \(\displaystyle{ (2N+1)\times(2M+1)}\).

[arek1357]

Bingo