Gra w mrówki
Kto miał lub ma w domu mrówki, ten wie, że niełatwo się ich pozbyć. Od niedawna podobne zagrożenie pojawiło się w Łamiblogu, do którego nieopatrznie wpuściłem rój formica aenigmistica. Mam nadzieję, że już niedługo zabawią, a sytuacja nie wymknie się spod kontroli, czyli mrówki nie pójdą w ślady Krzyżaków sprowadzonych przez Konrada Mazowieckiego. Tymczasem przypominam zadanie sprzed dwóch tygodni, które wówczas przytoczyłem niejako przy okazji.
Na wielościanie wypukłym znajduje się tyle mrówek, co ścian. Każda ściana należy do jednej mrówki i każda z nich cały czas wędruje po krawędzi wokół swojej ściany zgodnie z ruchem wskazówek zegara, przemieszczając się w ciągu godziny o co najmniej 1 milimetr. Należy dowieść, że po pewnym czasie jakieś dwie mrówki na pewno się spotkają.
Ku mojemu miłemu zaskoczeniu kilka tęgich głów spróbowało się z tym uporać. Z dowodami jest jednak sprawa równie trudna, jak z namolnymi mrówkami. Najlepszym przykładem są rygory dotyczące uznania za poprawne rozwiązań tzw. problemów milenijnych. Szacowne grono matematycznych autorytetów ma dwa lata na ustalenie, czy zgłoszony dowód, stanowiący rozwiązanie problemu, jest pod każdym względem bez zarzutu i delikwentowi należy się milion dolarów.
Czytając dowód (komentarz z 27 marca) nadesłany przez spiritus movens Łamiblogu Andrzeja69, poczułem się trochę tak, jakbym należał do szacownego grona. Poczucie megalomańskie i całkiem bezzasadne, bo matematycznych papierów nie posiadam, zresztą łamigłówkowych też nie. Mimo to ośmielę się wyrazić opinię na temat wspomnianego dowodu. Bardzo proszę Panie Andrzeju o potraktowanie formy poniższych uwag z przymrużeniem oka – zwłaszcza w dniu tego wpisu.
Dowód jest bardzo śmiały. Przeprowadzając go autor dokonuje tak radykalnych modyfikacji sytuacji wyjściowej, że przydałyby się dodatkowe dowody w celu wykazania, że proponowane zmiany nie wpływają na poprawność dowodu głównego. Największe wrażenie zrobiły na mnie wstęp i zakończenie. Mam na myśli uwagę poddającą w wątpliwość potrzebę informacji o minimalnym dystansie pokonywanym przez mrówki w ciągu godziny oraz oparcie dowodu na „spodzie” wielościanu. Z oparcia wynika, że gdyby pozbawić wielościan spodniej ścianki, to spotkania mrówek można by uniknąć. Otóż nie w tym rzecz, to znaczy nie spód warunkuje nieuchronność spotkania.
Początkowo zamierzałem przedstawić dowód, ale przyszedł mi do głowy pomysł pewnej prostej gry dla jednej osoby (w rodzaju klasycznego samotnika), która ten dowód nieco przybliża. Jeśli nikt nie skorzysta z gry-podpowiedzi, to doprowadzę temat do końca w jednym z najbliższych wpisów.
Załóżmy, że z wielościanu usunięto jedną ścianę, np. spód 
, pozostałe „rozpłaszczono”, a na bokach-krawędziach dorysowano pola gry – małe kółeczka, po jednym na każdym boku. Na tych polach umieszczamy zamiast mrówek pionki tak, by na obwodzie każdego wieloboku znalazł się dokładnie jeden pionek do tego wieloboku przypisany (taka sama litera na wieloboku i odpowiadającym mu pionku). Ponadto pionki rozmieszczone są w pewien „sprytny” sposób, ale szczegółów nie ujawnię, bo wówczas do dowodu byłoby zbyt blisko. Sytuacja wygląda jak na poniższym rysunku.
Ruch polega na przesunięciu pionka po obwodzie odpowiadającego mu wieloboku o dowolną liczbę pustych pól zgodnie z ruchem wskazówek zegara. Zabawa jest wieloetapowa – w każdym etapie należy wykonać dziesięć ruchów różnymi pionkami. Im więcej etapów uda się pokonać, tym lepszy wynik. Jaka może być maksymalna liczba etapów przy takim jak na rysunku „sprytnym” początkowym rozmieszczeniu pionków? Wydaje się, że nie jest to liczba oszałamiająca.
Pora na wyniki SET!-konkursu zamieszczonego w poprzednim wpisie. Wszyscy uczestnicy zabawy nadesłali poprawne rozwiązanie (3-5-6), choć szukanie setów wśród 18 samochodów było dość żmudne. Nagrodę, grę SET! wylosował Andrzej69. Fundatorem nagrody jest hurtownia gier Rost.
Laureata proszę o kontakt pod adresem m.penszko@polityka.com.pl w celu ustalenia sposobu postawienia SET-y .
Komentarze
Na wstępie chciałbym podziękować Panu, Panie Marku za miły komplement (czy ten spiritus to w związku z setą? 😉 ) choć jest on moim zdaniem zdecydowanie przesadzony, a także za docenienie moich wysiłków (choć jak na razie – z marnym skutkiem) oraz bardzo delikatne określenie tego, że przedstawiony przeze mnie dowód jest – nazywając po imieniu – do chrzanu :-(.
Poza tym chciałbym również przeprosić tych, którym obiecałem odpowiedź w sobotę wieczór, a do tej pory jej nie udzieliłem. Przyznam się, że niestety w ów dzień „padłem” kompletnie i zabrałem się za pisanie dopiero w niedzielę. Przygotowałem wówczas pierwszą część tej odpowiedzi (dotyczącą kwestii prędkości), którą zamieszczam poniżej, ale pisząc jej drugi człon – dotyczący uzupełnienia luki w moim dowodzie (bo luka oczywiście była i jest) – spostrzegłem, że wymyślony przeze mnie wcześniej (jeszcze w piątek) sposób w jaki chciałem to zrobić jest niestety również wadliwy (tzn. nie działa w jednej, przeoczonej przeze mnie, szczególnej sytuacji, o której dalej – ale to niestety kładzie całość). Także w tym momencie przerwałem pisanie i wróciłem do dowodu. Udało mi się znaleźć nową ideę (a właściwie to uzupełnić starą – bo koncepcja ta istniała już przed wersją, którą przedstawiłem), natomiast nie zdążyłem doprowadzić sprawy do końca (w obecnej postaci pozwala ona na dowód tego twierdzenia, ale przy założeniu, że w żadnym narożu wielościanu nie zbiegają się więcej niż trzy krawędzie) i dlatego też nic nie napisałem. Wczoraj (poniedziałek) byłem jeszcze całkiem „wyłączony z gry” przez sprawy służbowe, ale od dzisiaj (wtorek) wracam do tematu i mam nadzieję (a przynajmniej będę się starał) coś z tym zrobić.
A oto moja napisana wcześniej, ale nie wysłana, wypowiedź w kwestii prędkości:
……………………………….
Chyba nie do końca się zrozumieliśmy.
Nie musicie mnie przekonywać, że jeśli prędkość będzie stale malała do zera, a jednocześnie szereg sum częściowych „mikroodcinków” drogi (co sprowadza się do całki) jest zbieżny, to mrówka, nawet w nieskończenie długim czasie, przejdzie tylko konkretny odcinek i ani kawalątka dalej.
Chodziło mi o coś innego.
Po pierwsze:
O zbędne podawanie konkretnych wartości („przynajmniej milimetr na godzinę”). Poruszając się dwukrotnie wolniej mrówki także sprawią zadość tezie. W tym miejscu równie dobrze mogłyby się znaleźć dowolne inne jednostki (tylko proszę nie proponować nanometr i wiek 🙂 ).
Jeżeli zaś chcemy się zabezpieczyć przed wspomnianą ewentualnością może lepiej by było wyrazić to wprost.
Po drugie:
Wspomniane zabezpieczenie, wyrażone tak czy tak, do niczego nie prowadzi, jeżeli nic nie wiadomo o wielkości wielościanu.
Pisząc w poprzednim komentarzu o bardzo dużym jego rozmiarze miałem na myśli to, że mrówkom życia może nie starczyć na choć jednokrotne jego obejście (Esteonie, widziałeś mrówkę żyjącą przeszło dwa tysiące lat? 🙂 ).
A jeśli nawet założymy, że mamy do czynienia z teoretycznymi – nieśmiertelnymi i niestrudzonymi – mrówkami, to nie uważam, aby było błędem przyjęcie, że długość boku wielościanu może dążyć do nieskończoności. Mówi się czasem o sytuacji gdy wielkość danej figury maleje do zera (co sprowadzają do punktu), ale jednak dalej traktuje się ją jako daną figurę. A wielkości nieskończenie duże są w końcu równoprawne z nieskończenie małymi. Skoro prędkość może zmierzać do zera i dalej jest to jeszcze przemieszczanie się (czego nie neguję), a nie stanie w miejscu, to czemu wielościan o nieskończenie długim boku nie miałby być wielościanem? Wcale to przecież nie oznacza całej przestrzeni – nieskończoności, jak wiadomo, mogą być „mniejsze” i „większe” (taki skrót myślowy – proszę się nie czepiać 😉 ).
I jeszcze konkretny przykład:
Jednym ze sposobów obliczania liczby PI jest uznanie koła jako wielokąta o nieskończenie wielu nieskończenie krótkich bokach. Mimo dwukrotnie występującej nieskończoności (zarówno „dużej” jak i „małej”) w żaden sposób nie przeszkadza to, w traktowaniu tej figury dalej jako wielokąta i obliczania obwodu (lub pola) metodą jemu właściwą, choć przecież w rzeczywistości jest to koło!
Generalnie zmierzam do tego, co już napisałem poprzednio, ale pozwolę sobie powtórzyć. Albo jesteśmy bardzo formalistyczni i drobiazgowi tworząc KOMPLETNE założenia (co jest absolutnie niezbędne w poważnych twierdzeniach matematycznych), albo traktujemy sprawę skrótowo licząc (można ewentualnie o tym wspomnieć) na zdrowy rozsądek rozwiązującego (co wydaje mi się może być dopuszczalne w łamigłówkach).
Takie jest moje zdanie w tej kwestii. Ale aby nie kontynuować tego sporu (którego tak naprawdę chyba nie ma, tylko mam wrażenie, że nasze argumenty „się mijają”) mam pewną propozycję. Reguła, która powinna załatwić tę sytuację (tzn. zarówno prędkość jak i rozmiar), a jednocześnie nie odwoływać się ani do konkretnych jednostek, ani do wielkości nieskończenie dużych i małych (co mogłoby być niestrawne dla niektórych czytających 😉 i psuć „lekkość” łamigłówki) mogłaby brzmieć np. tak:
„Każda mrówka przynajmniej raz dokona pełnego obejścia swojej ściany.”
Wydaje mi się, że to powinno wystarczyć, ale przyznaję nie sprawdziłem dokładnie – może ktoś inny to zrobi? 😉 Jeśli jednak jest to za słabe założenie, wówczas można wspomnieć o konieczności kilkukrotnego okrążenia (wtedy będzie z zapasem).
Mam nadzieję, że teraz i wilk będzie syty, i owca cała.
……………………………….
Tyle a propos prędkości, a teraz chciałbym jeszcze wrócić do kwestii samego dowodu „mrówczego wielościanu”:
Zarzut Michała w stosunku do mojego dowodu jest oczywiście jak najbardziej trafny.
Mrówka zastępcza (wypadkowa dwóch lub więcej) – tak ją będę w dalej nazywać – rzeczywiście porusza się trochę inaczej niż zwykła (pojedyncza).
Ten inny sposób przemieszczania się wynika z faktu, iż mrówka wędrująca środkową krawędzią (rozdzielającą dwie łączone ściany) najpierw musi z niej zejść, a dopiero później druga mrówka może na nią wejść. Gdyby między tymi dwoma zdarzeniami nie występowała ani chwila przerwy, to mrówka zastępcza poruszałaby się identycznie jak zwykła. Ponieważ jednak taka przerwa może (o ile wręcz nie musi – pytanie jak traktować skrajny przypadek) wystąpić ruch ten będzie nieco inny.
Gdyby teraz nasze dwie ściany miały tylko po dwie krawędzie (rozważanie teoretyczne: druga – zewnętrzna – krawędź wygięta w łuk), to ta inność byłaby jedynie pozorna. Fakt, że mrówka zeszła ze wspólnej krawędzi i weszła na zewnętrzną wcale jeszcze nie powoduje luki w ruchu mrówki zastępczej, gdyż tak naprawdę liczy się „zajęcie” (lub jak kto woli – zablokowanie) krawędzi, a nie to czy znajdujemy się na samym początku jej długości, w środku, czy na końcu. I tak – jeśli ma nie dojść do spotkania – żadna inna mrówka nie może na nią wejść aż do czasu opuszczenia jej przez tę, która weszła jako pierwsza. Właściwie to można by mrówki traktować jako „pchełki”, które nie tyle stale wędrują wzdłuż krawędzi, ale co jakiś czas (przy czym wcale nie koniecznie synchronicznie) przeskakują z jednej na drugą (czyniąc to zgodnie z kierunkiem ruchu wskazówek zegara) i oczywiście unikając się wzajemnie (tzn. unikając wskoczenia na krawędź zajętą już przez inną „pchełkę”). Dlatego też początkowo wydawało mi się, że mam odpowiedź na ten zarzut.
Problem jednak w tym, że łączone ściany mają więcej krawędzi i możliwa jest sytuacja, w której z jednej strony nasza mrówka opuszczając wspólną krawędź i wchodząc na zewnętrzną nie tylko przespaceruje po niej kawałek, ale również dojdzie do jej końca i przejdzie na kolejną (również zewnętrzną!) krawędź, a tymczasem z drugiej strony okaże się, że druga mrówka nie osiągnie jeszcze ostatniej (przed wejściem do środka) zewnętrznej krawędzi i będzie się znajdować na którejś z wcześniejszych (ale oczywiście także zewnętrznych!). Ten szczególny przypadek, gdy spełnione są JEDNOCZEŚNIE oba wymienione warunki, powoduje lukę w ruchu i swoistą teleportację mrówki zastępczej. Jeżeli byłby spełniony tylko jeden z nich (lub żaden), to wbrew pozorom wszystko jest w porządku!
Mój błąd był wynikiem tego, że wcześniej analizowałem ostrosłupy, a te mają dwie wspólne krawędzie i tylko jedną „wolną” (i tu problem ten nie występuje).
Jeśli chodzi o wypowiedź Anki, to przykro mi, że wycofałaś swoje poparcie 🙁 , ale postąpiłaś oczywiście całkowicie słusznie.
Natomiast nie mogę się zgodzić z Twoim zarzutem. Tu akurat podtrzymuję to, co napisałem wcześniej.
Po pierwsze: zawsze możemy tak łączyć ściany, że na końcu pozostanie ostatnia. Nigdzie nie napisałem, że wspólny odcinek musi składać się z pojedynczej krawędzi. Przy połączeniu dwóch ścian (a także pseudościan, czyli powierzchni będących sumą kilku z nich) z mrówkami biegającymi po obwodzie (ruchem ciągłym) nie mogą one jednocześnie wejść na część wspólną (bez względu na liczbę tworzących ją krawędzi będzie to jedna ciągła łamana), bo nie będą miały szansy przed sobą uciec. Problem polega jedynie na tym, że ruch ten ciągły jednak nie jest (co już potwierdziłem powyżej).
Po drugie: dowód był nie wprost, a więc pisząc o łączeniu ścian zakładałem, że mrówki nie mogą się spotkać. W związku z tym NIGDY nie mogą wszystkie jednocześnie zejść z obwodu. W podanym przez Ciebie przykładzie z czworościanem widać to bardzo dobrze i sama to potwierdziłaś (mam na myśli ruch w stronę wierzchołka). Natomiast sytuacja odwrotna nie wymaga rozpatrywania, gdyż nie ma ona szans się zdarzyć (oznaczałaby ona, że mrówki spotkały się wcześniej). Można oczywiście jeszcze założyć, że to pozycja startowa (i to „wcześniej” nie istnieje), ale wówczas jest to stan chwilowy i niepowtarzalny. Za moment któraś z nich (w swoim czasie zrobi to każda, bo w końcu wszystkie są w stałym ruchu) zejdzie z bocznej krawędzi jako pierwsza i nie wejdzie na nią z powrotem dopóki jakaś inna również nie pojawi się na obwodzie podstawy.
Twierdzenie, że przy połączonych wszystkich ścianach z wyjątkiem jednej zawsze jakaś mrówka będzie na zewnątrz potrafię udowodnić (i mam nadzieję, że bez błędu 🙂 ). Natomiast nie potrafię (jeszcze – ale staram się 🙂 ) dowieść – choć mimo wszystko jestem przekonany, że tak właśnie jest – iż mrówka, która tam będzie się pojawiać (lub jedna wybrana z kilku – jeśli takich będzie na raz więcej) będzie to czynić na kolejnych krawędziach zgodnie z ruchem wskazówek zegara i można ją będzie w związku z tym potraktować jak mrówkę zastępczą, czyli pojedynczą cały czas wędrującą po obwodzie. Jest to o tyle istotne, że tylko wówczas spotkanie z „właścicielką podstawy” jest pewne, gdyż sam fakt stałego pojawiania się na krawędziach zewnętrznych i nawet poruszania się po nich we właściwym kierunku (ale odcinkami) tego nie gwarantuje (możliwe jest „przeskoczenie”).
Być może w gdzieś tekście mojego dowodu wyraziłem się w sposób niejasny i to w jakiś sposób Cię zmyliło, ale nie uważam, aby miał on więcej błędów. Oczywiście i tak nie zmienia faktu, że jest on do chrzanu.
I pozwolę sobie, Panie Marku, ustosunkować się jeszcze do Pańskich uwag (poza tym co napisałem na samym początku).
Sprawę prędkości już chyba wyjaśniłem i mam nadzieję, że teraz jest jasne co miałem na myśli i nie będzie już to budziło kontrowersji.
Natomiast chyba nie do końca rozumiem, co chciał Pan powiedzieć w kwestii „spodu”. Moim zdaniem jest on (przynajmniej w niektórych sytuacjach, a podejrzewam, że zawsze) absolutnie konieczny, aby wymusić spotkanie mrówek. Widać to dobrze na najprostszym przykładzie, czyli czworościanie, gdzie mrówki wędrujące wokół bocznych krawędzi, o ile tylko „dobrze się zgadają” 😉 , mogą sobie wzajemnie nie przeszkadzać. Dopiero mrówka obchodząca podstawę gwarantuje kolizję. Nie będę tego tutaj pokazywać, ponieważ nie jest to trudne do sprawdzenia, a za to wyjątkowo kłopotliwe do opisania.
Oczywiście spód jest tylko umowny. Chodziło mi o przeciwstawienie wszystkich pozostałych mrówek, które – jak napisałem – mogą się unikać, tej ostatniej, z którą jedna z nich spotkać się musi. A jeśli miałoby to jednak nie nastąpić, będzie to jednoznacznie świadczyło o tym, że inne spotkanie nastąpiło gdzieś (w sensie toku rozumowania) wcześniej.
Ale może na razie proszę na tę moją wątpliwość nie odpowiadać, aby tym samym nie podpowiadać. 😉 Nie wiem jak inni, ale ja jeszcze nie złożyłem broni. Podejrzewam, że przynajmniej jeszcze jeden czytelnik Łamibloga – również. 😉
Z tego też zresztą powodu (tzn. potencjalnego ułatwienia) pozwoliłem sobie na razie nie czytać części Pańskiego wpisu poświęconej grze-podpowiedzi. Nie to, żebym z góry uważał ją za nieciekawą lub niepotrzebną (choć jeśli chodzi o to drugie, to – nie będę ukrywać – chciałbym aby tak było 😉 ), a wręcz przeciwnie: wierzę, że zawiera jakąś sprytną metodę i dlatego właśnie pozwoliłem sobie tak postąpić. Mam nadzieję, że to Pana nie urazi. Obiecuje, że po zwalczeniu mrówek uzupełnię zaległości. 😉
Na koniec tego chyba obrzydliwie 😉 długiego komentarza przedstawię jeszcze ogólny zarys obecnej postaci mojego dowodu (dla wielościanów z narożami trójkrawędziowymi, np. dowolnego graniastosłupa lub dwunastościanu foremnego) wraz ze wskazaniem miejsca, nad którym jeszcze „pracuję”.
Dowód ten również jest metodą nie wprost i składa się trzech głównych części:
1.
Wykazanie, że w każdym czworościanie trzy mrówki biegające po ścianach bocznych, można zawsze (o ile tylko mają się nie spotkać) sprowadzić do jednej mrówki zastępczej biegającej wokół podstawy ruchem ciągłym (!) w tym samym kierunku.
To jest właśnie ta część, która wymaga jeszcze ulepszenia (ale właściwie to wymiany) z dwóch powodów.
Po pierwsze: metoda na jakiej się ona opiera to analiza (i to nie komputerowa, a „ręczna”) wszystkich możliwych sytuacji których jest prawie 60! Poszczególne jej warianty albo pokazują, że mrówka pojawia się na krawędziach podstawy bez przerw i we właściwej kolejności (możliwe jest też, że wszystkie mrówki znajdą się wokół podstawy jednocześnie, co sprowadza się wbrew pozorom do tego samego), albo kończą się blokadą (co oznacza, że dany wariant nas nie interesuje), ewentualnie sprowadzają się do innych już przeanalizowanych wariantów (w szczególności, gdy jedna z mrówek wykonała pełne okrążenie swojej ściany, a pozostałe dwie w tym czasie nie poruszyły się).
Po drugie: W tej postaci pozwala ona na dowód tylko dla pewnej grupy wielościanów. Nie udało mi się wykonać uogólnienia tego rozumowania na ostrosłupy o większej liczbie ścian i podejrzewam, że łatwiej będzie zrobić tę część od nowa – innym sposobem, a przy okazji pozbywając się benedyktyńskiej analizy.
2.
Dowód, że każdą ścianę można w dowolny (i nam pasujący) sposób podzielić na trójkąty, aby mogły one później stać się ścianami bocznymi ostrosłupów. Ten etap jest zdecydowanie najprostszy i raczej nie wymagający wielu wyjaśnień.
3.
Pokazanie metody „ścinania” kolejnych naroży wielościanu polegającej na zamianie pokrywających się z nimi ścian bocznych ostrosłupów na jedną płaszczyznę podstawy tegoż ostrosłupa z pojedynczą mrówką zastępczą biegającą wokół niej. Następnie zredukowanie całego wielościanu do pojedynczego ostrosłupa i spostrzeżenie, że wokół jego podstawy biegają dwie mrówki (zastępcza wynikająca ze ścian bocznych i właściwa dla tej ściany) w przeciwnych kierunkach, co musi skutkować ich kolizją (końcowy motyw jest taki sam jak w poprzednim wadliwym dowodzie).
Wracając do „zamiennika” do pierwszej części, to mam już jakąś koncepcję jak do tego podejść, ale jednocześnie spory problem jak to formalnie zapisać.
Jeżeli uda mi się to pozbierać do „ludzkiej” postaci to wtedy to przedstawię, a na razie wracam do mrowiska. 😉
Pozdrawiam
AB
Mi się udaje pokonać tylko jeden etap. Wciąż pionki f,g oraz d ustawiają się na trzech krawędziach o wspólnym wierzchołku (f przesuwam o 1 pole, g o3 pola i d o 3 pola). Inne pionki można przesunąć na więcej sposobów. Drugiego etapu nie mogę pokonać, bo f, d,g nie mogę ruszyć.
Nie wiem, czy ma to znaczenie, dla osiągnięcia lepszego wyniku, ale przed zmierzeniem się z tą grą chciałbym rozstrzygnąć pewną kwestię. Otóż, czy jest możliwe aby w jednym ruchu pionek powrócił na zajmowane w danej chwili miejsce? Dla przykładu: czy na pierwotnej planszy pionek g może wykonać ruch o 4 pola? Uogólniając, czy liczbę wolnych pól ustalamy przed wykonaniem ruchu, czy też w czasie jego wykonywania?
Pozdrawiam,
Jaz_off
Jaz_on:
Jeśli wszystkie pola na obwodzie ściany – poza jednym, zajętym przez pionek – są wolne, to można powrócić pionkiem na pole wyjściowe. Ruch zostaje więc wykonany, choć efekt końcowy jest taki, jakby pionek pozostawał w bezruchu.
mp
Trzeba przyznać, że mrówki czasem naprawdę ciężko wytępić. Gdy już się zalęgną, to za nic w świecie nie zamierzają opuścić zajmowanego miejsca. Nie inaczej jest z odmianą łamigłówkową. Czasem mogą dużo zdrowia kosztować zanim uda się je zwalczyć. 😉
Na zakończenie mojego poprzedniego komentarza w tym wątku przedstawiłem pewną ogólną koncepcję dowodu, która wówczas wymagała jeszcze dopracowania i uogólnienia, ponieważ dotyczyła pewnego szczególnego przypadku. Muszę jednak przyznać, że była ona jednak niestety (co wyszło po wielu nieudanych próbach jej uzasadnienia, gdy udało się znaleźć kontrprzykład) może nie tyle błędna, co po prostu nietrafiona.
To co dawało się dowieść dla czworościanów, okazało się nie być zawsze prawdziwe dla bardziej skomplikowanych ostrosłupów. W tym bardziej złożonym przypadku wyszło na to, że mrówki biegające po ścianach bocznych, mimo wzajemnego unikania się, wcale nie muszą dać się sprowadzić do jednej mrówki zastępczej biegającej wokół podstawy. Oczywiście zawsze przynajmniej jedna z nich tam się znajduje i gdy jest tam tylko jedna mrówka, to nim ona stamtąd zejdzie, musi pojawić się inna mrówka na następnej krawędzi podstawy. Jeżeli jednak tych mrówek na podstawie będzie więcej jednocześnie, może się okazać, że kolejność zajmowania krawędzi podstawy będzie inna niż ta pożądana.
Zmusiło mnie to do poszukania innych możliwości uzasadnienia. Sposób w jaki w końcu udało mi się to zrobić i jaki dalej przedstawię jest dokładnie odwrotny niż to, o czym pisałem dotychczas. Zarówno bowiem wspomniana wyżej koncepcja jak i pierwszy błędny dowód opierał się na metodzie od szczegółu do ogółu, tzn. próbowałem wychodząc od prostych elementów uogólniać je na coraz większe fragmenty, aby na końcu dojść do całego wielościanu.
Nowa metoda jest przeciwieństwem starej: A więc punktem wyjścia będzie cała bryła, a następnie krok po kroku analizowany obszar będzie się zmniejszał aż do pojedynczego wierzchołka. Może to trochę przypominać poszukiwanie (metodą zawężania) miejsca, gdzie mrówki muszą się spotkać i nawiasem mówiąc jeżeli zastosujemy ją do konkretnego układu mrówek, to można jej również w takim celu użyć.
Przedstawiony poniżej dowód może na pierwszy rzut oka wydawać się dość zawiły. W rzeczywistości jednak tak nie jest. Owo wrażenie ma dwie przyczyny.
Po pierwsze: brak możliwości przedstawienia w komentarzu rysunków, które w prosty sposób pokazywałyby pewne zależności. Siłą rzeczy musiałem polegać na opisach, a te, ze swej natury, zawsze wyglądają na bardziej skomplikowane. Dlatego też bardziej dociekliwym proponowałbym wykonywanie szkiców. Niektóre sytuacje stają się dzięki temu natychmiast zrozumiałe.
Po drugie: Starałem się przedstawić ten dowód w sposób możliwie dokładny, tak aby, jak to się mówi, nie można się było przyczepić 😉 (taaak… naiwny, myślałby sobie… 🙂 ). Dlatego też robiłem wiele szczegółowych założeń, formalnie niezbędnych, które mogą jednak, szczególnie na początku, zaciemniać nieco obraz całości.
Generalnie planowałem też unikać skrótów myślowych, ale pewne oczywiście się zdarzają. Starałem się jednak, aby miały one miejsce w sytuacjach mniej istotnych lub nie budzących wątpliwości.
Po tym nieco przydługim wstępie należałoby wreszcie przejść do właściwego dowodu.
Mam nadzieję, że tym razem obejdzie się bez potknięć. Niemniej szacowną komisję milenijną 😉 proszę o weryfikację (mając jednocześnie nadzieję, że nie zajmę jej tym całych dwóch lat 😉 ).
…………………..
Na początku chciałbym zdefiniować dwa terminy, abym później nie musiał za każdym razem powtarzać pewnych kwestii:
1. „Dowolne rozmieszczenie mrówek” – będzie to oznaczać dowolne ich rozmieszczenie na rozpatrywanych krawędziach z zastrzeżeniem, że żadne dwie nie znajdą się na tej samej krawędzi.
2. „Zwarty zbiór wierzchołków” (termin użyty trochę nieoficjalnie, ale potrzebowałem jakoś to nazwać) – taki ich zbiór, że każde dwa wierzchołki należące do tego zbioru można połączyć łańcuchem krawędzi, których oba końce również do tego zbioru należą. Innymi słowy: gdybyśmy usunęli wszystkie pozostałe (nie należące do tego zbioru) wierzchołki (i krawędzie których one są końcami), to i tak wszystkie rozważane wierzchołki będą ze sobą połączone (nie rozlecą się na dwie lub więcej oddzielnych grup). Przy tej okazji, wraz z tymi wierzchołkami będziemy rozpatrywać wyłącznie te krawędzie, których oba końce do tego zbioru należą. Podobnie ze ścianami (i przynależnymi im mrówkami): wyłącznie te, których wszystkie wierzchołki należą do wspomnianego zbioru. Pozostałe wierzchołki, krawędzie i ściany w tym momencie nas nie będą interesować.
…………………..
Osią całego dowodu będzie następujące twierdzenie pomocnicze:
Rozpatrzmy dowolny, przynajmniej dwuelementowy zwarty zbiór wierzchołków, a wraz z nim odpowiednie krawędzie, ściany i mrówki. Jeżeli teraz do dowolnie rozmieszczonych rozważanych mrówek dodamy gdziekolwiek JESZCZE JEDNĄ mrówkę, to w zbiorze tym będzie można wyodrębnić taki zwarty niepusty podzbiór, że na WSZYSTKICH krawędziach łączących elementy tego podzbioru z pozostałymi wierzchołkami pierwotnego zbioru będą znajdować się mrówki zmierzające w kierunku tegoż podzbioru. Czyli mówiąc krótko: z wszystkich stron będą się schodzić mrówki i nie będzie żadnej krawędzi wolnej (albo zajętej, ale przez mrówkę idącą „na zewnątrz”).
Dowód opiera się na wzorze Eulera:
S+W=K+2, gdzie S – liczba ścian wielościanu wypukłego, W – liczba wierzchołków, K – liczba krawędzi.
Prawdziwość tego twierdzenia wykazana jest np. tu: http://pl.wikipedia.org/wiki/Twierdzenie_Eulera_o_wielo%C5%9Bcianach .
Adres ten podaję, ponieważ zamierzam je trochę zmodyfikować, a nie chciałbym powtarzać całego rozumowania, które przebiega dokładnie w ten sam sposób. Dociekliwi będą mogli dzięki temu sprawdzić, że proponowane dalej zmiany nie wpływają na prawdziwość tego wzoru.
Jeżeli nasz zbiór wierzchołków składałby się z wszystkich wierzchołków wielościanu, to, ponieważ jest on płaski, będzie równoważny wielościanowi z usuniętą ostatnią ścianą. W takiej sytuacji (biorąc pod uwagę, że wszystkie jej krawędzie i wierzchołki są wspólne z innymi ścianami, a więc pozostają) wzór przyjmie postać S+W=K+1.
Jeżeli teraz z tego zbioru usuniemy dalsze ściany, to postać wzoru pozostanie już bez zmian. Zauważmy też, że jeśli dodamy „luźną” krawędź nie należącą do żadnej ściany, to liczba ścian nie zmieni się, a liczba wierzchołków i krawędzi wzrośnie o 1, czyli wzór dalej ma postać: S+W=K+1. A zatem jest on prawdziwy dla dowolnego zwartego zbioru wierzchołków (w tym również takiego, który nie tworzy żadnej ściany).
Oznaczmy teraz przez Kbm liczbę krawędzi bez mrówek. Normalnie krawędzi z mrówkami jest tyle co ścian, a więc Kbm=K-S. Wzór możemy więc sprowadzić do następującej postaci: Kbm=W-1. Ponieważ jednak w naszym twierdzeniu pomocniczym do mrówek wynikających z rozpatrywanych ścian dodajemy jeszcze jedną (czyli liczba pustych krawędzi zmniejsza się o 1), to wzór wygląda tak: Kbm=W-2.
Weźmy teraz dowolny wierzchołek z naszego zbioru. Łączy się on (bezpośrednio lub pośrednio, na jeden lub więcej sposobów) ze wszystkimi pozostałymi W-1 wierzchołkami (w przeciwnym przypadku zbiór nie byłby zwarty). Ponieważ krawędzi „bezmrówkowych” jest W-2, oznacza to, że w zbiorze istnieje przynajmniej jeden taki wierzchołek, że wszystkie możliwe drogi pomiędzy nim a pierwszym wierzchołkiem, są na jakimś odcinku zajęte przez mrówki. Można więc powiedzieć, że oba wierzchołki należą do dwóch rozłącznych niepustych podzbiorów takich, że aby przejść z jednego do drugiego musimy choć raz znaleźć się na krawędzi z mrówką.
Ustalmy teraz granice pierwszego z podzbiorów. Czyli wyszukajmy te wierzchołki, do których można dojść (z pierwszego wierzchołka) wyłącznie po krawędziach wolnych od mrówek. Wszystkie krawędzie łączące te wierzchołki z pozostałymi (nie należącymi do tego podzbioru) są zajęte przez mrówki. Weźmy dowolną z tych krawędzi i sprawdźmy, w którym kierunku porusza się po niej mrówka. Załóżmy wstępnie, że będzie to w stronę naszego podzbioru. Weźmy teraz inną z tych krawędzi, ale należącą do tej samej ściany, co pierwsza. Gdyby mrówka z pierwszej krawędzi do niej dotarła, to niejako zawróciłaby i poruszała się teraz w na zewnątrz naszego podzbioru, ale ponieważ znajduje się tam inna mrówka (a dwie mrówki na wspólnej krawędzi idą zawsze w przeciwne strony), oznacza to, że musi się ona również przemieszczać w stronę naszego podzbioru. Prowadząc dalej to rozumowanie dochodzimy do tego, że wszystkie mrówki maszerujące po krawędziach łączących oba podzbiory idą w kierunku naszego. A co by było, gdyby pierwsza mrówka szła nie „do nas”, ale „od nas”? Wówczas w analogiczny sposób wykażemy, że i pozostałe mrówki zmierzają „na zewnątrz”, a więc w stronę tego drugiego podzbioru.
Tak czy inaczej istnieje więc podzbiór wierzchołków, taki że na wszystkich krawędziach łączących elementy tego podzbioru z pozostałymi wierzchołkami zbioru pierwotnego znajdować się będą mrówki poruszające się w kierunku tegoż podzbioru.
Twierdzenie pomocnicze zostało zatem udowodnione.
…………………..
W tym momencie możemy przystąpić do właściwej części dowodu:
Na pierwszy ogień bierzemy wszystkie wierzchołki wielościanu. Dodatkową mrówkę (aby spełnić założenie, że mrówek jest o jedną więcej niż wynika to z liczby ścian) stanowi ta, która wędruje wokół spodniej, usuniętej ściany. Na podstawie udowodnionego chwilę wcześniej twierdzenia pomocniczego możemy więc wyodrębnić przynajmniej jednoelementowy podzbiór, w kierunku którego z wszystkich stron będą się schodzić mrówki.
Załóżmy teraz, że ów podzbiór ma więcej niż jeden element.
Na wszystkich krawędziach łączących ten podzbiór z pozostałymi wierzchołkami znajdują się mrówki zmierzające w jego kierunku. Taki stan nie może oczywiście trwać wiecznie i w pewnym momencie pierwsza z nich zejdzie z zajmowanej wcześniej krawędzi i znajdzie się na takiej, która łączy dwa wierzchołki tego podzbioru (zauważmy, że nie może być to inna krawędź łącząca ze „światem zewnętrznym”, gdyż na razie wszystkie pozostałe są jeszcze zajęte przez inne mrówki). To daje nam potrzebną dodatkową mrówkę i pozwala po raz drugi zastosować twierdzenie pomocnicze. Wyodrębniony wcześniej podzbiór staje się zbiorem pierwotnym, a wewnątrz jego możemy wskazać kolejny mniejszy podzbiór.
Tutaj należałoby jeszcze wyjaśnić jedną sprawę:
Otóż mrówka, która stała się mrówką dodatkową wcześniej „blokowała” przynależną jej krawędź „zewnętrzną”, ale w tej chwili siłą rzeczy tego już nie robi. Skąd wiadomo, że nie tworzy to luki? Mogłoby się przecież okazać, że świeżo wyodrębniony podzbiór nie jest jednak ze wszystkich stron otoczony przez mrówki zmierzające w jego kierunku, bo właśnie ta jedna krawędź tego warunku nie spełnia.
Aby pokazać, że taki stan nie może mieć miejsca, rozważmy dwa przypadki:
1. Tuż przed wejściem dodatkowej mrówki, mimo że jej jeszcze nie było, istniał już podział na dwa podzbiory. W tej sytuacji nie ma oczywiście problemu, po prostu nie rozważamy w ogóle efektów przejścia tej mrówki, bo nasz cel został osiągnięty bez tego już wcześniej.
2. Przed wejściem dodatkowej mrówki nie było podziału na podzbiory. Oznacza to, że jej udział był tym procesie podziału niezbędny, czyli że właśnie ta krawędź, którą ona zajęła, była tą łączącą elementy dwóch podzbiorów i dopiero teraz nastąpiła pełna ich separacja. Ponieważ jednak wszystkie mrówki rozdzielające podzbiory maszerują w tę samą stronę, a więc w tę samą, co rozpatrywana mrówka, a ta z kolei porusza się w kierunku „od” pozostawionej pustej krawędzi i będącego jej końcem wierzchołka, świadczy to o tym, że wierzchołek ten należy do tego podzbioru, od którego mrówki właśnie „odchodzą” i to ten podzbiór może być nie do końca „domknięty”. Tym samym interesujący nas podzbiór, czyli ten w kierunku którego zmierzają mrówki jest jednak, tak jak powinien, z wszystkich stron otoczony.
Zatem tej potencjalnie niebezpiecznej sytuacji obawiać się nie trzeba.
Po tym podziale na dwa podzbiory sprawdzamy liczbę wierzchołków. Jeżeli dalej mamy więcej niż jeden, identyczne rozumowanie przeprowadzamy jeszcze raz i tak dalej, aż w wyniku kolejnego podziału okaże się, że podzbiór będzie jednoelementowy. Oznacza to, że doprowadziliśmy w ten sposób do sytuacji, w której mamy jeden wierzchołek, taki że po wszystkich krawędziach doń prowadzących, w jego kierunku, maszerują mrówki. A taka sytuacja musi oczywiście oznaczać spotkanie mrówek.
Uważam zatem, iż teza została udowodniona.
Mam nadzieję, że tym razem poprawnie.
Pozdrawiam
AB
Panie Andrzeju. Przejżałem dowód, nie wszystko jest dla mnie w nim jasne. Po ogólnym przeglądzie mam uwagę co do jednego akapitu:
„Jeżeli nasz zbiór wierzchołków składałby się z wszystkich wierzchołków wielościanu, to, ponieważ jest on płaski, będzie równoważny wielościanowi z usuniętą ostatnią ścianą. W takiej sytuacji (biorąc pod uwagę, że wszystkie jej krawędzie i wierzchołki są wspólne z innymi ścianami, a więc pozostają) wzór przyjmie postać S+W=K+1.”
To co napisano w dowodzie w Wikipedii dotyczy wielościanu wyobrażonego na płaszczyźnie, ale jako jego siatkę. Siatka wielościanu a wielościan „rozpłaszczony po usunięciu jednej ściany” to dwie różne rzeczy.
Nie jestem w stanie stwierdzić jakie znaczenie i konsekwencje ma to dla dowodu, bo go dokładnie nie przeanalizowałem (i nie wiem czy mi się to uda).
Ja zrobiłem sobie dłuższą przerwę od mrówek, choć czasem wracam do nich myślami. Liczę, że Pan Marek jednak wkrótce zamieści rozwiązanie, bo, jak pamiętam, wspominał, że dowód można przeprowadzić nie odwołując się do wzorów.
Doszedłem do wniosku, że moja uwaga z poprzedniego wpisu nie ma znaczenia.
Obawiam się, że nie dam rady się przekonać bez rysunków. Dowodu oczywiście nie podważam, ale pewnie miałbym zbyt wiele pytań i wątpliwości (np. czym jest dodana „luźna” krawędź? „Zwarty zbiór wierzchołków” wyobrażam sobie jako coś podobnego do planszy „gry w mrówki” – czy na pewno słusznie?) byśmy mogli szybko zakończyć sprawę mrówek. Co do „twierdzenia pomocniczego” to intuicyjnie się zgadzam (przedostatni akapit o nim wymagałby rysunku). Jednak kiedy czytam koniec dowodu, to mam wątpliwości czy dobrze je zrozumiałem, bo ostatnie akapity są dla mnie niejasne.
Chciałbym zobaczyć to na rysunkach, albo, jeśli byłby Pan skłonny, Panie Andrzeju, podać swój dowód w formie serii krótkich pytań, tak, żeby od coraz prostszych, ułożonych w odpowiedniej kolejności, czytelnik mógł sam dojść do dowodu odpowiadając sobie na te pytania jedno po drugim i wyciągając wnioski.
Andrzeju69, przyłączam się do opinii Michała Gajzlera, czyli kilka fragmentów dowodu jest niejasnych lub przynajmniej wątpliwych. Szczerze mówiąc, znajomi matematycy formułują tę opinię bardziej radykalnie.
Jeśli znajdę wolną chwilę napiszę bardziej szczegółowo, a poza tym niedługo przedstawię dowód „oficjalny”.
Pozdrawiam
mp
Przeczytałem z uwagą uwagi 😉 do przedstawionego przeze mnie dowodu.
Na wszelki wypadek przeanalizowałem jeszcze raz cały tok myślenia i (przynajmniej jak na razie), mimo „delikatnej sugestii” 😉 Pana Marka, błędu ani luki w ROZUMOWANIU nie widzę, natomiast oczywiście mogę się zgodzić, że są pewne niejasności w OPISIE, niektóre sprawy mogą budzić wątpliwości, wydawać się niezrozumiałe itp.
Najważniejsze przyczyny takiego stanu rzeczy to brak rysunków (samymi słowami często trudno pokazać sytuację) oraz chęć utrzymania (wbrew pozorom) jak najkrótszej formy (nie chciałem przy okazji napisać książki 😉 ), między innymi dlatego, żeby na „dzień dobry” nie zniechęcać czytających.
Poza tym nie wiem co matematycy mają do zarzucenia, ale podejrzewam że braki formalne, nieszczęsne sformułowania (których wiem, że tutaj nie brakuje, ale nie potrafię pewnych spraw nazwać inaczej) oraz nieścisłości w samym opisie.
Wzięło się to stąd, że jeśli chodzi o matematykę, to bazuję wyłącznie na wiedzy ze szkoły średniej, a na tym etapie jedyną dziedziną, która byla dokładnie przedstawiona od strony formalnej to była geometria, której tu, wbrew pozorom, wcale nie ma. Podejrzewam, że za to bardzo przydałaby się teoria grafów, o której – od razu mówię – nie mam pojęcia. Dlatego też prosiłbym o wyrozumiałość przy pewnych brakach formalnych, które nie są istotne dla IDEI dowodu. W końcu mętne 😉 sformułowania nie muszą oznaczać złego toku myślenia.
Oczywiście mogę się mylić, ale jak na razie, w tym przypadku, jestem przekonany co do prawidłowości dowodu. W związku z tym, dopóki nie uda się znaleźć (tzn. sam nie znajdę lub ktoś nie wskaże) konkretnego błędu, będę go bronić. Jak jest w rzeczywistości, mam nadzieję że się wyjaśni, gdy uzupełnię moje objaśnienia, co jak najbardziej zamierzam uczynić.
Z tego co Pan, Panie Marku, napisał wnioskuję że Pański dowód jest całkiem inny (podejrzewam, że prostszy), ale z dowodami tak to już jest, że zazwyczaj można je przeprowadzić na wiele sposobów i odmienny sposób rozumowania nie oznacza, że jest on zły. I w sumie dobrze, bo różnorodność zawsze jest wskazana, by nie zasklepiać się i nie myśleć w „jedynym słusznym” kierunku.
Na Pański dowód będę czekać z niecierpliwością i jestem bardzo ciekawy jak można to zrobić w inny sposób.
Osobiście nie planuję już poszukiwania kolejnej metody, natomiast chętnie będę wyjaśniać nieścisłości opisu. Zaraz też przystępuję do uszczegóławiania tego, co pokazałem wcześniej. Postaram się również przedstawić rysunki – mam nadzieję, że one rozwieją wiele wątpliwości.
W miarę tego co napiszę proszę zainteresowanych o nadsyłanie ewentualnych pytań. W końcu to, co jest proste i oczywiste dla autora (który zna cały tok rozumowania) nie musi być takie same dla czytelnika (który na tej podstawie próbuje dojść do tego, co autor miał na myśli 😉 ).
Pozdrawiam
AB
Zgodnie z zapowiedzią pozwolę sobie przedstawić pierwszą część wyjaśnień do mojego dowodu mrówczego zadania. Mam nadzieję, że rozwieje ona przynajmniej trochę wątpliwości, w szczególności że zawiera obrazki (a dokładniej linki do nich). Część ta obejmuje definicję zwartego zbioru oraz dowód twierdzenia pomocniczego czyli tzw. lematu. Część druga wkrótce.
……………………………
1. Co rozumiem pod pojęciem „zwarty zbiór wierzchołków”?
Na wszelki wypadek jeszcze raz przypomnę, że określenie „zwarty” występuje tu nieoficjalnie. W rzeczywistości termin ten odnosi się do spraw zupełnie innych, których nawet nie próbuję zrozumieć 😉 . Potrzebne mi jednak było, dla wygody opisu, nazwanie pewnej sytuacji. Być może istnieje na to adekwatne określenie, ale niestety nie jest mi ono znane.
W moim dowodzie takim zbiorem może być np.:
a) dowolny pojedynczy wierzchołek,
b) dwa sąsiednie wierzchołki (tzn. będące końcami tej samej krawędzi),
c) więcej wierzchołków (nawet wszystkie) – mogą one tworzyć ścianę, lub kilka ścian, ale mogą też nie tworzyć żadnej. Możliwa jest też sytuacja gdy mamy np. pełną ścianę oraz jeszcze jeden wierzchołek (lub więcej), taki że jedna z krawędzi, której jest końcem łączy się ze wspomnianą ścianą (taką krawędź określiłem później mianem „luźnej krawędzi”).
Ważne, żeby z dowolnego z tych wierzchołków dało się przejść (krawędziami) do każdego innego należącego do tego zbioru po drodze „zaliczając” wyłącznie wierzchołki z naszego zbioru. Przykładowy taki zbiór można zobaczyć tu: http://aps-projekt.pl/mrowki/mrowki01.gif . Wierzchołki należące do tego zbioru zaznaczono na zielono.
Natomiast NIE będzie zwartym zbiorem taki, którego elementy są „rozproszone” jak np. ten: http://aps-projekt.pl/mrowki/mrowki02.gif . Zielone wierzchołki tworzą tutaj jakby dwa zwarte zbiory, ale jeżeli potraktujemy to jako jeden zbiór, wówczas nie będzie on zwarty. Aby takim się stał, najprościej byłoby włączyć doń jeszcze wierzchołek zaznaczony na czerwono.
……………………………
2. Rozszerzenie pojęcia zbioru zwartego o krawędzie, ściany i mrówki.
Definicję podaną w poprzednim punkcie należałoby jeszcze uzupełnić o jedną bardzo ważną rzecz:
Razem z wierzchołkami (elementami zbioru) będę ZAWSZE rozpatrywać również WSZYSTKIE krawędzie, których OBA końce należą do zbioru oraz, na podobnej zasadzie, WSZYSTKIE ściany, których WSZYSTKIE wierzchołki należą do zbioru, a wraz z nimi WSZYSTKIE przynależne tym ścianom mrówki i, o ile nie zaznaczę inaczej, TYLKO TE krawędzie, ściany i mrówki.
Jak to wygląda w praktyce, przedstawiłem tu: http://aps-projekt.pl/mrowki/mrowki03.gif , gdzie oprócz wierzchołków, zaznaczyłem również powiązane z nimi krawędzie (na zielono), ściany (na żółto) oraz okrążające te ściany mrówki (zielony łuk pokazujący kierunek marszu).
Przyznaję, z nazwaniem tej sytuacji miałem nielichy zgryz.
Nie chciałem napisać, że owe obiekty wchodzą w skład zbioru (składałby się on wtedy z elementów różnego typu), bo wówczas podczas dzielenia go na dwie części (wyodrębniania podzbioru) ktoś mógłby chcieć np. zaliczyć wierzchołek tu, a krawędź gdzie indziej itp. Poza tym, w rezultacie tego podziału, WSZYSTKIE wierzchołki znajdą się albo w jednym, albo drugim podzbiorze, natomiast część krawędzi (te, przez które przechodzi granica na dwa podzbiory) nie będzie przynależna ani tu, ani tu. Tak samo będzie z niektórymi ścianami oraz mrówkami.
Sytuację tę pokazałem tu: http://aps-projekt.pl/mrowki/mrowki04.gif , gdzie zbiór wszystkich wierzchołków (powiązany ze wszystkimi krawędziami i wszystkimi ścianami) został podzielony na dwa podzbiory: „zielono-żółty” i „czerwono-pomarańczowy”. Jednak jak widać, w wyniku tego podziału siedem krawędzi i sześć ścian (z sześcioma mrówkami) przestało być związane z którymkolwiek z podzbiorów.
Muszę powiedzieć, że nie wiem jak to zgrabnie ująć. Może niech matematycy się wypowiedzą?
……………………………
3. Teza lematu.
Tu nie było jak na razie zgłaszanych wątpliwości, ale ponieważ jest to według mnie najważniejsze miejsce całości wywodu napiszę parę słów.
Dla przypomnienia brzmi on tak:
Rozpatrzmy dowolny, przynajmniej dwuelementowy zwarty zbiór wierzchołków, a wraz z nim odpowiednie krawędzie, ściany i mrówki. Jeżeli teraz do dowolnie rozmieszczonych rozważanych mrówek dodamy gdziekolwiek JESZCZE JEDNĄ mrówkę, to w zbiorze tym będzie można wyodrębnić taki zwarty niepusty podzbiór, że na WSZYSTKICH krawędziach łączących elementy tego podzbioru z pozostałymi wierzchołkami pierwotnego zbioru będą znajdować się mrówki zmierzające w kierunku tegoż podzbioru. Czyli mówiąc krótko: z wszystkich stron będą się schodzić mrówki i nie będzie żadnej krawędzi wolnej (albo zajętej, ale przez mrówkę idącą „na zewnątrz”).
Ilustrację tej sytuacji mamy tu: http://aps-projekt.pl/mrowki/mrowki05.gif . Podobnie jak poprzednio wyodrębniony podzbiór jest zielono-żółty. Tym, co go separuje od reszty jest tyraliera mrówek zaznaczonych na czerwono (brrr… czerwone mrówki atakują 😉 ). Mrówki te są celowo narysowane obok krawędzi, gdyż w ten sposób zamierzam pokazywać, do której ściany należą. Mrówek tych jak widać jest o jedną więcej niż ścian, co pokrywa się z założeniem. Ta dodatkowa, nie przynależna do żadnej ze ścian (więcej na jej temat będzie trochę dalej), została w związku z tym umieszczona na zewnątrz (pierwsza z lewej). Zgodnie z brzmieniem tezy wszystkie krawędzie łączące nasz podzbiór z resztą wierzchołków są zajęte przez mrówki maszerujące w jego stronę. W ten sposób utworzyła się swoista granica. Dokładne położenie pozostałych mrówek jest, z punktu widzenia samej tezy, nieistotne.
……………………………
4. Mój wywód, a wzór Eulera.
Wzór ten, lekko zmodyfikowany na potrzeby tego dowodu (brak ostatniej ściany), wygląda tak:
S+W=K+1, gdzie S, W, K – liczby ścian, wierzchołków i krawędzi.
Właściwie to powinienem był przedstawić „od zera” metodę dojścia do tej zależności i tak początkowo planowałem zrobić (wówczas jakakolwiek wzmianka o tw. Eulera byłaby zbędna), ale później stwierdziłem, że trochę sobie ułatwię sprawę.
Sytuacje występujące w tym dowodzie różnią się od tego co opisuje wzór Eulera m.in. tym:
a) wzór Eulera dotyczy wielościanów, tutaj sytuacja rozgrywa się na płaszczyźnie,
b) konsekwencją tego (najistotniejszą) jest brak ostatniej ściany (co powoduje, że po prawej stronie jest „K+1”, a nie „K+2”),
c) możliwe są również pojedyncze wierzchołki, krawędzie i łańcuchy krawędzi/wierzchołków nie tworzące ścian itp., które w bryłach nie mają miejsca.
Jak widać trochę tych różnic jest i zastosowanie tego twierdzenia wprost nie ma racji bytu. Generalnie chodziło mi jednak nie tyle o samo tw. Eulera, ile o sposób w jaki jest ono dowodzone, ponieważ uzasadnienie przedstawionego powyżej wzoru przebiega dokładnie w taki sam sposób.
Dlatego zalecałbym przeanalizowanie wywodu z Wikipiedii (tu od razu odpowiadam na zadane pytanie: tam nigdzie nie ma mowy o siatce!) i samodzielną próbę sprawdzenia wszystkich pojawiających się tu nowych możliwości jak np.:
Jeżeli w interesującym nas zbiorze nie ma żadnej ściany, to zaczynamy od pojedynczego wierzchołka, czyli S=0, W=1, K=0, ale postać wzoru jest taka sama.
Gdybyśmy dodawali luźną krawędź (tzn. nie należącą do żadnej ściany), to liczba ścian nie zmienia się, a liczba wierzchołków i krawędzi rośnie o 1. Czyli wzór dalej ma postać: S+W=K+1.
Pomocny w liczeniu może być ten rysunek: http://aps-projekt.pl/mrowki/mrowki03.gif . Tutaj mamy: S=2, W=15, K=16 dla części zaznaczonej oraz S=25, W=30, K=54 dla całości.
Dodatkowo proponowałbym kliknięcie na umieszczony na samym dole strony Wikipedii link „Twierdzenie Eulera i jego zastosowanie”. Dla leniwych przytaczam go tu: http://www.jakubas.pl/konspekty/Tw-Eulera/Tw-Eulera.htm . Tam (w zadaniu 1) jest omówiona prawie identyczna sytuacja. Jedyna różnica polega na tym, że rozważania zaczęto od trzech wierzchołków, a tu powinniśmy od jednego.
……………………………
5. Zależność między liczbą wierzchołków a krawędzi „bezmrówkowych”.
Ponieważ krawędzi zajętych przez mrówki jest tyle co ścian, więc wolnych będzie K-S. A zatem:
Dla dowolnego zwartego zbioru wierzchołków zależność między liczbą tych wierzchołków, a liczbą krawędzi wolnych w danym momencie od mrówek wygląda tak:
Kbm=W-1,
gdzie:
W – liczba wierzchołków (elementów zbioru),
Kbm – liczba krawędzi bez mrówek łączących wyłącznie te wierzchołki.
UWAGA: jak zawsze biorę pod uwagę wyłącznie mrówki biorące się ze ścian, których WSZYSTKIE wierzchołki należą do zbioru.
Można to dodatkowo zobaczyć tu: http://aps-projekt.pl/mrowki/mrowki06.gif . Dla całego zbioru należy wziąć pod uwagę wszystkie wyróżnione (czerwone, zielone i jedną grubą czarną), a dla każdego z podzbiorów (rozdzielonych linią przerywaną) wyłącznie zielone lub czerwone.
……………………………
6. Dodatkowa mrówka.
W lemacie jest mowa o dodatkowej (ponad te wynikające ze ścian przynależnych do danego zbioru) mrówce.
Skąd się ona bierze?
Generalnie, to z takiej ściany, której nie wszystkie wierzchołki do naszego rozpatrywanego zbioru należą. Podczas UŻYCIA lematu, będzie to dokładnie wyjaśnione, jednak na potrzeby jego DOWODU jest całkowicie nieistotne. Ważne, że nie pochodzi z żadnej ze ścian, której WSZYSTKIE wierzchołki należą do zbioru.
Ponieważ mamy o jedną mrówkę więcej, zależność z punktu poprzedniego przyjmuje postać: Kbm=W-2.
……………………………
7. Skąd wiadomo, że istnieje granica?
W naszym zbiorze mamy W wierzchołków. Zgodnie z przyjętą tu definicją zbioru zwartego, każdy z nich musi mieć połączenie z każdym z pozostałych W-1 wierzchołków. Na to potrzeba przynajmniej W-1 krawędzi i nie ma znaczenia, czy będzie to w formie gwiazdy (jeden w środku ma bezpośrednie połączenie z każdym), szeregowe (pierwszy łączy się z drugim, ten z trzecim itd.), czy mieszane, w kształcie rozgałęzionego drzewa (jak na rysunkach dalej).
Uznajmy teraz na moment, że interesują nas wyłącznie takie połączenia, które przebiegają krawędziami wolnymi od mrówek (krawędzie zajęte potraktujemy jako nie do przejścia).
Rozważmy na razie sytuację bez dodatkowej mrówki (czyli Kbm=W-1). W tym przypadku jest możliwe, by między dowolnymi wierzchołkami można było przejść wyłącznie po krawędziach nie zajętych przez mrówki. Tę sytuację można zobaczyć tu: http://aps-projekt.pl/mrowki/mrowki07.gif .
Ponieważ wolnych krawędzi mamy dokładnie tyle, ile wynosi minimum, oznacza to, że między dowolnymi dwoma wierzchołkami można przejść wyłącznie na jeden sposób. Jeśli istniałyby dwa wierzchołki, między którymi byłyby dwie różne drogi, to zabrakłoby krawędzi na podpięcie ostatniego. W takim układzie już na tym etapie mielibyśmy rozdzielone wierzchołki. Wtedy jest jeszcze prościej – nie musimy nawet uwzględniać dodatkowej mrówki i możemy pominąć następny akapit.
A co się dzieje jeśli przejście jednak istnieje?
Ponieważ, jak już napisałem, nie mamy zbędnej krawędzi, więc jeśli gdziekolwiek wprowadzimy dodatkową mrówkę jak tu: http://aps-projekt.pl/mrowki/mrowki08.gif (w kolorze zielonym) spowoduje to przerwanie łańcucha połączeń i rozdzielenie wierzchołków na dwie grupy.
Właściwie to co napisałem w tym punkcie po stwierdzeniu (w pierwszym akapicie), że „potrzeba przynajmniej W-1 krawędzi” dla samego dowodu nie jest potrzebne. Wystarczyłoby dodanie, że dysponujemy tylko Kbm=W-2 wolnymi krawędziami, a więc mamy o jedną za mało. Uznałem jednak, że takie przedstawienie sprawy pozwoli trochę lepiej zorientować się w sytuacji, a poza tym przyda się później, już podczas korzystania z lematu.
Wracając do właściwego toku rozumowania (teraz uwzględniamy już wszystkie krawędzie):
Wniosek jest taki, że jeśli wprowadzimy dodatkową mrówkę, to będą istnieć takie dwa wierzchołki, że bez względu na to, ile jest możliwych dróg między nimi, aby przedostać się z jednego do drugiego będziemy musieli, przynajmniej jeden odcinek, przejść krawędziami zajętymi przez mrówki. Mrówki te (na razie o nieokreślonym kierunku ruchu) będą tworzyć swoistą granicę biegnącą w poprzek zajętych przez nie krawędzi i rozdzielającą nasz zbiór na dwa podzbiory.
…………………………..
8. Przebieg granicy.
To miejsce chyba budziło najwięcej wątpliwości, a to pewnie dlatego, że tak naprawdę nic tu się nie dzieje.
W poprzednim punkcie podzieliliśmy zwarty zbiór wierzchołków na dwa podzbiory. Podzbiory te również będą zwarte. Gdyby z jakichś powodów miało być inaczej, to po prostu traktujemy, jakby było kilka mniejszych podzbiorów i rozpatrujemy każdy z nich z osobna. Dla dowodu nie ma to znaczenia (a nawet jest lepiej, bo będą wtedy mniejsze). Dalej jednak przyjmiemy, że owe podzbiory są dwa.
Na tym etapie musimy ustalić jedynie ich wielkość i wyszukać wszystkie wierzchołki będące końcami krawędzi, z których składa się granica – będą one stanowiły dane początkowe dla rozumowania w następnym punkcie. Także przemyśleń tu żadnych nie ma, jedynie wprowadzenie oznaczeń. Sytuacja ta jest pokazana tu: http://aps-projekt.pl/mrowki/mrowki09.gif .
Na razie wiemy tylko tyle, że jeden z wierzchołków należy do podzbioru „zielono-żółtego”, a drugi do „czerwono-pomarańczowego”. Dla każdego z tych podzbiorów (robimy to dla obydwu, ponieważ w tym momencie nie wiemy jeszcze, który z nich będzie nas później interesować) wyznaczamy kolejne wierzchołki doń należące przechodząc pomiędzy nimi wyłącznie krawędziami wolnymi od mrówek. Po wyszukaniu wszystkich, patrzymy, które z nich są końcami krawędzi z mrówkami (będzie to przytłaczająca większość – na wspomnianym rysunku jedynie dwa z nich takimi nie są), odrzucamy jednak te, u których WSZYSTKIE „mrówcze” krawędzie są przynależne do tego podzbioru (czyli ich drugi koniec jest jego elementem). Na rysunku te nie interesujące nas wierzchołki zostały oznaczone na żółto i pomarańczowo, natomiast nie mające znaczenia granice – linią przerywaną na białym tle.
W następnym punkcie będziemy analizować tylko krawędzie oraz ściany, których wierzchołki należą do różnych podzbiorów. Końce tych krawędzi wyróżniono kolorami zielonym i czerwonym, granicę pomiędzy podzbiorami – przerywaną linią na niebieskim tle, na samych zaś krawędziach (przebiegających w poprzek tej granicy) umieszczono czerwone mrówki (których kierunek marszu zostanie za chwilę ustalony).
……………………………
9. Zgodny kierunek ruchu mrówek.
Ostatnią rzeczą, którą należałoby określić jest kierunek ruchu mrówek „granicznych”. Sytuacja po ostatnich ustaleniach pokazana jest tu: http://aps-projekt.pl/mrowki/mrowki10.gif . Jak widać na rysunku, wiemy już dokładnie którędy przebiega granica, natomiast nie wiadomo, w którą stronę poruszają się tworzące ją mrówki. Należy jednak pamiętać, że kierunek ruchu każdej z nich jest zdeterminowany ścianą, którą obiega, tak jak to pokazują czarne strzałki.
Analizę rozpoczynamy od dowolnej z tych mrówek i obserwujemy kierunek jej ruchu, który może być oczywiście w obie strony. Przypuśćmy, że będzie to wyglądać jak u mrówki oznaczonej kolorem zielonym. Zobaczmy jak to wpłynie na pozostałe.
W tym celu spoglądamy na inną z krawędzi granicznych, ale należącą do tej samej ściany co pierwsza. Na rysunku znajduje się ona na lewo od niej (trzecia od lewej). Mrówka po tej krawędzi może teoretycznie przemieszczać się w dowolną stronę, ale zauważmy, że gdyby szła w przeciwną niż pierwsza, oznaczałoby to (biorąc pod uwagę konieczność poruszania się zgodnie ze wskazówkami zegara), że również należy do tej ściany. To byłoby oczywiście sprzeczne z warunkami zadania, tak więc po tej krawędzi i w tym kierunku żadna mrówka iść nie może. Ponieważ jednak wiemy, że jakaś mrówka tam się znajduje, więc świadczy to o tym, że maszeruje ona w przeciwną stronę niż założono pierwotnie, czyli zgodnie z kierunkiem pierwszej mrówki.
Sytuacja to pokazana jest na rysunku tu: http://aps-projekt.pl/mrowki/mrowki11.gif . Kolorem czerwonym oznaczono kierunek wykluczony, na zielono – właściwy. Rozumowanie to powtarzamy dla następnej krawędzi (drugiej od lewej) itd.
Dodatkowego wyjaśnienia wymaga kontynuacja po osiągnięciu skrajnej krawędzi. Mrówka, która po niej idzie znajduje się od strony zewnętrznej. Świadczy to o tym, że nie jest to mrówka przynależna którejkolwiek ze ścian kojarzonych z całym zbiorem, a jest ona tą mrówką dodatkową. Ponieważ taka może być tylko jedna (cała reszta pochodzi od ścian związanych z naszym zbiorem), więc na drugiej zewnętrznej granicznej krawędzi (pierwszej od prawej) nie może poruszać się po jej zewnętrznej stronie, a w związku z tym musi po wewnętrznej, co również determinuje zgodny z poprzednimi mrówkami kierunek marszu. Dalej już powtarzamy to rozumowanie bez zakłóceń, aż osiągniemy ostatnią z granicznych krawędzi. Wtedy możemy stwierdzić, że wszystkie mrówki tworzące granicę przemieszczają się w tę samą stronę (zielone strzałki).
A co stałoby się, gdyby pierwsza mrówka szła w odwrotnym kierunku? Wówczas prowadzimy analogiczne rozumowanie, w wyniku którego okazałoby się, że i pozostałe poruszają się odwrotnie. Tak czy inaczej wszystkie zawsze zmierzają w tę samą stronę.
……………………………
10. Podsumowanie.
W ten sposób wykazaliśmy, że w dowolnym zwartym zbiorze wierzchołków (wraz z przynależnymi krawędziami, ścianami i mrówkami) po dodaniu na dowolnej nie zajętej krawędzi jeszcze jednej mrówki będzie można wyodrębnić zwarty niepusty podzbiór wierzchołków w taki sposób, że na wszystkich krawędziach łączących elementy tego podzbioru z pozostałymi wierzchołkami zbioru pierwotnego będą znajdować się mrówki zmierzające w kierunku tegoż podzbioru.
Lemat zatem został udowodniony, a sytuacja końcowa pokazana jest tutaj: http://aps-projekt.pl/mrowki/mrowki05.gif .
……………………………
Tu na razie przerywam wyjaśnienia, bo chciałbym uzyskać jakiś odzew czy są one zrozumiałe.
Jednocześnie przepraszam, że tak wolno odpowiadam, ale jak widać wymaga to trochę pracy, a w związku z tym i czasu.
Zgodnie z tym, co napisałem we wstępie, część druga niebawem (powinna już być trochę krótsza).
Pozdrawiam
AB
Wow! Jestem pod wrażeniem nakładu pracy. Mam nadzieję wkrótce przeczytać i skomentować tekst.
W mordę jeża (mrówki)!
Komentarze Andrzeja69 są jak łamiblog w łamiblogu.
Pozdrawiam
Rzeczywiscie ogrom pracy, ale może jest jakieś proste rozwiązanie? Np. jak dotyczące innej zagadki, też o mrówkach (NIEZBĘDNIK INTELIGENTA POLITYKA NR 27 z 3 lipca 2004).
Cytuję:”…jest kij o dlugości 2 m, po tym kiju chodza mrówki. Każda mrówka chodzi z szybkością jednego centymetra na sekundę, w lewo albo w prawo. Jeśli się dwie mrówki spotykają, robią w tył zwrot i idą z powrotem. Tych mrówek jest na początku dwieście, jeśli któraś z nich dojdzie do końca kija, spada. Pytanie brzmi: po jakim czasie można być pewnym, że na kiju nie będzie ani jednej mrówki, bo wszystkie spadną?
….Otóż to, jak się zachowuje każda konkretna mrówka A,B,C itd, w ogóle nie jest istotne. Wszystko jedno, czy jak się spotka mrówka A z mrówką C, to obie wykonają zwrot w tył, czy po prostu miną się, bo i tak jedna nadal będzie szła w lewo, a druga w prawo. Czyli z punktu widzenia dynamiki te zmiany kierunku w ogóle można pominąć. I w związku z tym odpowiedź robi się prosta (cały czas cytuję): wszystkie mrówki spadną po takim czasie, jaki jest potrzebny jednej mrówce idącej z prędkością centymetra na sekundę do przejścia całego kija z jednego końca na drugi.”
Nadal nie wszystko jest dla mnie jasne, jednak z rysunkami jest już dużo wygodniej i uważam, że znacznie skuteczniej byłoby zamieścić zakończenie z rysunkami i opisem niż żebyśmy mieli omawiać szczegóły tego co jest aktualnie, bo wolałbym najpierw poznać pełny obraz dowodu, a ew. później rozważyć celowość skupienia się na tych czy innych niuansach.
Mimo wszystko, „oficjalne” rozwiązanie też chciałbym poznać.
Bezpośrednio z „grą w mrówki” nie jest to związane, ale nieco mnie zaskoczyło stwierdzenie (to w nawiasie):
„Dlatego zalecałbym przeanalizowanie wywodu z Wikipiedii (tu od razu odpowiadam na zadane pytanie: tam nigdzie nie ma mowy o siatce!)”.
Cytuję Wikipedię (http://pl.wikipedia.org/wiki/Twierdzenie_Eulera_o_wielo%C5%9Bcianach):
„Dowód: Wyobraźmy sobie wykonany z jakiegoś materiału (np. z tektury) wielościan. Jeżeli go rozetniemy wzdłuż krawędzi, tak jednak, aby jedna ściana przylegała do sąsiedniej, to możemy całą bryłę rozwinąć na płaszczyźnie”
Czy wtedy nie powstanie siatka wielościanu?
nie ma żadnej gry!!!