nauki ścisłe
Autor: Marek Penszko | dodano: 2013-04-22
Superpozycje i lustra

Choć szachy trudno nazwać grą matematyczną, to między królową nauk
a królewską grą można doszukać się wielu powiązań.

Z reguły są to związki formalne, czyli dotyczące planszy i figur, a nie samej rozgrywki. Zagadnienia z nimi związane można wprawdzie rozpatrywać, nie odwołując się do szachów, jednak z grą jest bardziej obrazowo, ciekawiej, a czasami prościej. Typowy przykład stanowi stare zadanie o liczbie ziaren zboża, umieszczanych na szachownicy w następujący sposób: jedno na pierwszym polu, dwa na drugim, cztery na trzecim itd. – na każdym następnym dwukrotnie więcej niż na poprzednim. Trudno uwierzyć, że do pokrycia w ten sposób 64 pól nie starczyłoby zboża na Ziemi, choć nietrudno obliczyć sumę wyrazów postępu geometrycznego.

Inny przykład – problem z zakresu geometrii kombinatorycznej lub teorii grafów: kwadrat podzielono na 64 kwadratowe pola (8×8); ile co najmniej pól należałoby oznaczyć, aby w każdym rzędzie równoległym do brzegu lub do przekątnej kwadratu znalazło się jedno oznaczone pole? Byłoby to zapewne bardzo niszowe zadanie, gdyby nie jego szachowa modyfikacja popularna od kilkuset lat: ustaw na szachownicy cztery hetmany tak, aby atakowały wszystkie wolne pola. Dopiero w połowie XIX wieku wykazano, a właściwie mozolnie sprawdzono, że nie jest to możliwe. Prosty dowód, że cztery hetmany nie wystarczą, nie jest znany, ale jakkolwiek by ich nie rozmieszczać, zawsze co najmniej dwa pola pozostaną nieatakowane. Ustawień całkowicie różnych (z dokładnością do odbić i obrotów) z parą niezagrożonych pól jest osiem. Wszystkie można przedstawić na dwóch diagramach (rys. 1) – na każdym znajdują się nałożone na siebie cztery ustawienia w takich pozycjach (obrócone lub/i odbite), że w żadne pole nie trafiają dwa oznaczenia. Takie „bezkolizyjne” nałożenie nazwiemy superpozycją rozłączną. Ustawienia na rys.1 różnią się kolorami; w nieatakowanych polach są gwiazdki.

 

Rys. 1

 
Zadanie o czterech hetmanach należy do łamigłówek matematyczno-szachowych, polegających na takim rozmieszczaniu na szachownicy określonych figur, aby ich układ spełniał podane warunki. Zalicza się do nich także bardziej znane XIX-wieczne zadanie, w którym chodzi o ustawienie na szachownicy ośmiu hetmanów tak, by żaden nie atakował innego. Rozwiązać je łatwo, choć to zajęcie żmudne i schematyczne – idealne, by napisać algorytm i skorzystać z komputera, więc często pojawia się jako ćwiczenie dla początkujących programistów. Komputer błyskawicznie znajduje 12 całkowicie różnych rozwiązań (rys. 2).

 

Rys. 2

Przed 60 laty w Stanach Zjednoczonych w sklepach z zabawkami można było kupić grę dla jednej osoby zwaną hoodoo. Obejmowała ona kilka łamigłówek, polegających na umieszczaniu kolorowych kołeczków w otworach kwadratowej planszy. W najtrudniejszej były 64 kołeczki, po osiem w ośmiu różnych kolorach, a układ 64 otworów był taki, jak pól szachownicy. Wszystkie kołeczki należało rozmieścić tak, by w żadnym rzędzie równoległym do brzegów lub przekątnej planszy nie było dwóch w takim samym kolorze. Zabawa nawet jak na lata 50. nie była zbyt wyszukana, ale pikanterii dodawała jej nagroda – na pierwszą osobę, która uporałaby się z zadaniem, czekał… milion dolarów. W wersji szachowej reguły brzmiałyby krótko i zwięźle: znajdź superpozycję rozłączną ośmiu rozwiązań problemu ośmiu hetmanów. Zapewne wiele czasu stracono na bezowocne zmagania z tą kuszącą milionem łamigłówką, bowiem mało kto wiedział, że już w roku 1914 angielski prawnik i matematyk-amator Thorold Gosset wykazał w prosty i elegancki sposób, że rozwiązanie nie istnieje. Dowód sprowadza się do oznaczenia na szachownicy 20 pól (rys. 3).

 

 Rys. 3

 

 

 Rys. 4

