nauki ścisłe
Autor: Marek Penszko | dodano: 2013-10-23
Domino matrymonialne

Jak matematyka pomaga rozwiązać sercowe problemy.

W sierpniowym Umyśle giętkim zamieściliśmy zadanie, które wielu osobom sprawiło kłopot. Zwykle pomijano je w nadesłanych rozwiązaniach, pojawiały się też błędne odpowiedzi; tylko dwie osoby próbowały analizować je nieco wnikliwiej, a z reguły radzono sobie, próbując i błądząc. Zadanie polegało na usunięciu z szachownicy (8×8) minimalnej liczby jasnych i ciemnych pól – tylu samo jednych i drugich – tak, aby pozostałe tworzyły spójną planszę (do każdego pola można było dotrzeć z dowolnego innego wieżą) i aby niemożliwe było pokrycie ich wszystkich kamieniami domina (każdy zakrywa dwa pola stykające się bokami, a więc w różnych kolorach) mimo równej liczby jasnych i ciemnych pól.

Dowód, że pozbycie się jednego jasnego i jednego ciemnego pola to za mało, czyli że 62 pozostałe zawsze da się pokryć 31 kamieniami, jest prosty i elegancki. Podał go przed 40 laty matematyk amerykański Ralph Gomory. Wystarczy narysować na szachownicy trasę zamkniętą, obejmującą wszystkie pola – zawsze przechodzącą z pola na pole w rzędzie lub kolumnie, nigdy na ukos. Takich różnych tras jest wiele, przykładowa na rys. 1. Po usunięciu dwu dowolnych pól, ciemnego i jasnego (np. przekreślonych na rysunku), trasa zostanie podzielona na dwie części – każda będzie złożona z parzystej liczby pól – więc pokrycie dominem obu tych części, a zatem całej planszy, będzie możliwe.

Rys. 1    

 

Rys. 2

Sprawa nieco się komplikuje, jeśli pójść krok dalej, czyli usunąć dwa jasne i dwa ciemne pola. Uzasadniony był więc komentarz, który dołączył do rozwiązań jeden z czytelników, Pan Jacek Tyburczyk z Krakowa: z przyjemnością zobaczyłbym (jeśli istnieje) prosty dowód tego, że dla dowolnych czterech się da. Chodzi, oczywiście, o możliwość pokrycia w takiej sytuacji dominem pozostałych 60 pól. Kontynuacja dowodu Gomory’ego w tym przypadku zawodzi, bo pola można usunąć tak, że trasa zostanie podzielona na części złożone z parzystej albo nieparzystej liczby pól. Prostą metodę poradzenia sobie w tej sytuacji zaproponował Ian Stewart1: należy podzielić planszę na dwie części tak, aby w każdej brakowało jednego jasnego i jednego ciemnego pola oraz w każdej możliwe było zastosowanie dowodu Gomory’ego (przykład na rys. 2). Szkopuł w tym, że teraz wypadałoby dowieść, iż zawsze uda się dokonać takiego podziału, a dowodu Stewart nie podaje. Przyznaje, że metoda przyjęta jest „na wiarę” i że być może uda się w przyszłości wymyśleć coś lepszego. I rzeczywiście, z zadaniem można poradzić sobie inaczej i niemal równie elegancko, jak zrobił to Gomory. W tym celu należy skorzystać z tzw. twierdzenia Halla, zwanego również twierdzeniem o kojarzeniu małżeństw.

Załóżmy, że mamy dwie grupy osób – jedna składa się z p panien, druga z iluś kawalerów. Każda panna lubi niektórych kawalerów – upatrzyła sobie ich jako możliwych kandydatów na męża. Celem jest wyswatanie wszystkich panien. W jakiej sytuacji będzie to możliwe (poligamię wykluczamy)? Zwięzły warunek sformułował w roku 1935 brytyjski matematyk Philip Hall:

Każdej podgrupie n dziewcząt (1np) powinno podobać się co najmniej n chłopców.

