nauki ścisłe
Autor: Marek Penszko | dodano: 2013-07-22
Logika krótkich klepek

Amerykański filozof Max Black opublikował w 1946 roku książkę Critical thinking, w której zamieścił kilka prostych zadań, ilustrujących różne sposoby wnioskowania. Jedno z nich zrobiło światową karierę. Publikowane jest często jako łamigłówka i uchodzi za klasyczne w dziale matematyki zwanym geometrią kombinatoryczną.

Z szachownicy (8×8) usunięto dwa narożne pola (z końców tej samej przekątnej, rys. 1). Czy możliwe jest pokrycie całej „wybrakowanej” planszy kamieniami domina, z których każdy zakrywa dokładnie dwa pola?

 To, że mowa jest o szachownicy, stanowi jakby podpowiedź. Wystarczy zauważyć, że usunięte pola miały ten sam kolor, a zatem pól jednego koloru pozostało o dwa więcej niż drugiego; ponieważ każdy kamień zakrywa dwa pola różnego koloru, więc wszystkich zakryć się nie da. Sprytne i proste.

Nierzadko zadanie to zamieszczane jest bez podpowiedzi, czyli pytanie dotyczy pokrywania dominem planszy 8×8 bez dwóch rogów, ale jednobarwnej. Tak jest trudniej, bo na szachownicowy sposób wpaść niełatwo. Kto go nie zna, będzie raczej szukał innego, analitycznego dowodu. Wówczas najwygodniej założyć na wstępie, że pokrycie jest możliwe, i zacząć od wypełniania kamieniami pierwszego rzędu, liczącego 7 pól. Znajdzie się w nim x kamieni leżących poziomo oraz nieparzysta liczba N=7–2x kamieni umieszczonych pionowo, które sięgną drugiego rzędu. W drugim rzędzie pozostanie więc pustych 8–N pól, czyli także liczba nieparzysta, a zatem w tym rzędzie również, podobnie jak w pierwszym, pojawi się nieparzysta liczba kamieni leżących pionowo, które sięgną trzeciego rzędu (przykładowy początkowy etap tworzenia takiego układu na rys. 2).

Kontynuując takie rozumowanie dla dalszych rzędów, dojdziemy do wniosku, że w każdych dwu kolejnych rzędach będzie nieparzysta liczba kamieni leżących pionowo, które całkowicie się w tych rzędach mieszczą. Takich sąsiednich par rzędów jest 7, więc liczba wszystkich kamieni leżących pionowo też będzie nieparzysta. Dokładnie taką samą analizę można przeprowadzić dla kolumn planszy i kamieni leżących w nich poziomo, wyciągając analogiczny wniosek, że liczba kamieni leżących poziomo też musi być nieparzysta. Liczba wszystkich kamieni, jako suma dwu liczb nieparzystych, będzie zatem parzysta, a tymczasem umieścić mamy 31 kamieni. Doszliśmy więc do sprzeczności, czyli wyszczerbionego kwadratu 8×8 dominem nie pokryjemy.

Jak widać, drugi dowód, choć dłuższy, jest bardziej uniwersalny – podobny do dowodu, z którego korzysta się przy rozwiązywaniu innego klasycznego zadania.

Udowodnij, że jeśli szachownicę pokryjemy 32 kamieniami domina, to liczba kamieni leżących pionowo będzie parzysta (więc leżących poziomo także).

W tym przypadku wniosek końcowy będzie „odwrotnością” podanego wyżej, jeśli chodzi o parzystość, czyli: w każdych dwu kolejnych rzędach pionowo leży parzysta liczba kamieni, całkowicie się w nich mieszczących. Znany jest także inny sprytny dowód, w którym korzysta się, podobnie jak w zadaniu Blacka, z odpowiedniego oznaczenia pól planszy 8×8 – tym razem zamiast szachownicy są pasy cyfr 0 i 1, jak na rys. 3. Każdy kamień umieszczony pionowo zakryje parzystą sumę cyfr (0 lub 2), a umieszczony poziomo – nieparzystą (1), suma zaś wszystkich cyfr do zakrycia parzystą liczbą kamieni jest parzysta, a zatem… z dokończeniem dowodu giętkie umysły z pewnością sobie poradzą.

