Termit
Do sześcianu utworzonego z 27 sześciennych drewnianych klocków zbliża się termit z rodziny kubikojadów.
Ten żarłoczny owad ma niecny plan: chce zjadać klocki. Pierwszego dnia postanowił zjeść jeden cały klocek, a drugiego i każdego następnego dnia zamierza konsumować doszczętnie kolejny – taki, który styka się ścianką (a właściwie stykał się przed konsumpcją) ze zjedzonym wczoraj. Trasę wyżerki zamierza zakończyć, pałaszując 27. dnia ostatni, centralny klocek sześcianu. Czy mu się to uda?
Krótka odpowiedź „tak” lub „nie” nie wystarczy. Należy ją uzasadnić, czyli podać jakiś elegancki (krótki, jasny i ewentualnie sprytny) sposób rozwiązania.
Komentarze
Nie jest to możliwe.
Pokolorujmy wszystkie klocki sześcianu naprzemiennie na biało i czarno. Dla ustalenia uwagi załóżmy, że centralny klocek jest biały. Wówczas sześcian składa się z 13 klocków białych i 14 klocków czarnych. Termit zjada naprzemiennie klocki raz biały, raz czarny. Jeśli miałby zjeść wszystkie klocki musiałby zatem zacząć od czarnego i zakończyć wyżerkę na czarnym klocku. Warunki zadania wymuszały jednak zakończenie pochodu na białym, centralnym klocku.
Nie da się!
Klocki malujemy w szachownicę, tzn. narożniki sześcianu oraz środki jego ścian malujemy na czarno, pozostałe klocki (środki krawędzi sześcianu oraz klocek centralny zostają białe).
Klocków czarnych jest 14 a białych 13.
Gdyby termit mógł zrealizować swój plan, to przez pierwsze 26 dni musiałby zjeść 14 czarnych i 12 białych klocków (bo ostatni klocek – centralny – jest biały), czyli pewne dwa czarne klocki musiałby zjeść jeden po drugim – a to niemożliwe, bo czarne klocki nie sąsiadują ze sobą.
Pokolorujmy naprzemiennie, jak przestrzenną szachownicę, poszczególne klocki sześcianu. Przyjmijmy, że środkowy klocek jest biały. Kornik zjada klocki mające wspólną ścianę a zatem naprzemiennie biały i czarny. Ponieważ jest komórek 27 to aby skończyć na białym musi zacząć na białym. Zatem w ciągu ruchów powinno być 14 białych i 13 czarnych. W kostce jest jednak tylko 13 białych klocków, zatem nie ma ścieżki spełniającej podane warunki.
Zanim ten teserakt „rozgryzę”, zapodam starą, podobną (ale nie do końca) zagadkę. W bibliotece na półce stoi 10 książek – każda ma 100 kartek. Dla uproszczenia – razem z okładkami, które są numerowane (czyli numer pierwszej i ostatniej strony jest na kładce). Książki stoją na półce w porządku od lewej do prawej
1, 2, …, 10
Mol przegryza się od pierwszej strony pierwszej książki do ostatniej strony ostatniej książki. Ile kartek przegryzie, jeżeli nic go nie zatrzyma?
(Przepraszam, ale widząc owada, nie mogłem się powstrzymać).
Ode mnie na początek żarcik programistyczny: https://snag.gy/hmOVyt.jpg
A teraz zwięzłe uzasadnienie. Bloki można podzielić na dwie grupy: te, które znajdują się na środku krawędzi lub środkowy (13 sztuk) oraz pozostałe (narożniki + środki ścian = 14). Każdy blok graniczy wyłącznie z blokami z przeciwnej grupy, więc aby przejść przez wszystkie musimy zacząć i zakończyć ścieżkę w większej grupie, do której środkowy blok nie należy.
@bubekró
To zależy, czy skrajne książki na półce stoją w klasyczny sposób (wtedy przegryzie tylko po 100 kartek każdej z wewnętrznych książek (od 2 do 9) – czyli w sumie 800 kartek), czy może do góry nogami albo grzbietem do wnętrza półki – wtedy może wyjść 900 lub 1000 kartek.
@bubekró
Gdzie jest haczyk? 😉 Bo przypuszczam, że odpowiedź 1000 jest zbyt prosta?
A może miało być – każda książka ma 100 stron? I wówczas odpowiedź 500?
@ bubekró
1000 lub 802 lub 901. Wynik zależy jak rozumiemy pierwsza i ostatnia karta.
@miodziu
Tak, chodzi o ułożenie klasyczne. Dlatego w zagadce jest mowa o bibliotece. (Dziękuję gospodarzowi za puszczenie zagadki)
Granie w szachy popłaca… Malujemy kostki „na przemian” na czarno i biało. Powiedzmy, że zaczynamy od czarnej – wtedy musimy skończyć również na czarnej (27 kostek). Ta w środku jest biała, więc się nie uda.
Kolorujemy kostkę jak trójwymiarową szachownicę. Każdy jednostkowy sześcian jest albo biały albo czarny. Białe sąsiadują tylko z czarnymi a czarne z białymi. Załóżmy, że białych jest 13, czarnych 14. Z kolorowania widać, że środkowy sześcian jest biały. Lecz aby przejść przez wszystkie sześcianiki to drogę należy zacząć od czarnego i skończyć na czarnym. Z tego wynika, że nie można żeżreć w ten sposób wszystkich klocków.
Sprawdzimy czy możliwa jest droga powrotna termita, od środka sześcianu do końca w środku ściany, środku krawędzi lub wierzchołku, które będziemy odpowiednio oznaczać S, K, W. Po chwili zastanowienia widzimy, że możliwe są tylko następujące przejścia: S->K->W i W->K->S co możemy złożyć w jeden graf skierowany w kształcie ósemki z K w środku oraz S i W na jej antypodach. W nienaruszonym sześcianie mamy 1 środek sześcianu,
6 – S, 12 – K, 8-W, razem 27 kostek. Pierwsze 3 ruchy są jednoznacznie określone: środek sześcianu->S->K.
Teraz termit znajduje się w środku grafu w K. Ilości pozostałych kostek są: S=5, K=11, W=8, razem 24 kostki.
Ponieważ z K możemy pójść tylko do S lub W, a z S lub W możemy pojść tylko do K to możemy to zapisać w postaci łańcucha:
K->SW->K->SW->…->SW->K. Długość tego łańcucha od pierwszego SW do ostatniego K wynosi 24 bo tyle kostek termit ma jeszcze pożreć. Skoro tak, to termit musi pochłonąć jeszcze 12 kostek typu K a jest ich tylko 11. Stąd wynika, że termitowi zamierzona sztuka się nie uda 🙂
Tu chyba chodzi o wpuszczenie rozwiązującego w kanał myślenia o kartkach podczas gdy na końcu zadajemy podstępnie pytanie o ilość stron, których jest 2 razy więcej niż kartek ??? 😉
Aby ułatwić termitowi zadanie, pomalujmy klocki na dwa kolory. Na czarno 14 klocków – 8 narożnych i 6 na środkach każdej ściany. Na biało 13 pozostałych, czyli 12 na środkach krawędzi sześcianu oraz 1 w środku sześcianu. Jak łatwo zauważyć, ani klocki czarne nie stykają się ze sobą, ani klocki białe – zawsze sąsiadują ze sobą klocki różnych kolorów. Skoro termit postanowił zjadać kolejno klocki sąsiadujące, musi na zmianę zjadać białe i czarne. Po to, by zjeść wszystkie, musi zacząć konsumpcję od klocka czarnego i na czarnym klocku zakończyć. A ponieważ klocek w środku sześcianu jest biały, to nie może być zjedzony jako ostatni.
100? 😉
A jeśli chodzi o główne zadanie, to… nie mogę znaleźć rozwiązania, chociaż podchodziłam wielokrotnie. A jak nie mogę go znaleźć, to go nie ma 😉
@ Baś
Wspaniała odpowiedź:
żadnego zbędnego słowa o jakichś tam „czarnych i białych na przemian”, czy innym „parity check”,
tylko
po prostu:
„nie da się, bo ja nie mogę go znaleźć”.
W skrypcie z mojego poprzedniego komentarza jest błąd w założeniach: analizowałem ścieżki od końca i przyjąłem, że wszystkie rozpoczynają się od bloku w środku ściany, następnie przechodzą do bloku na środku krawędzi i w trzecim kroku muszą skręcić do narożnika, w związku z czym wszystkie początki po odbiciach/obrotach sprowadzają się do tego samego. A przecież w trzecim kroku możemy przejść do bloku na środku sąsiedniej ściany.
Nie zmienia to końcowego efektu, ścieżki o długości 26 nie ma.
Zabarwiwszy wszystkie klocki jednym z dwóch kolorów tak, żeby sąsiadujące bokami miały różne barwy widać, że każdy kolejny zjedzony klocek ma inny kolor niż poprzedni, a więc nie da się zjeść wszystkich kończąc na środkowym, bo takich jak on jest o jeden mniej, niż tych w drugim kolorze 🙂
Nie.
Wśród liczb od 1 do 27 jest 14 nieparzystych i 13 parzystych.
Termit zacznie konsumpcję w dniu nieparzystym (1.) i w dniu nieparzystym (27.) ją zakończy.
Pomalujmy na czarno narożne kubiki (całe) oraz te stykające się z nimi rogami (też całe) tak, że – niczym na szachownicy – dwa pomalowane kubiki nigdy nie będą stykały się ze sobą ścianami. W ten sposób 14 kubików będzie pomalowanych, a 13 niepomalowanych. Wśród niepomalowanych znajdzie się centralny kubik.
Jeśli termit zacznie konsumpcję od któregoś z 14 kubików pomalowanych to zakończyć ją będzie mógł także tylko na kubiku pomalowanym. Natomiast jeśli zacznie konsumpcję od kubika niepomalowanego (np. centralnego) to w 25. dniu skonsumuje ostatni taki kubik i zostaną mu do skonsumowania dwa kubiki pomalowane. Ponieważ takie nie stykają się ze sobą ścianami, to termit nie da rady skonsumować wszystkich.
To zadanie skojarzyło mi się z tym: http://penszko.blog.polityka.pl/2010/06/01/1×3-1×1/
co ułatwiło drogę do rozwiązania. 🙂
Zreflektowałem się co do założenia, które towarzyszyło mi od początku rozumowania tj. że jest wszystko jedno czy termit zacznie czy skończy na kubiku centralnym. Skoro ma na centralnym kubiku zakończyć, to należy przeanalizować jego ruchy wstecz. To prowadzi do analogicznego wniosku, czyli termit musiałby zacząć od zjedzenia dwóch pomalowanych kubików – co jest wykluczone – aby ostatniego dnia skonsumować niepomalowany.
@apartado
Wiedziałam że znajdzie się ktoś z humorem 🙂
@bubekró
Nie dostałam od Ciebie pochwały, a może nawet 10 minut zajęło mi rozwiązanie 🙁