Co najmniej trzy z tych pól zajmują hetmany w każdym z 12 rozwiązań na rys. 2. Rozłączna superpozycja nawet siedmiu rozwiązań nie będzie więc możliwa, bo na oznaczonych 20 polach znajdzie się przynajmniej 21 hetmanów. Zatem nałożyć na siebie można co najwyżej sześć rozwiązań, które zajmą 48 pól. Przykład jednej z takich superpozycji przedstawiony jest na rys. 4. Wśród sześciu składających się na nią rozwiązań są tylko dwa różne, odpowiednio odbite lub/i obrócone – cztery „2” i dwa „10” z rys. 2. Zadanie okazuje się znacznie trudniejsze po dodaniu warunku, aby całkowicie różne były wszystkie nałożone rozwiązania. Wówczas niemożliwa jest nie tylko rozłączna superpozycja sześciu rozwiązań, ale prawdopodobnie także pięciu. Nie sposób nawet „bezkolizyjnie” nałożyć na siebie niektórych par rozwiązań, np. „5” i „6” lub „6” i „12”, mimo uwzględniania odbić i obrotów. Można natomiast utworzyć trzy rozłączne superpozycje, obejmujące wszystkie 12 rozwiązań – po cztery rozwiązania w każdej, czyli przedstawić wszystkie rozwiązania hetmańskiego problemu na trzech diagramach (rys. 5; hetmany zastąpiono liczbami odpowiadającymi numerom rozwiązań na rys. 2).

 

Rys. 5

Wracając do gry hoodoo, a ściślej do jej uogólnionej wersji (plansza n×n) – w roku 1918 matematyk węgierski George Pólya wykazał, że rozwiązanie (wypełnienie hetmanami wszystkich pól) nie istnieje nie tylko dla n=8, ale dla każdego n podzielnego przez 2 lub 3. Później okazało się, że wnioski Pólyi są prawdziwe tylko dla nn=5, 7 i większe od 10) ufundowanie przez producenta nagrody miliona dolarów oznaczałoby więc jego bankructwo.

Inne ciekawe zagadnienie związane z problemem ośmiu hetmanów dotyczy wariantu tego zadania, w którym jakby zwiększony jest zasięg ataku figur. Dzieje się tak dzięki „lustru” umieszczonemu przy jednym brzegu szachownicy w odległości równej połowie szerokości pola. Ukośna linia ataku odbija się od niego jak promień i po odbiciu może trafić w innego hetmana. Podstawowa zasada jest taka, jak w pierwowzorze: osiem hetmanów trzeba rozlokować tak, aby sobie nie zagrażały. Rozwiązania nietrudno znaleźć, ustawiając kolejno lustro przy każdym boku każdego z 12 rozwiązań na rys. 2. Na przykład, piąte rozwiązanie z lustrem z prawej strony odpadnie, bo dwie pary hetmanów zagrażają sobie po odbiciu (linie przerywane na rys. 6); jeśli jednak lustro umieścimy u dołu, żadnego zagrożenia nie będzie. W sumie pozostanie pięć rozwiązań: 5 i 9 z lustrem u dołu oraz 7, 9 i 11 z lustrem z lewej strony.

 