Rys. 1

Rys. 2

Rys. 3

Rys.4

Gdy zadanie Blacka stało się znane, pojawiło się kilka jego odmian. Na przykład: Czy jeśli z szachownicy usuniemy dwa różnobarwne pola, to pokrycie dominem wszystkich pozostałych pól zawsze będzie możliwe? Okazuje się, że tak, a zaskakująco prosty dowód podał na początku lat 70. matematyk amerykański Ralph Gomory. Wystarczy oznaczyć na szachownicy trasę jej obejścia wieżą, zwaną cyklem hamiltonowskim, czyli taką, która przez każde pole przejdzie tylko raz i wróci do pola wyjściowego; kolory pól na trasie będą się oczywiście przeplatać. Możliwych tras jest bardzo wiele – przykład na rys. 4. Po usunięciu dowolnego białego pola i dowolnego niebieskiego cykl zostanie podzielony na dwie części lub przerwany w jednym miejscu (gdy oba pola będą kolejnymi na trasie). Cała trasa lub każda z jej dwu części będzie się jednak zawsze składać z parzystej liczby pól – tylu białych, ilu niebieskich – więc niezależnie od tego, czy będzie w jednym, czy w dwóch kawałkach, z jej wyłożeniem wzdłuż dominem nie będzie problemu.

Kamień domina to najkrótsza z klepek, czyli prostokątów 1×n (n≥2). Następną jest trimino – prostokąt 1×3. Szachownicy (8×8) triminem pokryć nie sposób, bo 64 nie dzieli się przez 3. A czy będzie to możliwe po usunięciu dowolnego pola? Problem jest ciekawy przede wszystkim ze względu na dowód podobny do szachownicowego, czyli z wykorzystaniem kolorowania pól. Tym razem jednak plansza jest trójbarwna (rys. 5).

Każde trimino zakrywa trzy pola różnych kolorów, czyli usunięte powinno być pole w nadmiarowym kolorze – w tym przypadku różowe, bo takie pola są 22; białych i niebieskich jest po 21. Czy po usunięciu lewego górnego pola zakryjemy planszę 21 triminami? Nie, bo gdyby tak było, to usunięcie dowolnego rogu stwarzałoby taką możliwość, gdy tymczasem dwa z nich nie są różowe. Stąd wniosek: należy usunąć różowe pole umieszczone w takim miejscu, że po obróceniu planszy o dowolną wielokrotność kąta prostego pojawi się w tym miejscu inne różowe pole. Inaczej mówiąc, do usunięcia kwalifikuje się dowolne z czterech różowych pól położonych symetrycznie względem każdego z trzech pozostałych. Taki kwartet jest tylko jeden – tworzą go narożne pola centralnego kwadratu 4×4. Po usunięciu dowolnego z nich pozostałe można pokryć triminem na wiele sposobów (przykład na rys. 6).

Rys. 5

Rys. 6

Kwadratową szachownicę m×m z usuniętymi polami na końcach tej samej przekątnej nazwiemy szachownicą Blacka. Pokrycie jej dominem nigdy nie będzie możliwe, niezależnie od wymiarów, czyli wartości m. To oczywiste, bo dla parzystych m dwa wycięte pola są zawsze jednakowego koloru, więc po ich usunięciu liczby pól w różnych kolorach będą różne. Natomiast dla m nieparzystych po usunięciu dwóch pól nieparzystość pozostaje, co automatycznie wyklucza pokrycie. A gdyby domino zastąpić triminem, a więc czy możliwe jest pokrycie szachownicy Blacka (m2–2)/3 kamieniami 1×3? Nie, ponieważ trójka nie jest dzielnikiem liczby o 2 mniejszej od kwadratu – można tego dowieść w sposób podobny do zamieszczonego przy rozwiązaniu trzeciego zadania z czerwcowego odcinka (ramka na s. 72).