Warunek jest konieczny, ponieważ zabrakłoby kawalerów, gdyby było ich mniej niż n. Jest także – co wydaje się zaskakujące i co rozstrzyga o randze w ramach teorii zbiorów oraz o praktycznych zastosowaniach twierdzenia Halla – dostateczny. W pełnej „matrymonialnej” formie twierdzenie mogłoby więc brzmieć tak:

Jeśli każdej podgrupie n spośród p panien (1np) podoba się co najmniej n kawalerów, wtedy I TYLKO WTEDY wszystkie p panien uda się wyswatać ku ich zadowoleniu (żadna nie dostanie chłopca, który jej się nie podoba).

To, że podany warunek wystarcza, aby każda panna była kontenta, można udowodnić, korzystając z indukcji matematycznej. Dla „niepraktykujących” dowód nie jest jednak prosty. Zainteresowanym polecam jego w miarę przystępną wersję zamieszczoną w znakomitych „Dowodach z Księgi” 2.

Powróćmy do szachownicy i domina. Jasne pola planszy to panny, ciemne – kawalerowie. Wszystkie można pokryć dominem, czyli wyswatać, bo – co łatwo sprawdzić – każda podgrupa n jasnych pól (1≤n≤32) sympatyzuje, czyli sąsiaduje bokiem, z co najmniej n ciemnymi polami. Aby wyswatanie, a więc pokrycie dominem, nie było możliwe, trzeba doprowadzić do sytuacji, w której jakaś podgrupa n jasnych pól, możliwie najmniejsza, będzie sąsiadować z mniej niż n ciemnymi polami. Gdyby podgrupę stanowiło jedno jasne pole, to nie powinno ono graniczyć z żadnym ciemnym, ale wtedy plansza nie byłaby spójna. Muszą więc być co najmniej dwa i oba muszą sąsiadować z dokładnie jednym wspólnym ciemnym. Kawalerów nie może być jednak mniej niż panien, więc potrzebne jest jeszcze jedno ciemne pole, ale niestykające się z już wybranymi dwoma jasnymi. Musi ono jednak sąsiadować z jakimś jasnym (spójność planszy), więc jedno jasne trzeba jeszcze w układzie uwzględnić. W ten sposób powstał najmniejszy komplet połączeń jasnych-panien i ciemnych-kawalerów, uniemożliwiający swaty-pokrycie dominem (rys. 3). Inaczej mówiąc, trzeba usunąć tyle i takich pól, aby na planszy pojawił się układ z rys. 3.

             

Rys. 3

Warto przy tym pamiętać, że panny są ważniejsze, bo to one wybierają kawalerów, więc trzeba przede wszystkim zadbać o to, aby w układzie były trzy jasne pola, stykające się z dwoma i tylko dwoma ciemnymi – z iloma jasnymi sąsiadować będą te dwa ciemne, nie jest istotne. Zadanie sprowadza się więc do usunięcia z szachownicy najmniejszej liczby ciemnych pól tak, aby pozostała grupa trzech jasnych, graniczących tylko z dwoma ciemnymi.

Czy wystarczy usunąć dwa ciemne? Byłoby to możliwe, gdybyśmy wskazali na szachownicy grupę trzech jasnych, graniczącą z czterema ciemnymi, ale takiej grupy nie ma. Można natomiast wskazać trzy jasne otoczone pięcioma ciemnymi i taka grupa jest tylko jedna! – oczywiście z dokładnością do odbić i obrotów szachownicy (rys. 4).

 

Rys. 4

Teraz zadanie staje się trywialne – wystarczy usunąć dowolne trzy z ciemnych pól, otaczających tę grupę. Można to zrobić na 10 sposobów. Po odrzuceniu tych, które prowadzą do niespójności planszy, czyli odcinają jakieś pole, oraz po uwzględnieniu symetrii i odbić pozostanie pięć całkowicie różnych rozwiązań zadania wyjściowego (rys. 5). Pomijamy trzy jasne pola, które – zgodnie z treścią zadania – należałoby jeszcze usunąć, bo mogą to być dowolne pola z pozostałej części szachownicy.

 

Rys. 5