Rys. 6

 Najciekawsze w tym zadaniu jest jednak co innego – jego zaskakujące powiązanie z pewnym problemem z zakresu teorii liczb. Problem dotyczy ciągu liczb całkowitych od 1 do 2n; dla n=8 będą to więc liczby od 1 do 16. Łączymy je w pary i obliczamy sumę i różnicę liczb w każdej parze, ale należy zrobić to tak, aby wszystkie 2n sum i różnic było różnymi liczbami. Udowodniono, że takie swaty możliwe są dla każdego n≥3; na ile sposobów można to zrobić, wiadomo tylko dla n≤10.

 

Rys. 7

Weźmy teraz rozwiązanie 5 z rys. 2 z lustrem u dołu i ponumerujmy rzędy jak w szachach – liczbami od 1 do 8 od dołu do góry, a następnie kolumny od 9 do 16 (rys. 7). Traktując te liczby jak współrzędne, wypiszemy pozycje wszystkich hetmanów – każda określona jest dwiema liczbami w tabeli. W prawej kolumnie są ich sumy i różnice – proszę zwrócić uwagę, że każda z tych liczb jest inna, czyli – o dziwo – pary współrzędnych stanowią jedno z rozwiązań powyższego problemu liczbowego dla n=8.

Skąd taka zbieżność zagadnień pozornie od siebie odległych? Oto zagadka, być może trudniejsza niż każda z czterech sąsiednich hetmańskich łamigłówek konkursowych.

1.         Zadanie polega na zrobieniu trzech ruchów w jednym z rozwiązań problemu ośmiu hetmanów (rys. 8). Należy:

– przesunąć jednego z hetmanów (zgodnie z zasadą jego ruchu),

– dostawić na szachownicę jeszcze jednego, dziewiątego hetmana,

– umieścić na szachownicy pionek.

 

Rys. 8

 Ruchy powinny być takie, aby po ich wykonaniu nadal żadne dwa hetmany wzajemnie się nie atakowały.

2.         Na mini-szachownicy 4×4 (rys. 9) należy ustawić osiem hetmanów tak, aby każdy atakował inną liczbę wolnych pól – od zera do siedmiu. Dwa hetmany są już na właściwych polach, pozostaje dostawić sześć.

 

Rys. 9

 

3.         Pięć hetmanów na rys. 10 nie atakuje 15 pól (żółte). Zadanie polega na dostawieniu do tego układu jeszcze trzech hetmanów tak, aby przy ośmiu hetmanach liczba nieatakowanych pól nie spadła poniżej 11.

 

 

Rys. 10

 

4.         Trzy hetmany i dwie wieże stoją w szyku bojowym u dołu planszy gotowe do jej opanowania (rys. 11); na razie panują nad 52 polami – atakowanymi i/lub zajmowanymi (szare). Każdą figurą należy wykonać jeden ruch – zgodny ze sposobem jej poruszania się – tak, aby po pięciu ruchach wszystkie pola szachownicy zostały opanowane. Ruchy wieżami są znane: Wd1-d8 oraz Wf1-f4. Jakie powinny być trzy posunięcia hetmańskie?

 

Rys. 11



Rozwiązania prosimy nadsyłać do 31 maja br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl),
wpisując w temacie e-maila hasło UG05/13, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką
Zrozumieć niepojęte Leona Ledermana i Christophera Hilla, ufundowaną przez wydawnictwo Prószyński Media.

 

