8 skrypt - plansze

SAVE OFFLINE

Internetowe Kółko Olimpiady Matematycznej Juniorów 8. Plansze W wielu zadaniach pojawia się motyw umieszczania jakichś obiektów na planszy. Mogą to być różnego rodzaju „klocki” (np. prostokąty 2 × 1), którymi tę planszę chcemy wypełnić, różne pionki czy figury podobne do szachowych, które chcemy umieszczać tak, by żadne dwie się nie biły lub liczby, które wpisujemy w pola tablicy przy zachowaniu pewnych reguł (np. suma w każdym wierszu i kolumnie ma być równa zeru). W tego typu zadaniach często pomocne jest pokolorowanie pól danej planszy. Może się na przykład okazać, że przy kolorowaniu na biało i czarno każdy „klocek” umieszczony na szachownicy pokrywa jedno pole białe i jedno czarne. Jeżeli pól białych nie jest tyle samo, co pól czarnych, wnioskujemy, że nie da się planszy wypełnić danymi klockami (patrz zad. 1). Analogiczne rozumowania są też często pomocne w zadaniach z figurami szachowymi czy liczbami na planszach. Czasem zamiast kolorowania warto wpisać liczby w pola tablicy (np. -1 w białe pola szachownicy i 1 w czarne) i patrzeć na sumę wszystkich wpisanych liczb oraz na sumy liczb pokrywanych przez dane klocki. Jeżeli np. każdy klocek pokrywa pola o sumie -2, 0 lub 2, to na pewno nie pokryjemy planszy o sumie pól 101, gdyż sumowanie dowolnej liczby liczb -2, 0 i 2 nie może dać nieparzystego wyniku. Uwaga: jeśli dane kolorowanie nie prowadzi do sprzeczności, nie oznacza to, że planszę da się wypełnić zadanymi klockami. Czasami trzeba wypróbować kilka różnych kolorowań.

Zadania 1. Z kwadratowej planszy 4 × 4 usunięto przeciwległe narożniki, otrzymując planszę z czternastoma polami. Czy da się ją wypełnić siedmioma prostokątami o wymiarach 2 × 1? Prostokąty można obracać o 90°. 2. Ile maksymalnie wież można umieścić na szachownicy o wymiarach 8 × 8 tak, by żadne dwie się nie biły? Dwie wieże biją się, jeżeli znajdują się w tej samej kolumnie lub w tym samym wierszu. 3. Dana jest plansza o wymiarach 5 × 5 i skoczek (koń szachowy) w jej narożniku. Po pewnej liczbie ruchów okazało się, że skoczek wrócił na pole, z którego zaczął. Czy możliwym jest, by skoczek był na każdym polu dokładnie raz (poza polem startowym, na którym nie był ani razu poza pierwszym i ostatnim ruchem)? 4. Klockiem nazwiemy figurę powstałą po przyłączeniu kwadratów 1 × 1 do trzech boków kwadratu 1 × 1. Czy z 25 klocków da się ułożyć kwadrat o wymiarach 10 × 10? 5. Ile najwięcej króli można umieścić na szachownicy 8 × 8 tak, by żadne dwa się nie biły? Dwa króle biją się, jeżeli stoją na polach o wspólnym boku lub wspólnym wierzchołku. 6. Z kwadratowej planszy o boku 99 usunięto jeden narożnik. Czy możliwe jest pokrycie otrzymanej planszy prostokątami o wymiarach 5 × 1? Prostokąty można obracać o 90°. 7. Czy kwadratową planszę o boku 100 da się wypełnić klockami w kształcie litery Z (jak na rysunku)?

8. Kwadratową planszę o wymiarach n × n pokryto kwadratami o wymiarach 3 × 3 i 2 × 2. Udowodnij, że tę samą planszę można pokryć tylko kwadratami 3 × 3 lub tylko kwadratami 2 × 2. 9. (Obóz Naukowy OMG na poziomie OM w 2016 roku) Czy kwadrat o boku 1000 można tak podzielić na prostokąty, z których każdy ma wymiary 2 × 7 lub 3 × 5, aby dłuższe boki wszystkich prostokątów podziału były równoległe? 10. Kwadratową planszę o boku 7 pokryto szesnastoma klockami o wymiarach 3 × 1 i jednym klockiem 1 × 1. Udowodnij, że klocek 1 × 1 leży na środku planszy lub przy jej krawędzi. Liga Zadaniowa 22. Dany jest trójkąt równoboczny o boku długości 6, podzielony na 36 jednostkowych trójkątów równobocznych. Czy da się go rozciąć na klocki o następującym kształcie:

Równoległobok na rysunku składa się z 4 trójkątów równobocznych o boku długości 1. Odpowiedź uzasadnij. 23. Z kwadratowej planszy o boku 7 usunięto wszystkie cztery narożniki. Czy możliwe jest pokrycie otrzymanej planszy prostokątami o wymiarach 3 × 1? Prostokąty można obracać o 90°. Odpowiedź uzasadnij. 8. Internetowe Kółko OMJ, tydzień 15.12.2019 – 21.12.2019

1

24. Dana jest tablica o wymiarach 2 × 2019. Każde pole tej tablicy jest pokolorowane na czerwono, niebiesko lub zielono. Wyznaczyć liczbę takich kolorowań, że żadne dwie sąsiadujące (bokiem) kratki nie są tego samego koloru.

Regulamin 1. Rozwiązania powyższych zadań Ligi należy przesłać na adres [email protected] najpóźniej do dnia 21 grudnia 2019 r. (sobota), godz. 23:59. 2. Wysłanie rozwiązań zadań na podany adres jest równoważne z wyrażeniem zgody na przetwarzanie danych osobowych (imię, nazwisko, klasa) oraz publikację imienia, nazwiska i klasy uczestnika na facebookowej stronie Olimpiady Matematycznej Juniorów w przypadku uzyskania dobrego wyniku.

Podpowiedzi do zadań 1. Pokoloruj planszę jak szachownicę na biało i czarno. Ile pól każdego koloru będzie zakrytych przez rozważane 7 kostek domina? 2. Popatrz na każdą kolumnę osobno. 3. Pokoloruj planszę jak szachownicę. Na jakich kolorach pól skoczek staje w swoich ruchach? Ile ruchów wykona? 4. Pokoloruj kwadrat 10 × 10 jak szachownicę. 5. Podziel szachownicę na 16 kwadratów 2 × 2. 6. Rozważ 5 kolorów A, B, C, D, E. Koloruj kolejne kolumny kolorami A, B, C, D, E, A, B, C, D, E, . . . . 7. Rozważ położenie domina, które pokrywa jeden z rogów. Sprawdź, czy możliwe jest pokrycie wszystkich pól przy krawędzi planszy. 8. Wpisz w kolejne kolumny liczby -1, 1, -1, 1,. . . . 9. Niech dłuższe boki będą pionowe. Wpisz w kolejne kolumny liczby -1, 0, 1, -1, 0, 1, . . . . 10. Pokoloruj przekątne na trzy kolory (cyklicznie), a następnie zastosuj analogiczny argument w kolorowaniu obróconym o 90°.

8. Internetowe Kółko OMJ, tydzień 15.12.2019 – 21.12.2019

2