Kamienie domina, jako figury złożone z dwóch kwadratów (oczka pomijamy), goszczą w niektórych poważnych zagadnieniach matematycznych, przede wszystkim w geometrii kombinatorycznej. Często też występują w zadaniach. Poniższe, konkursowe, stanowią przedsmak tematów związanych z dominem, które pojawią się w jednym z najbliższych numerów Świata Nauki.

W zadaniach 1 i 2 domino umieszczane jest na szachownicy tak, że każdy kamień zakrywa ściśle dwa pola, a układ wszystkich powinien być spójny, czyli taki, by możliwe było dotarcie z dowolnego kamienia do każdego innego ruchem wieży. Kiedy mowa jest o sąsiadowaniu lub stykaniu się kamieni, oznacza to kontakt bokami.

1. Kamienie domina należy umieścić na szachownicy 9×9 (rys. 6) tak, aby:

–    każdy sąsiadował dokładnie z dwoma innymi;

–    żadne dwa nie stykały się krótszymi lub dłuższymi bokami, a więc wykluczone są takie układy par kamieni, jak na rys. 6 z lewej strony;

–    układ wszystkich kamieni był spójny i tworzył pętlę, czyli aby można je było wszystkie obejść wieżą, nie goszcząc dwukrotnie na tym samym kamieniu, i wrócić do punktu wyjścia.

Część pól, które powinny zakryć kamienie, oznaczona jest kropkami.

W rozwiązaniu wystarczy podać, ile pól zasłaniają kamienie na przekątnych szachownicy.

Rys. 6

2. Na szachownicy układane są trzy rodzaje kamieni rozdzielonych na pół, czyli przypominających używane w grze: ○|□, ×|□ i ×|○. Trzeba je rozmieścić tak, aby:

–    tworzyły spójny układ;

–    nigdzie nie stykały się ze sobą takie same rodzaje kamieni;

–    na stykających się połówkach kamieni były jednakowe symbole.

Na diagramie (rys. 7) ujawniono miejsca niektórych połówek kamieni.

W rozwiązaniu wystarczy podać, ile symboli każdego rodzaju znalazło się na przekątnych.

Rys. 7

3. Wielokąt z 12 kwadratów (rys. 8) można pokryć kamieniami domina na trzy sposoby. Jaki kształt ma wielokąt złożony z 12 kwadratów, który da się pokryć dominem dokładnie na siedem sposobów? Odpowiedź można podać, umieszczając figurę na szachownicy i zapisując współrzędne tworzących ją kwadratów. Na przykład, dla figury z rys. 8 rozwiązanie mogłoby wyglądać tak: a3, b1–3, c1–4, d1–3, e3.

 

Rys. 8

1 Ian Stewart, „Histerie matematyczne”, Prószyński i S-ka, 2007.
2
Martin Aigner, Günter M. Ziegler, „Dowody z Księgi”, PWN 2002.

 

Rozwiązania prosimy nadsyłać do 30 listopada br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG11/13, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02-697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Jamesa D. Steina Kosmiczne liczby. Liczby, które definiują naszą rzeczywistość, ufundowaną przez wydawnictwo Prószyński Media.

 

Rozwiązanie zadań z numeru wrześniowego

1. 4059, 4060, 5741.

2. Najlepsza aproksymacja √2 w postaci ułamka złożonego z 10 różnych cyfr: 95103/67248 = 1,4142130621

3. Układ 9 różnych cyfr w kwadracie 3x3 (rzędami od góry) 709/435/126 umożliwia odczytanie rozwinięcia dziesiętnego √2 do 17 cyfry po przecinku: 1,41421356237309504.

Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Stephena Oppenheimera Pożegnanie z Afryką, ufundowaną przez wydawnictwo Prószyński Media, otrzymują:  Andrzej Idzik z Bolesławca, Andrzej Sulich z Olkusza, Edward Śliwa z Kalisza, Paweł Totoń z Wrocławia, Jarosław Trzmielewski z Poznania.

 

Więcej w miesięczniku „Świat Nauki" nr 11/2013 »
Drukuj »
Ten artykuł nie został jeszcze skomentowany.
Aktualne numery
11/2017
10/2017 - specjalny
Kalendarium
Listopad
20
W 1985 r. Microsoft zaprezentował system operacyjny Windows 1.0.
Warto przeczytać
Odkrycia Svante Pääbo zrewolucjonizowały antropologię i doprowadziły do naniesienia poprawek w naszym drzewie genealogicznym. Stały się fundamentem, na którym jeszcze przez długie lata budować będą inni badacze