Więcej w miesięczniku „Świat Nauki" nr 05/2013 »
Drukuj »
Komentarze
Dodany przez: m.penszko | 2013-05-06
Oczywiście racja:( Fioletowa powinna być na b2, a na jej miejsce należy przesunąć niebieską z f3. Mam nadzieję, że pozostałe gwiazdki "świecą" gdzie i jak należy, poza tym że na rys. 4 jednej brakuje - łatwo zauważyć gdzie i jakiej. Marek Penszko
Dodany przez: agata | 2013-05-05
rys. 1: dla koloru niebieskiego nie bronione jest tez pole e2?
 
Dodany przez: agata | 2013-05-05
Bardzo ciekawy artykul. Dziękuję. Fioletowa gwiazdka na rys. 1 nie powinna byc na polu b2 a nie na e2? 
Aktualne numery
11/2017
10/2017 - specjalny
Kalendarium
Listopad
19
W 1912 r. urodził się George Emil Palade, amerykański cytolog, laureat Nagrody Nobla.
Warto przeczytać
Chwila bez biologii… nie istnieje. W nas i wokół nas kipi życie. Dlaczego by wobec tego nie poznać go bliżej, najlepiej we własnym laboratorium? By nie sięgać daleko, można zacząć od siebie.

Logowanie

Nazwa użytkownika

Hasło

Autor: Marek Penszko | dodano: 2013-04-22
Superpozycje i lustra

Choć szachy trudno nazwać grą matematyczną, to między królową nauk
a królewską grą można doszukać się wielu powiązań.

Z reguły są to związki formalne, czyli dotyczące planszy i figur, a nie samej rozgrywki. Zagadnienia z nimi związane można wprawdzie rozpatrywać, nie odwołując się do szachów, jednak z grą jest bardziej obrazowo, ciekawiej, a czasami prościej. Typowy przykład stanowi stare zadanie o liczbie ziaren zboża, umieszczanych na szachownicy w następujący sposób: jedno na pierwszym polu, dwa na drugim, cztery na trzecim itd. – na każdym następnym dwukrotnie więcej niż na poprzednim. Trudno uwierzyć, że do pokrycia w ten sposób 64 pól nie starczyłoby zboża na Ziemi, choć nietrudno obliczyć sumę wyrazów postępu geometrycznego.

Inny przykład – problem z zakresu geometrii kombinatorycznej lub teorii grafów: kwadrat podzielono na 64 kwadratowe pola (8×8); ile co najmniej pól należałoby oznaczyć, aby w każdym rzędzie równoległym do brzegu lub do przekątnej kwadratu znalazło się jedno oznaczone pole? Byłoby to zapewne bardzo niszowe zadanie, gdyby nie jego szachowa modyfikacja popularna od kilkuset lat: ustaw na szachownicy cztery hetmany tak, aby atakowały wszystkie wolne pola. Dopiero w połowie XIX wieku wykazano, a właściwie mozolnie sprawdzono, że nie jest to możliwe. Prosty dowód, że cztery hetmany nie wystarczą, nie jest znany, ale jakkolwiek by ich nie rozmieszczać, zawsze co najmniej dwa pola pozostaną nieatakowane. Ustawień całkowicie różnych (z dokładnością do odbić i obrotów) z parą niezagrożonych pól jest osiem. Wszystkie można przedstawić na dwóch diagramach (rys. 1) – na każdym znajdują się nałożone na siebie cztery ustawienia w takich pozycjach (obrócone lub/i odbite), że w żadne pole nie trafiają dwa oznaczenia. Takie „bezkolizyjne” nałożenie nazwiemy superpozycją rozłączną. Ustawienia na rys.1 różnią się kolorami; w nieatakowanych polach są gwiazdki.

 

Rys. 1

 
Zadanie o czterech hetmanach należy do łamigłówek matematyczno-szachowych, polegających na takim rozmieszczaniu na szachownicy określonych figur, aby ich układ spełniał podane warunki. Zalicza się do nich także bardziej znane XIX-wieczne zadanie, w którym chodzi o ustawienie na szachownicy ośmiu hetmanów tak, by żaden nie atakował innego. Rozwiązać je łatwo, choć to zajęcie żmudne i schematyczne – idealne, by napisać algorytm i skorzystać z komputera, więc często pojawia się jako ćwiczenie dla początkujących programistów. Komputer błyskawicznie znajduje 12 całkowicie różnych rozwiązań (rys. 2).

 

Rys. 2

Przed 60 laty w Stanach Zjednoczonych w sklepach z zabawkami można było kupić grę dla jednej osoby zwaną hoodoo. Obejmowała ona kilka łamigłówek, polegających na umieszczaniu kolorowych kołeczków w otworach kwadratowej planszy. W najtrudniejszej były 64 kołeczki, po osiem w ośmiu różnych kolorach, a układ 64 otworów był taki, jak pól szachownicy. Wszystkie kołeczki należało rozmieścić tak, by w żadnym rzędzie równoległym do brzegów lub przekątnej planszy nie było dwóch w takim samym kolorze. Zabawa nawet jak na lata 50. nie była zbyt wyszukana, ale pikanterii dodawała jej nagroda – na pierwszą osobę, która uporałaby się z zadaniem, czekał… milion dolarów. W wersji szachowej reguły brzmiałyby krótko i zwięźle: znajdź superpozycję rozłączną ośmiu rozwiązań problemu ośmiu hetmanów. Zapewne wiele czasu stracono na bezowocne zmagania z tą kuszącą milionem łamigłówką, bowiem mało kto wiedział, że już w roku 1914 angielski prawnik i matematyk-amator Thorold Gosset wykazał w prosty i elegancki sposób, że rozwiązanie nie istnieje. Dowód sprowadza się do oznaczenia na szachownicy 20 pól (rys. 3).

 

 Rys. 3

 

 

 Rys. 4

Co najmniej trzy z tych pól zajmują hetmany w każdym z 12 rozwiązań na rys. 2. Rozłączna superpozycja nawet siedmiu rozwiązań nie będzie więc możliwa, bo na oznaczonych 20 polach znajdzie się przynajmniej 21 hetmanów. Zatem nałożyć na siebie można co najwyżej sześć rozwiązań, które zajmą 48 pól. Przykład jednej z takich superpozycji przedstawiony jest na rys. 4. Wśród sześciu składających się na nią rozwiązań są tylko dwa różne, odpowiednio odbite lub/i obrócone – cztery „2” i dwa „10” z rys. 2. Zadanie okazuje się znacznie trudniejsze po dodaniu warunku, aby całkowicie różne były wszystkie nałożone rozwiązania. Wówczas niemożliwa jest nie tylko rozłączna superpozycja sześciu rozwiązań, ale prawdopodobnie także pięciu. Nie sposób nawet „bezkolizyjnie” nałożyć na siebie niektórych par rozwiązań, np. „5” i „6” lub „6” i „12”, mimo uwzględniania odbić i obrotów. Można natomiast utworzyć trzy rozłączne superpozycje, obejmujące wszystkie 12 rozwiązań – po cztery rozwiązania w każdej, czyli przedstawić wszystkie rozwiązania hetmańskiego problemu na trzech diagramach (rys. 5; hetmany zastąpiono liczbami odpowiadającymi numerom rozwiązań na rys. 2).

 

Rys. 5

Wracając do gry hoodoo, a ściślej do jej uogólnionej wersji (plansza n×n) – w roku 1918 matematyk węgierski George Pólya wykazał, że rozwiązanie (wypełnienie hetmanami wszystkich pól) nie istnieje nie tylko dla n=8, ale dla każdego n podzielnego przez 2 lub 3. Później okazało się, że wnioski Pólyi są prawdziwe tylko dla nn=5, 7 i większe od 10) ufundowanie przez producenta nagrody miliona dolarów oznaczałoby więc jego bankructwo.