Dalsze uogólnienie zadania polega na pokrywaniu szachownicy Blacka (m2–2)/n klepkami 1×n. Dla jakiego najmniejszego n pokrycie byłoby możliwe? Skoro wykluczyliśmy domino i trimino, to na starcie odpadną wszystkie n parzyste i wielokrotności trójki. Warunkiem koniecznym jest, aby n było dzielnikiem m2–2. Piątkę i jej wielokrotności trzeba więc także odrzucić, bo wtedy kwadrat musiałby się kończyć cyfrą 2 lub 7. W ciągu liczb dodatnich mniejszych o 2 od kwadratów (2, 7, 14, 23, 34, 47, 62, 79, 98, 119, 142, 167, 194, 223, 254, 287, 322, 359, 398, 439, 482, 527, …) jest wiele liczb podzielnych przez 7 (14, 98, 119, 287, 322, 574,…), co stwarza szansę na efektywne wykorzystanie typowych klepek parkietowych 1×7. Niestety, ani takimi, ani żadnymi dłuższymi klepkami 1×n szachownicy Blacka pokryć się nie da – liczbowy warunek konieczny nie jest wystarczający, rozstrzygająca okazuje się geometria. Pokrycie byłoby możliwe po zastąpieniu klepek płytkami o odpowiednim kształcie (przykład na rys. 7).

Większość dowodów niemożności pokrycia pokratkowanej figury klepkami 1×n jest oparta na kolorowaniu pól na różne sposoby. Zwykle szachownicowo, a ściślej – cyklicznie, bo w rzędach i kolumnach powtarza się n-kolorowy ciąg pól (szachownica powstaje dla n=2) – każda klepka zakrywa n pól różnego koloru. Kolorować lub oznaczać można także pasami, jak na rys. 3. Podstawą klepkowej logiki jest więc wybór właściwego sposobu kolorowania, które może być także oryginalne, jak choćby przy pokrywaniu kwadratu 10×10 klepkami tetromina (1×4). Arytmetyka podpowiada, że wystarczy wziąć 25 klepek i po kłopocie. Tymczasem sprytne pokolorowanie pól (rys. 8) natychmiast rozwiewa nadzieje: każda klepka zakryje parzystą liczbę pól danego koloru, a pól każdego koloru jest 25.

Rys. 7

Rys. 8

Krótkie klepki pojawiają się, poza dominem, w wielu grach towarzyskich. Jedną z bardziej znanych jest papierowo-ołówkowa bitwa morska. Występują w niej klepki-okręty 2-, 3- i 4-masztowe. Tradycyjnie na diagramie-akwenie 10×10 rozmieszcza się cztery 1-masztowce (1×1), trzy 2-masztowce (1×2), dwa 3-masztowce (1×3) i jeden 4-masztowiec (1×4). Okręty nie mogą się stykać nawet rogami, więc na diagramie jest sporo luzu, zatem jako gra bitwa morska ma z parkietem niewiele wspólnego. Jednak jako łamigłówka – przeciwnie; tak właśnie jest w drugim z poniższych zadań konkursowych.

 

1.     Ile co najmniej pól – tyle samo w każdym kolorze – i które (proszę podać współrzędne) należałoby usunąć z szachownicy 8×8, aby pokrycie dominem pozostałej części planszy nie było możliwe? Usunięte pola nie mogą dzielić szachownicy na części, jak np. na rys. 9 (przekreślone pola odcinają róg planszy, który praktycznie też należałoby uznać za usunięty).

2.     Diagram-akwen 8×8 zapełniony jest klepkami-okrętami (rys. 10) oraz 1-masztowcami (małe kwadraty). Należy ustalić położenie 10 z nich, składających się na standardową flotę umieszczoną pod diagramem. Kluczem do „wyłowienia” tej floty jest warunek obowiązujący w grze: pola zajmowane przez okręty nie mogą się stykać, nawet rogami. W rozwiązaniu wystarczy podać współrzędne 1-masztowców.

Rys.9

Rys.10

 