Logowanie

Nazwa użytkownika

Hasło

Autor: Marek Penszko | dodano: 2013-10-23
Domino matrymonialne

Jak matematyka pomaga rozwiązać sercowe problemy.

W sierpniowym Umyśle giętkim zamieściliśmy zadanie, które wielu osobom sprawiło kłopot. Zwykle pomijano je w nadesłanych rozwiązaniach, pojawiały się też błędne odpowiedzi; tylko dwie osoby próbowały analizować je nieco wnikliwiej, a z reguły radzono sobie, próbując i błądząc. Zadanie polegało na usunięciu z szachownicy (8×8) minimalnej liczby jasnych i ciemnych pól – tylu samo jednych i drugich – tak, aby pozostałe tworzyły spójną planszę (do każdego pola można było dotrzeć z dowolnego innego wieżą) i aby niemożliwe było pokrycie ich wszystkich kamieniami domina (każdy zakrywa dwa pola stykające się bokami, a więc w różnych kolorach) mimo równej liczby jasnych i ciemnych pól.

Dowód, że pozbycie się jednego jasnego i jednego ciemnego pola to za mało, czyli że 62 pozostałe zawsze da się pokryć 31 kamieniami, jest prosty i elegancki. Podał go przed 40 laty matematyk amerykański Ralph Gomory. Wystarczy narysować na szachownicy trasę zamkniętą, obejmującą wszystkie pola – zawsze przechodzącą z pola na pole w rzędzie lub kolumnie, nigdy na ukos. Takich różnych tras jest wiele, przykładowa na rys. 1. Po usunięciu dwu dowolnych pól, ciemnego i jasnego (np. przekreślonych na rysunku), trasa zostanie podzielona na dwie części – każda będzie złożona z parzystej liczby pól – więc pokrycie dominem obu tych części, a zatem całej planszy, będzie możliwe.

Rys. 1    

 

Rys. 2

Sprawa nieco się komplikuje, jeśli pójść krok dalej, czyli usunąć dwa jasne i dwa ciemne pola. Uzasadniony był więc komentarz, który dołączył do rozwiązań jeden z czytelników, Pan Jacek Tyburczyk z Krakowa: z przyjemnością zobaczyłbym (jeśli istnieje) prosty dowód tego, że dla dowolnych czterech się da. Chodzi, oczywiście, o możliwość pokrycia w takiej sytuacji dominem pozostałych 60 pól. Kontynuacja dowodu Gomory’ego w tym przypadku zawodzi, bo pola można usunąć tak, że trasa zostanie podzielona na części złożone z parzystej albo nieparzystej liczby pól. Prostą metodę poradzenia sobie w tej sytuacji zaproponował Ian Stewart1: należy podzielić planszę na dwie części tak, aby w każdej brakowało jednego jasnego i jednego ciemnego pola oraz w każdej możliwe było zastosowanie dowodu Gomory’ego (przykład na rys. 2). Szkopuł w tym, że teraz wypadałoby dowieść, iż zawsze uda się dokonać takiego podziału, a dowodu Stewart nie podaje. Przyznaje, że metoda przyjęta jest „na wiarę” i że być może uda się w przyszłości wymyśleć coś lepszego. I rzeczywiście, z zadaniem można poradzić sobie inaczej i niemal równie elegancko, jak zrobił to Gomory. W tym celu należy skorzystać z tzw. twierdzenia Halla, zwanego również twierdzeniem o kojarzeniu małżeństw.

Załóżmy, że mamy dwie grupy osób – jedna składa się z p panien, druga z iluś kawalerów. Każda panna lubi niektórych kawalerów – upatrzyła sobie ich jako możliwych kandydatów na męża. Celem jest wyswatanie wszystkich panien. W jakiej sytuacji będzie to możliwe (poligamię wykluczamy)? Zwięzły warunek sformułował w roku 1935 brytyjski matematyk Philip Hall:

Każdej podgrupie n dziewcząt (1np) powinno podobać się co najmniej n chłopców.

Warunek jest konieczny, ponieważ zabrakłoby kawalerów, gdyby było ich mniej niż n. Jest także – co wydaje się zaskakujące i co rozstrzyga o randze w ramach teorii zbiorów oraz o praktycznych zastosowaniach twierdzenia Halla – dostateczny. W pełnej „matrymonialnej” formie twierdzenie mogłoby więc brzmieć tak:

Jeśli każdej podgrupie n spośród p panien (1np) podoba się co najmniej n kawalerów, wtedy I TYLKO WTEDY wszystkie p panien uda się wyswatać ku ich zadowoleniu (żadna nie dostanie chłopca, który jej się nie podoba).

To, że podany warunek wystarcza, aby każda panna była kontenta, można udowodnić, korzystając z indukcji matematycznej. Dla „niepraktykujących” dowód nie jest jednak prosty. Zainteresowanym polecam jego w miarę przystępną wersję zamieszczoną w znakomitych „Dowodach z Księgi” 2.

Powróćmy do szachownicy i domina. Jasne pola planszy to panny, ciemne – kawalerowie. Wszystkie można pokryć dominem, czyli wyswatać, bo – co łatwo sprawdzić – każda podgrupa n jasnych pól (1≤n≤32) sympatyzuje, czyli sąsiaduje bokiem, z co najmniej n ciemnymi polami. Aby wyswatanie, a więc pokrycie dominem, nie było możliwe, trzeba doprowadzić do sytuacji, w której jakaś podgrupa n jasnych pól, możliwie najmniejsza, będzie sąsiadować z mniej niż n ciemnymi polami. Gdyby podgrupę stanowiło jedno jasne pole, to nie powinno ono graniczyć z żadnym ciemnym, ale wtedy plansza nie byłaby spójna. Muszą więc być co najmniej dwa i oba muszą sąsiadować z dokładnie jednym wspólnym ciemnym. Kawalerów nie może być jednak mniej niż panien, więc potrzebne jest jeszcze jedno ciemne pole, ale niestykające się z już wybranymi dwoma jasnymi. Musi ono jednak sąsiadować z jakimś jasnym (spójność planszy), więc jedno jasne trzeba jeszcze w układzie uwzględnić. W ten sposób powstał najmniejszy komplet połączeń jasnych-panien i ciemnych-kawalerów, uniemożliwiający swaty-pokrycie dominem (rys. 3). Inaczej mówiąc, trzeba usunąć tyle i takich pól, aby na planszy pojawił się układ z rys. 3.

             

Rys. 3

Warto przy tym pamiętać, że panny są ważniejsze, bo to one wybierają kawalerów, więc trzeba przede wszystkim zadbać o to, aby w układzie były trzy jasne pola, stykające się z dwoma i tylko dwoma ciemnymi – z iloma jasnymi sąsiadować będą te dwa ciemne, nie jest istotne. Zadanie sprowadza się więc do usunięcia z szachownicy najmniejszej liczby ciemnych pól tak, aby pozostała grupa trzech jasnych, graniczących tylko z dwoma ciemnymi.

Czy wystarczy usunąć dwa ciemne? Byłoby to możliwe, gdybyśmy wskazali na szachownicy grupę trzech jasnych, graniczącą z czterema ciemnymi, ale takiej grupy nie ma. Można natomiast wskazać trzy jasne otoczone pięcioma ciemnymi i taka grupa jest tylko jedna! – oczywiście z dokładnością do odbić i obrotów szachownicy (rys. 4).

 

Rys. 4

Teraz zadanie staje się trywialne – wystarczy usunąć dowolne trzy z ciemnych pól, otaczających tę grupę. Można to zrobić na 10 sposobów. Po odrzuceniu tych, które prowadzą do niespójności planszy, czyli odcinają jakieś pole, oraz po uwzględnieniu symetrii i odbić pozostanie pięć całkowicie różnych rozwiązań zadania wyjściowego (rys. 5). Pomijamy trzy jasne pola, które – zgodnie z treścią zadania – należałoby jeszcze usunąć, bo mogą to być dowolne pola z pozostałej części szachownicy.

 