Inne ciekawe zagadnienie związane z problemem ośmiu hetmanów dotyczy wariantu tego zadania, w którym jakby zwiększony jest zasięg ataku figur. Dzieje się tak dzięki „lustru” umieszczonemu przy jednym brzegu szachownicy w odległości równej połowie szerokości pola. Ukośna linia ataku odbija się od niego jak promień i po odbiciu może trafić w innego hetmana. Podstawowa zasada jest taka, jak w pierwowzorze: osiem hetmanów trzeba rozlokować tak, aby sobie nie zagrażały. Rozwiązania nietrudno znaleźć, ustawiając kolejno lustro przy każdym boku każdego z 12 rozwiązań na rys. 2. Na przykład, piąte rozwiązanie z lustrem z prawej strony odpadnie, bo dwie pary hetmanów zagrażają sobie po odbiciu (linie przerywane na rys. 6); jeśli jednak lustro umieścimy u dołu, żadnego zagrożenia nie będzie. W sumie pozostanie pięć rozwiązań: 5 i 9 z lustrem u dołu oraz 7, 9 i 11 z lustrem z lewej strony.

 

Rys. 6

 Najciekawsze w tym zadaniu jest jednak co innego – jego zaskakujące powiązanie z pewnym problemem z zakresu teorii liczb. Problem dotyczy ciągu liczb całkowitych od 1 do 2n; dla n=8 będą to więc liczby od 1 do 16. Łączymy je w pary i obliczamy sumę i różnicę liczb w każdej parze, ale należy zrobić to tak, aby wszystkie 2n sum i różnic było różnymi liczbami. Udowodniono, że takie swaty możliwe są dla każdego n≥3; na ile sposobów można to zrobić, wiadomo tylko dla n≤10.

 