3.     Diagram 10×10 (rys. 11) należy pokryć klepkami 1×n – w tym płytkami 1×1, które także będziemy nazywać klepkami. Każda z cyfr określa długość klepki (n), w której powinna się znaleźć. Żadna klepka nie może obejmować więcej niż jednej cyfry (większość klepek nie obejmie żadnej cyfry). Klepki takiej samej długości nie mogą się ze sobą stykać. Żadne dwie klepki nie mogą się stykać tylko rogami. W rozwiązaniu wystarczy podać liczbę klepek 1×2.

4. Diagram 8×8 (rys. 12) należy pokryć takimi klepkami, jak w zadaniu 3. Tym razem jednak każda klepka powinna obejmować jedną cyfrę, która nie może być równa długości klepki, w której się znajduje. Żadne dwie klepki nie mogą się stykać tylko rogami. W rozwiązaniu wystarczy podać liczbę klepek 1×3.

Rys. 11

Rys. 12

 

Rozwiązania prosimy nadsyłać do 31 sierpnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG08/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ą Od splątania cząstek do kwantowej teleportacji Antona Zeilingera, ufundowaną przez wydawnictwo Prószyński Media.

 

Więcej w miesięczniku „Świat Nauki" nr 08/2013 »
Drukuj »
Komentarze
Dodany przez: SwiatNauki | 2013-07-29
Powinno być, oczywiście, UG08/13 – przepraszamy. Ale proszę się nie niepokoić – bez względu na tytuł maila, wyłowimy sierpniowe odpowiedzi.
Dodany przez: Smiley | 2013-07-29
Witam, czy w temacie e-maila na pewno ma się znaleźć UG06/13? Taki sam temat miały odpowiedzi z numeru czerwcowego. :)

Analogicznie do poprzednich tematów, numer sierpniowy jest ósmym z kolei czyli powinien zawierać UG08/13, prawda?

Dodany przez: m.penszko | 2013-07-25
Istotnie, przyczyną nadmiaru rozwiązań jest mój błąd, którego zresztą nietrudno się domyślić z rysunku: w zadaniu brak informacji, że n (długość klepki) powinno być nie większe niż 4. Oczywiście w tej sytuacji poprawne jest każde z podanych (i nie podanych :)) rozwiązań. Pozdrawiam mp
Dodany przez: Andrzej | 2013-07-25
Panie Marku, mam problem z rozwiązaniem, a właściwie z nadmiarem rozwiązań, trzeciego zadania konkursowego (rys.11).
Spośród wielu rozwiązań podam dwa przykładowe:

1)
3224224444
3434133313
3434221223
2434344443
2422355555
3334313331
1424666666
3424323232
3414323232
3422313131

Odp. 11

2)
3224224444
3434133313
3434221223
2434344443
2422322122
3334343334
1424141414
3424343434
3414343434
3422313431

Odp. 10 


Które z nich wybrać? 
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-07-22
Logika krótkich klepek

Amerykański filozof Max Black opublikował w 1946 roku książkę Critical thinking, w której zamieścił kilka prostych zadań, ilustrujących różne sposoby wnioskowania. Jedno z nich zrobiło światową karierę. Publikowane jest często jako łamigłówka i uchodzi za klasyczne w dziale matematyki zwanym geometrią kombinatoryczną.

Z szachownicy (8×8) usunięto dwa narożne pola (z końców tej samej przekątnej, rys. 1). Czy możliwe jest pokrycie całej „wybrakowanej” planszy kamieniami domina, z których każdy zakrywa dokładnie dwa pola?

 To, że mowa jest o szachownicy, stanowi jakby podpowiedź. Wystarczy zauważyć, że usunięte pola miały ten sam kolor, a zatem pól jednego koloru pozostało o dwa więcej niż drugiego; ponieważ każdy kamień zakrywa dwa pola różnego koloru, więc wszystkich zakryć się nie da. Sprytne i proste.