Rys. 5

Kamienie domina, jako figury złożone z dwóch kwadratów (oczka pomijamy), goszczą w niektórych poważnych zagadnieniach matematycznych, przede wszystkim w geometrii kombinatorycznej. Często też występują w zadaniach. Poniższe, konkursowe, stanowią przedsmak tematów związanych z dominem, które pojawią się w jednym z najbliższych numerów Świata Nauki.

W zadaniach 1 i 2 domino umieszczane jest na szachownicy tak, że każdy kamień zakrywa ściśle dwa pola, a układ wszystkich powinien być spójny, czyli taki, by możliwe było dotarcie z dowolnego kamienia do każdego innego ruchem wieży. Kiedy mowa jest o sąsiadowaniu lub stykaniu się kamieni, oznacza to kontakt bokami.

1. Kamienie domina należy umieścić na szachownicy 9×9 (rys. 6) tak, aby:

–    każdy sąsiadował dokładnie z dwoma innymi;

–    żadne dwa nie stykały się krótszymi lub dłuższymi bokami, a więc wykluczone są takie układy par kamieni, jak na rys. 6 z lewej strony;

–    układ wszystkich kamieni był spójny i tworzył pętlę, czyli aby można je było wszystkie obejść wieżą, nie goszcząc dwukrotnie na tym samym kamieniu, i wrócić do punktu wyjścia.

Część pól, które powinny zakryć kamienie, oznaczona jest kropkami.

W rozwiązaniu wystarczy podać, ile pól zasłaniają kamienie na przekątnych szachownicy.

Rys. 6

2. Na szachownicy układane są trzy rodzaje kamieni rozdzielonych na pół, czyli przypominających używane w grze: ○|□, ×|□ i ×|○. Trzeba je rozmieścić tak, aby:

–    tworzyły spójny układ;

–    nigdzie nie stykały się ze sobą takie same rodzaje kamieni;

–    na stykających się połówkach kamieni były jednakowe symbole.

Na diagramie (rys. 7) ujawniono miejsca niektórych połówek kamieni.

W rozwiązaniu wystarczy podać, ile symboli każdego rodzaju znalazło się na przekątnych.

Rys. 7

3. Wielokąt z 12 kwadratów (rys. 8) można pokryć kamieniami domina na trzy sposoby. Jaki kształt ma wielokąt złożony z 12 kwadratów, który da się pokryć dominem dokładnie na siedem sposobów? Odpowiedź można podać, umieszczając figurę na szachownicy i zapisując współrzędne tworzących ją kwadratów. Na przykład, dla figury z rys. 8 rozwiązanie mogłoby wyglądać tak: a3, b1–3, c1–4, d1–3, e3.

 

Rys. 8

1 Ian Stewart, „Histerie matematyczne”, Prószyński i S-ka, 2007.
2
Martin Aigner, Günter M. Ziegler, „Dowody z Księgi”, PWN 2002.

 

Rozwiązania prosimy nadsyłać do 30 listopada br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG11/13, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02-697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Jamesa D. Steina Kosmiczne liczby. Liczby, które definiują naszą rzeczywistość, ufundowaną przez wydawnictwo Prószyński Media.

 

Rozwiązanie zadań z numeru wrześniowego

1. 4059, 4060, 5741.

2. Najlepsza aproksymacja √2 w postaci ułamka złożonego z 10 różnych cyfr: 95103/67248 = 1,4142130621

3. Układ 9 różnych cyfr w kwadracie 3x3 (rzędami od góry) 709/435/126 umożliwia odczytanie rozwinięcia dziesiętnego √2 do 17 cyfry po przecinku: 1,41421356237309504.

Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Stephena Oppenheimera Pożegnanie z Afryką, ufundowaną przez wydawnictwo Prószyński Media, otrzymują:  Andrzej Idzik z Bolesławca, Andrzej Sulich z Olkusza, Edward Śliwa z Kalisza, Paweł Totoń z Wrocławia, Jarosław Trzmielewski z Poznania.