Rys. 7

Weźmy teraz rozwiązanie 5 z rys. 2 z lustrem u dołu i ponumerujmy rzędy jak w szachach – liczbami od 1 do 8 od dołu do góry, a następnie kolumny od 9 do 16 (rys. 7). Traktując te liczby jak współrzędne, wypiszemy pozycje wszystkich hetmanów – każda określona jest dwiema liczbami w tabeli. W prawej kolumnie są ich sumy i różnice – proszę zwrócić uwagę, że każda z tych liczb jest inna, czyli – o dziwo – pary współrzędnych stanowią jedno z rozwiązań powyższego problemu liczbowego dla n=8.

Skąd taka zbieżność zagadnień pozornie od siebie odległych? Oto zagadka, być może trudniejsza niż każda z czterech sąsiednich hetmańskich łamigłówek konkursowych.

1.         Zadanie polega na zrobieniu trzech ruchów w jednym z rozwiązań problemu ośmiu hetmanów (rys. 8). Należy:

– przesunąć jednego z hetmanów (zgodnie z zasadą jego ruchu),

– dostawić na szachownicę jeszcze jednego, dziewiątego hetmana,

– umieścić na szachownicy pionek.

 

Rys. 8

 Ruchy powinny być takie, aby po ich wykonaniu nadal żadne dwa hetmany wzajemnie się nie atakowały.

2.         Na mini-szachownicy 4×4 (rys. 9) należy ustawić osiem hetmanów tak, aby każdy atakował inną liczbę wolnych pól – od zera do siedmiu. Dwa hetmany są już na właściwych polach, pozostaje dostawić sześć.

 

Rys. 9

 

3.         Pięć hetmanów na rys. 10 nie atakuje 15 pól (żółte). Zadanie polega na dostawieniu do tego układu jeszcze trzech hetmanów tak, aby przy ośmiu hetmanach liczba nieatakowanych pól nie spadła poniżej 11.

 

 

Rys. 10

 

4.         Trzy hetmany i dwie wieże stoją w szyku bojowym u dołu planszy gotowe do jej opanowania (rys. 11); na razie panują nad 52 polami – atakowanymi i/lub zajmowanymi (szare). Każdą figurą należy wykonać jeden ruch – zgodny ze sposobem jej poruszania się – tak, aby po pięciu ruchach wszystkie pola szachownicy zostały opanowane. Ruchy wieżami są znane: Wd1-d8 oraz Wf1-f4. Jakie powinny być trzy posunięcia hetmańskie?

 

Rys. 11



Rozwiązania prosimy nadsyłać do 31 maja br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl),
wpisując w temacie e-maila hasło UG05/13, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką
Zrozumieć niepojęte Leona Ledermana i Christophera Hilla, ufundowaną przez wydawnictwo Prószyński Media.