Nierzadko zadanie to zamieszczane jest bez podpowiedzi, czyli pytanie dotyczy pokrywania dominem planszy 8×8 bez dwóch rogów, ale jednobarwnej. Tak jest trudniej, bo na szachownicowy sposób wpaść niełatwo. Kto go nie zna, będzie raczej szukał innego, analitycznego dowodu. Wówczas najwygodniej założyć na wstępie, że pokrycie jest możliwe, i zacząć od wypełniania kamieniami pierwszego rzędu, liczącego 7 pól. Znajdzie się w nim x kamieni leżących poziomo oraz nieparzysta liczba N=7–2x kamieni umieszczonych pionowo, które sięgną drugiego rzędu. W drugim rzędzie pozostanie więc pustych 8–N pól, czyli także liczba nieparzysta, a zatem w tym rzędzie również, podobnie jak w pierwszym, pojawi się nieparzysta liczba kamieni leżących pionowo, które sięgną trzeciego rzędu (przykładowy początkowy etap tworzenia takiego układu na rys. 2).

Kontynuując takie rozumowanie dla dalszych rzędów, dojdziemy do wniosku, że w każdych dwu kolejnych rzędach będzie nieparzysta liczba kamieni leżących pionowo, które całkowicie się w tych rzędach mieszczą. Takich sąsiednich par rzędów jest 7, więc liczba wszystkich kamieni leżących pionowo też będzie nieparzysta. Dokładnie taką samą analizę można przeprowadzić dla kolumn planszy i kamieni leżących w nich poziomo, wyciągając analogiczny wniosek, że liczba kamieni leżących poziomo też musi być nieparzysta. Liczba wszystkich kamieni, jako suma dwu liczb nieparzystych, będzie zatem parzysta, a tymczasem umieścić mamy 31 kamieni. Doszliśmy więc do sprzeczności, czyli wyszczerbionego kwadratu 8×8 dominem nie pokryjemy.

Jak widać, drugi dowód, choć dłuższy, jest bardziej uniwersalny – podobny do dowodu, z którego korzysta się przy rozwiązywaniu innego klasycznego zadania.

Udowodnij, że jeśli szachownicę pokryjemy 32 kamieniami domina, to liczba kamieni leżących pionowo będzie parzysta (więc leżących poziomo także).

W tym przypadku wniosek końcowy będzie „odwrotnością” podanego wyżej, jeśli chodzi o parzystość, czyli: w każdych dwu kolejnych rzędach pionowo leży parzysta liczba kamieni, całkowicie się w nich mieszczących. Znany jest także inny sprytny dowód, w którym korzysta się, podobnie jak w zadaniu Blacka, z odpowiedniego oznaczenia pól planszy 8×8 – tym razem zamiast szachownicy są pasy cyfr 0 i 1, jak na rys. 3. Każdy kamień umieszczony pionowo zakryje parzystą sumę cyfr (0 lub 2), a umieszczony poziomo – nieparzystą (1), suma zaś wszystkich cyfr do zakrycia parzystą liczbą kamieni jest parzysta, a zatem… z dokończeniem dowodu giętkie umysły z pewnością sobie poradzą.

Rys. 1

Rys. 2

Rys. 3

Rys.4

Gdy zadanie Blacka stało się znane, pojawiło się kilka jego odmian. Na przykład: Czy jeśli z szachownicy usuniemy dwa różnobarwne pola, to pokrycie dominem wszystkich pozostałych pól zawsze będzie możliwe? Okazuje się, że tak, a zaskakująco prosty dowód podał na początku lat 70. matematyk amerykański Ralph Gomory. Wystarczy oznaczyć na szachownicy trasę jej obejścia wieżą, zwaną cyklem hamiltonowskim, czyli taką, która przez każde pole przejdzie tylko raz i wróci do pola wyjściowego; kolory pól na trasie będą się oczywiście przeplatać. Możliwych tras jest bardzo wiele – przykład na rys. 4. Po usunięciu dowolnego białego pola i dowolnego niebieskiego cykl zostanie podzielony na dwie części lub przerwany w jednym miejscu (gdy oba pola będą kolejnymi na trasie). Cała trasa lub każda z jej dwu części będzie się jednak zawsze składać z parzystej liczby pól – tylu białych, ilu niebieskich – więc niezależnie od tego, czy będzie w jednym, czy w dwóch kawałkach, z jej wyłożeniem wzdłuż dominem nie będzie problemu.

Kamień domina to najkrótsza z klepek, czyli prostokątów 1×n (n≥2). Następną jest trimino – prostokąt 1×3. Szachownicy (8×8) triminem pokryć nie sposób, bo 64 nie dzieli się przez 3. A czy będzie to możliwe po usunięciu dowolnego pola? Problem jest ciekawy przede wszystkim ze względu na dowód podobny do szachownicowego, czyli z wykorzystaniem kolorowania pól. Tym razem jednak plansza jest trójbarwna (rys. 5).

Każde trimino zakrywa trzy pola różnych kolorów, czyli usunięte powinno być pole w nadmiarowym kolorze – w tym przypadku różowe, bo takie pola są 22; białych i niebieskich jest po 21. Czy po usunięciu lewego górnego pola zakryjemy planszę 21 triminami? Nie, bo gdyby tak było, to usunięcie dowolnego rogu stwarzałoby taką możliwość, gdy tymczasem dwa z nich nie są różowe. Stąd wniosek: należy usunąć różowe pole umieszczone w takim miejscu, że po obróceniu planszy o dowolną wielokrotność kąta prostego pojawi się w tym miejscu inne różowe pole. Inaczej mówiąc, do usunięcia kwalifikuje się dowolne z czterech różowych pól położonych symetrycznie względem każdego z trzech pozostałych. Taki kwartet jest tylko jeden – tworzą go narożne pola centralnego kwadratu 4×4. Po usunięciu dowolnego z nich pozostałe można pokryć triminem na wiele sposobów (przykład na rys. 6).

Rys. 5

Rys. 6

Kwadratową szachownicę m×m z usuniętymi polami na końcach tej samej przekątnej nazwiemy szachownicą Blacka. Pokrycie jej dominem nigdy nie będzie możliwe, niezależnie od wymiarów, czyli wartości m. To oczywiste, bo dla parzystych m dwa wycięte pola są zawsze jednakowego koloru, więc po ich usunięciu liczby pól w różnych kolorach będą różne. Natomiast dla m nieparzystych po usunięciu dwóch pól nieparzystość pozostaje, co automatycznie wyklucza pokrycie. A gdyby domino zastąpić triminem, a więc czy możliwe jest pokrycie szachownicy Blacka (m2–2)/3 kamieniami 1×3? Nie, ponieważ trójka nie jest dzielnikiem liczby o 2 mniejszej od kwadratu – można tego dowieść w sposób podobny do zamieszczonego przy rozwiązaniu trzeciego zadania z czerwcowego odcinka (ramka na s. 72).

Dalsze uogólnienie zadania polega na pokrywaniu szachownicy Blacka (m2–2)/n klepkami 1×n. Dla jakiego najmniejszego n pokrycie byłoby możliwe? Skoro wykluczyliśmy domino i trimino, to na starcie odpadną wszystkie n parzyste i wielokrotności trójki. Warunkiem koniecznym jest, aby n było dzielnikiem m2–2. Piątkę i jej wielokrotności trzeba więc także odrzucić, bo wtedy kwadrat musiałby się kończyć cyfrą 2 lub 7. W ciągu liczb dodatnich mniejszych o 2 od kwadratów (2, 7, 14, 23, 34, 47, 62, 79, 98, 119, 142, 167, 194, 223, 254, 287, 322, 359, 398, 439, 482, 527, …) jest wiele liczb podzielnych przez 7 (14, 98, 119, 287, 322, 574,…), co stwarza szansę na efektywne wykorzystanie typowych klepek parkietowych 1×7. Niestety, ani takimi, ani żadnymi dłuższymi klepkami 1×n szachownicy Blacka pokryć się nie da – liczbowy warunek konieczny nie jest wystarczający, rozstrzygająca okazuje się geometria. Pokrycie byłoby możliwe po zastąpieniu klepek płytkami o odpowiednim kształcie (przykład na rys. 7).

Większość dowodów niemożności pokrycia pokratkowanej figury klepkami 1×n jest oparta na kolorowaniu pól na różne sposoby. Zwykle szachownicowo, a ściślej – cyklicznie, bo w rzędach i kolumnach powtarza się n-kolorowy ciąg pól (szachownica powstaje dla n=2) – każda klepka zakrywa n pól różnego koloru. Kolorować lub oznaczać można także pasami, jak na rys. 3. Podstawą klepkowej logiki jest więc wybór właściwego sposobu kolorowania, które może być także oryginalne, jak choćby przy pokrywaniu kwadratu 10×10 klepkami tetromina (1×4). Arytmetyka podpowiada, że wystarczy wziąć 25 klepek i po kłopocie. Tymczasem sprytne pokolorowanie pól (rys. 8) natychmiast rozwiewa nadzieje: każda klepka zakryje parzystą liczbę pól danego koloru, a pól każdego koloru jest 25.

Rys. 7

Rys. 8

Krótkie klepki pojawiają się, poza dominem, w wielu grach towarzyskich. Jedną z bardziej znanych jest papierowo-ołówkowa bitwa morska. Występują w niej klepki-okręty 2-, 3- i 4-masztowe. Tradycyjnie na diagramie-akwenie 10×10 rozmieszcza się cztery 1-masztowce (1×1), trzy 2-masztowce (1×2), dwa 3-masztowce (1×3) i jeden 4-masztowiec (1×4). Okręty nie mogą się stykać nawet rogami, więc na diagramie jest sporo luzu, zatem jako gra bitwa morska ma z parkietem niewiele wspólnego. Jednak jako łamigłówka – przeciwnie; tak właśnie jest w drugim z poniższych zadań konkursowych.

 

1.     Ile co najmniej pól – tyle samo w każdym kolorze – i które (proszę podać współrzędne) należałoby usunąć z szachownicy 8×8, aby pokrycie dominem pozostałej części planszy nie było możliwe? Usunięte pola nie mogą dzielić szachownicy na części, jak np. na rys. 9 (przekreślone pola odcinają róg planszy, który praktycznie też należałoby uznać za usunięty).

2.     Diagram-akwen 8×8 zapełniony jest klepkami-okrętami (rys. 10) oraz 1-masztowcami (małe kwadraty). Należy ustalić położenie 10 z nich, składających się na standardową flotę umieszczoną pod diagramem. Kluczem do „wyłowienia” tej floty jest warunek obowiązujący w grze: pola zajmowane przez okręty nie mogą się stykać, nawet rogami. W rozwiązaniu wystarczy podać współrzędne 1-masztowców.

Rys.9

Rys.10

 

3.     Diagram 10×10 (rys. 11) należy pokryć klepkami 1×n – w tym płytkami 1×1, które także będziemy nazywać klepkami. Każda z cyfr określa długość klepki (n), w której powinna się znaleźć. Żadna klepka nie może obejmować więcej niż jednej cyfry (większość klepek nie obejmie żadnej cyfry). Klepki takiej samej długości nie mogą się ze sobą stykać. Żadne dwie klepki nie mogą się stykać tylko rogami. W rozwiązaniu wystarczy podać liczbę klepek 1×2.

4. Diagram 8×8 (rys. 12) należy pokryć takimi klepkami, jak w zadaniu 3. Tym razem jednak każda klepka powinna obejmować jedną cyfrę, która nie może być równa długości klepki, w której się znajduje. Żadne dwie klepki nie mogą się stykać tylko rogami. W rozwiązaniu wystarczy podać liczbę klepek 1×3.

Rys. 11

Rys. 12

 

Rozwiązania prosimy nadsyłać do 31 sierpnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG08/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ą Od splątania cząstek do kwantowej teleportacji Antona Zeilingera, ufundowaną przez wydawnictwo Prószyński Media.