Wpis z mrowiska
Stopień trudności łamigłówki, jak zresztą czegokolwiek, to rzecz względna. Jeśli w poprzednim wpisie zaznaczyłem, że zadanie z japońskimi samochodami jest dość trudne, to wcale nie znaczy, że dla kogoś nie może się ono okazać pestką. Aby precyzyjnie określić trudność, wypadałoby skorzystać z jakiegoś wzorca. W gruncie rzeczy jednak taki wzorzec nie miałby większego sensu, bo przynajmniej z grubsza wiadomo, co jest łatwe, a co wymaga większego wysiłku lub umiejętności – i to wystarcza.
Takie przemyślunki dotyczące stopnia trudności dopadły mnie z dwóch powodów. Po pierwsze zauważyłem, że zadanie z wypożyczalnią aut można bardzo łatwo zmienić w naprawdę trudne, bardzo trudne lub horrendalnie trudne, a nawet – przy dzisiejszym poziomie techniki obliczeniowej – praktycznie nierozwiązywalne (o tym w następnym wpisie). Po drugie, obecnie siedzę po uszy w mrowisku i co chwila trafiam na zadania, przy których to samochodowe jest niemal trywialne. Przygotowuję artykuł o łamigłówkach, w których występują mrówki. Pomysł, zapewne nieco kuriozalny, przyszedł mi do głowy po wpisie o łamimrówkach. Zadań myrmekologicznych jest całkiem sporo, bo mrówka znakomicie nadaje się do roli punktu poruszającego się po płaszczyźnie. Jako pierwszy zauważył to Fibonacci, umieszczając postać formica aenigmistica na łamach wydanej w 1202 roku „Księgi obliczeń”.
Z zadaniami Fibonacciego poradziliby sobie dziś pierwszoklasiści, ale niektóre współczesne mrówcze twarde orzeszki mogą stanowić niezły zgryz nawet dla absolwentów matematyki.
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ą.
Zastanawiałem się nawet, czy to w ogóle można nazwać łamigłówką. Jest wprawdzie fabułka, a rozwiązywanie nie wymaga właściwie żadnej wiedzy matematycznej, jednak logicznie główkować trzeba jakby obok i kilka poziomów wyżej, niż w przypadku, powiedzmy, bardzo trudnego sudoku.
Podobne wątpliwości może budzić poniższe zadanie.
Ktoś zamierzał otworzyć małą walcowatą puszkę z kawiorem. Założył otwieracz i w tej samej chwili zrezygnował z zamiaru, po czym odstawił puszkę do spiżarni. Nie zauważył jednak, że na skutek przymiarki puszka została przebita, w jej krawędzi powstała dziurka (D).
Zwabiona zapachem kawioru mrówka dotarła do podstawy puszki w punkcie A najbardziej oddalonym od D (umieszczonym symetrycznie do D względem centrum puszki), który wkrótce także odnalazła. Z czasem mrówki wydeptały na puszce dwupasmową ścieżkę od A do D. Drugim pasmem owady wracały z łupami. Okazało się, że dzięki niezwykłemu mrówczemu zmysłowi wytyczona trasa A-D była najkrótszą z możliwych. Jaka była jej długość i przebieg na powierzchni puszki o wysokości h i promieniu podstawy r.
Z jednej strony rozwiązywanie tego zadania wymaga korzystania z niełatwych metod analitycznych (szukanie ekstremum lokalnego funkcji, liczenie drugiej pochodnej), czyli, że tak powiem, łamania głowy inaczej. Z drugiej można je rozgryzać poniekąd intuicyjnie, korzystając z metod elementarnych, zdecydowanie łamigłówkowych i otrzymać poprawny wynik (a ściślej dwa wyniki) mimo… niewłaściwego sposobu rozwiązywania. Dzięki takiemu zbiegowi okoliczności temat puszeczki z kawiorem jest jednak w pewnym stopniu łamigłówkowy. A przy okazji jest niejako odrobinę świąteczny, bo wszak kawior to jajka:).
Pogodnych świąt.
PS Do japońskich aut powrócę tuż po świętach, wówczas także uwolnię komentarze z rozwiązaniem zadania z wpisu Jap Co. W związku z tym termin zakończenia zabawy z grą-nagrodą zostaje przedłużony do wtorkowego południa (25 marca).
Komentarze
Proponuję takie rozwiązanie:
Po rozcięciu powierzchni bocznej puszki otrzymujemy prostokąt
o wysokości h i szerokości 2\pi r. Jedna mrówka znajduje się
w prawym/lewym górnym rogu, a druga na dole po środku.
Odległość między nimi to \sqrt{h^2 + \pi^2 r^2}.
Hmm.. a ja mam taką propozycję:
„Na chłopski rozum” najkrótsze drogi są dwie: albo spiralnie po boku puszki („po gwincie”), albo wejść na górę i pójść w prostej linii przez środek wieczka.
Pierwsza droga to sqrt(pi^2*r^2 + h^2), druga to oczywiście h+2r.
Jeżeli przyrównamy obie funkcje do siebie, otrzymujemy h~1,5r. Dla h mniejszych od tej wartości krótsza jest droga druga, dla większych pierwsza.
Chyba niczego nie pomyliłem 😉
Pozdrawiam
Odległość1 AD=PI*r*h, gdyby mrówka poszła po spirali i AD=2r+h gdyby poszła po średnicy i wysokości. Obie drogi będą równe dla warunku
r=h(PI-1).
Pozdrawiam.
Wesołych Świąt Wielkanocnych
Hmmm. A co z mozliwoscia, ze mrowka idzie kawalek po bocznej sciance, a kawalek po cięciwie?
Niestety jak dla mnie otrzymuje sie (matematycznie) paskudne równanie (pierwszej pochodnej), którego nie potrafię rozwiązać. (Skądinąd mam podejrzenie, ze nie da sie go rozwiazac dokladnie) Analiza w Maple’u dodatkowo sugeruje, ze faktycznie takie rozwiazanie posrednie jest optymalne np. dla r=1, h=5 (o ile dobrze pamietam…)
Ech… tyle ostatnio ciekawych łamigłówek, a ja nie mam nawet chwili, aby się za nie zabrać. 🙁 Może przez święta uda się nadrobić zaległości.
A na razie, dla Pana, Panie Marku oraz dla innych główkołamaczy wielkanocne życzenia wesołych jaj i smacznych zajączków 😉 .
Pozdrawiam
AB
Panie Andrzeju69, wlaśnie się zbieram, żeby sprobować Pana zastąpić i porozgryzać w następnym wpisie zadanie z samochodami. Jeśli zatem jest Pan jeszcze trochę zajety, to ma Pan jeszcze trochę wolne:)
Do Esteona: zapewne otrzymał Pan wzór, z którego należy wyznaczyć wartośc kąta jako funkcję h i r. Faktycznie, tego nie sposób rozwiązać. Aby dojść do sensownych wniosków, trzeba stosować „chitre” sposoby związane z szukaniem ekstremów lokalnych, ale to temat zdecydowanie nie świąteczny.
Pozdrawiam prawieświątecznie
mp
Zadanie z samochodami to jedno z ciekawszych, z jakimi się ostatnio zetknąłem. Wymagało twórczego wysiłku, bo nie poddawało się żadnemu znanemu mi schematowi dojścia do rozwiązania. Mam nadzieję, że udzieliłem poprawnej odpowiedzi.
Życzę pogodnych Świąt!
Panie Marku!
Najserdeczniejsze życzenia świąteczne składam.
Jednocześnie postanowiłem „porządnie matematycznie” rozwiązać drugą zagadkę z mrówkami. Oto efekt, trochę przydługi mi wyszedł, mam nadzieję, że przejdzie:
Gdybym dostał to zadanie na analizie, rozwiązywałbym je tak:
Po pierwsze: możemy przyjąć, że r=1. W innym przypadku przeskalujemy puszkę tak, żeby promień był jednostkowy, ważny w zadaniu jest tylko stosunek h/r.
Po drugie: droga mrówek będzie wyglądała tak: idziemy najkrótszą drogą do pewnego punktu na górnym wieczku, a potem po nim po cięciwie do otworu.
Rozważmy funkcję f, określoną na [0,Pi], gdzie f(x) to długość drogi mrówki która idzie w opisany wyżej sposób, przechodząc przez punkt, taki, że długość łuku wyznaczonego przez niego i rzut prostopadły punktu A na górne wieczko wynosi x.
Najkrótsza droga po powierzchni bocznej dla konkretnego x ma długość sqrt(h^2+x^2)
Najkrótsza droga po cięciwie to 2*sin((Pi-x)/2) (bo przy okazji Pi-x to wartość kąta między punktem D a x).
To oznacza, że:
f(x)=sqrt(h^2+x^2)+2sin((Pi/2-x/2) sin można zamienić na cos:
f(x)=sqrt(h^2+x^2)+2cos(x/2), policzmy pochodną:
f'(x)=2x/2sqrt(h^2+x^2)-sin(x/2), badamy, kiedy pochodna jest >0:
x/sqrt(h^2+x^2)-sin(x/2)>0
x/sqrt(h^2+x^2)>sin(x/2). szczęśliwie obie strony nierówności są więsze od 0, więc można podnieść ją do kwadratu:
X^2/(h^2+x^2)>sin^2(x/2)
x^2>sin^2(x/2)h^2+sin^2(x/2)x^2
x^2(1-sin^2(x/2)>h^2sin^2(x/2) korzystamy z jedynki trygonometrycznej.
x^2>h^2sin^2(x/2)/cos^2(x/2)
x^2/h^2>tg^2(x/2)
x/h>tg(x/2)
funkcje x/h i tg(x/2) przecinają się w dokładnie jednym punkcie (na (0.Pi)), przy czym dla x bliskich Pi tg(x/2) jest większy więc:
Pochodna najpierw jest dodatnia,
w pewnym punkcie x0 jest równa zero,
potem jest ujemna.
To oznacza, że f rośnie od 0 do x0, tak osiąga swoje maksimum, a następnie maleje od x0 do Pi.
Czyli prawidłowym rozwiązaniem jest to, które przychodzi do głowy „na chłopski rozum”:
najkrótsza droga to krótsza z dwóch:
– cały czas po powierzchni bocznej
– najpierw pionowo do góry, a potem po średnicy.
uff…
Plazmoniku, dziękuję (za życzenia) i gratuluję (rozwiązania), bo to jest TO, czyli piątka.
Tak między nami mówiąc, Ola, Cosi i JohnyR w gruncie rzeczy rozwiązali inne zadanie, polegające na określeniu, kiedy jedna z dwóch wybranych dróg będzie dłuższa (krótsza) od drugiej. Ale rozwiązaniem trafili w sedno, więc czwórka, przynajmniej ode mnie, im się należy:)
Przedzdrawiam (bo przedświątecznie)
mp
Moim zdaniem w rozumowaniu przedstawionym przez Plazmonika pod sam koniec wkradła się pewna nieścisłość: Otóż o wspomnianych tam funkcjach x/h i tg(x/2) i ich punktach wspólnych można powiedzieć to, że na pewno zawsze przecinają się w zerze, natomiast w przedziale (0,pi) (otwartym) mogą mieć dokładnie jeden punkt wspólny, ale też mogą nie mieć żadnego!
Ta druga sytuacja bedzie mieć miejsce, gdy wysokość walca będzie dłuższa od średnicy jego podstawy, czyli, przy przyjętym założeniu, że r=1, będzie większa niż 2. W tej sytuacji pochodna będzie zawsze ujemna, a więc funkcja długości drogi będzie stale malejąca.
Co to zmienia?
W sumie niewiele. Najkrótsza droga będzie oczywiście zawsze biegła albo wyłącznie po powierzchni bocznej, albo dokładnie pionowo, a później (lub wcześniej) wzdłuż średnicy.
To z którym przypadkiem będziemy mieć do czynienia, będzie zależało od stosunku h/r. Jeśli przekroczy wartość pi*pi/4-1 = 1.4674… będzie to wariant pierwszy, jeśli będzie mniejszy to drugi. Gdy będzie równy – obie drogi będą tej samej długości (o czym wspominał już Cosi).
Natomiast warto według mnie zwrócić uwagę na to, że gdy ów stosunek będzie się jednak trochę (i to niekoniecznie znacznie) różnił od wspomnianej wartości, to jedna z tych potencjalnie najkrótszych dróg łatwo może stać się drogą… najdłuższą! (lub prawie)
Jeżeli będzie większy, to wystarczy, że osiągnie 2. O tym już wspominałem – funkcja drogi jest wówczas stale malejąca, a więc najkrótsza droga biegnie w całości po powierzchni bocznej walca, natomiast wysokość+średnica jest drogą najdłuższą.
Z kolei jeśli stosunek h/r będzie mniejszy od pi*pi/4-1, to choć formalnie rzecz ujmując „droga bokiem” najdłuższą nigdy nie będzie (miałoby to miejsce tylko wtedy gdyby był on równy 0), to jednak trzeba zauważyć, że nie będzie się ona dużo od niej różnić. Wystarczy, że stosunek ten będzie wynosić 1 (czyli h=r) – w tej sytuacji różnica w stosunku do drogi maksymalnej jest mniejsza niż 1%! Jeżeli będzie mniejszy, różnica ta będzie się jeszcze bardziej zacierać.
Napisałem to po to, aby pokazać jak diametralnie może się zmienić odpowiedź po wcale nie tak dużych zmianach proporcji puszki.
Także trzeba, myślę, tym „łamimrówkom” pogratulować intuicji i dobrej miarki.
Pozdrawiam
AB
Aj, rzeczywiście, dziękuję Andrzeju69, za zwrócenie uwagi.
ps. dla osób zainteresowanych „łamigłówkami matematycznymi” (o ile taka kategoria istnieje), polecam ropuchę:
http://www.cs.cmu.edu/puzzle/
Zadania są trudne, ale próby rozwiązania dają mi wiele satysfakcji.
Zainteresowało mnie zadanie z mrówkami na wielościanie wypukłym i usiłowałem je rozwiązać. Do konkretnej odpowiedzi nie doszedłem, ale postanowiłem podzielić się swoimi spostrzeżeniami, a może komuś pomogą w dojściu do rozwiązania.
1) Jeżeli mrówki mogą się kiedykolwiek spotkać, to na pewno idąc wprost na siebie z naprzeciwka. Nigdy nie będzie tak, że spotkają się gdy jedna prześcignie drugą.
2) W sytuacji w której dwie mrówki znajdą się na tej samej krawędzi (nawet na jej krańcach) możemy uznać, że na pewno nastąpiło spotkanie.
3) Wyobraźmy sobie eksperyment:
a) W chwili 0 zaczynamy obserwować wszystkie mrówki i czekamy aż każda z nich obiegnie dokładnie cały obwód swojego boku wielościanu. Tę ostatnią chwilę, gdy ostatnia mrówka dokona pełnego obiegu, nazwijmy t.
b) Wśród wszystkich mrówek możemy wyróżnić najwolniejszą (albo najwolniejsze – jeśli miały taki sam czas) i najszybszą (albo najszybsze), albo wszystkie dokonały obiegu w tym samym czasie.
c) Pełny obieg u każdej mrówki na pewno musiał nastąpić, bo mrówki poruszają się minimum 1 mm/h (z treści zrozumiałem, że mogą się zatrzymywać, ale nie wolno im się cofać).
4) Dwie własności wielościanów wypukłych uznałem za interesujące i być może niezbędne by rozwiązać zadanie.
a) Wzór Eulera: S + W = K + 2
S – liczba ścian (jednocześnie: liczba mrówek),
W – liczba wierzchołków
K – liczba krawędzi wielościanu
b) Każdy wielościan wypukły można „rozłożyć” na płaszczyźnie przedstawiając jego siatkę.
5) Rozpoczynając eksperyment z pkt. 3, w chwili 0, każda z mrówek musiała znaleźć się na osobnej krawędzi (bo – patrz stwierdzenie z pkt. 2).
a) Liczba krawędzi zajętych przez mrówki to S, a liczba krawędzi wolnych od mrówek to (W – 2), bo K – S = W – 2 (patrz pkt. 4a).
b) Wystarczy udowodnić, że od chwili 0 do t musiało nastąpić conajmniej jedno spotkanie. Jednak trzeba wziąść pod uwagę, że t może być mniejsze, równe albo większe od 1 h. Jeśli t jest mniejsze od 1 h, to wcale nie jestem pewien czy nie mogłoby być tak, że każda mrówka dokona okrążenia i jednocześnie spotkanie od 0 do t nie nastąpi, a mogłoby nastąpić po t.
c) Podobnie nie wiadomo, czy wszystkie boki wielościanu są mniejsze, równe czy większe od 1 mm (podejrzewam, że należy założyć, że są większe).
6) Rysowałem sobie np. czworościan, a raczej jego symboliczną wizualizację na płaszczyźnie (przypominało mi to trochę zadanie z trójnicami) – ciężko to wyjaśnić bez zamieszczania obrazków.
Obwód ścian bocznych dla każdej mrówki rysowałem jako kółko, które podzieliłem na części – każda część to inna krawędź. Łączyłem odpowiednie części różnych kółek linią, by oznaczyć, że to ta sama krawędź.
Potem rozstawiałem mrówki, założyłem, że któraś jest najwolniejsza i rozpatrywałem gdzie mogą być inne podczas podróży tej najwolniejszej.
Rozpatrywałem tak sytuację dla wierzchołka łączącego trzy ściany boczne – czyli każda z trzech mrówek miała na swoim kółku dwa boki zagrożone spotkaniem, a jeden tymczasowo „bezpieczny”.
Są takie rozstawienia, w których musi nastąpić spotkanie, a są i takie gdzie wcale nie musi, czy może raczej: nie wiadomo. Na razie nie mam więcej pomysłów. Może gdzieś robię błąd. Może brak mi jakiejś istotnej informacji o wielościanach albo we wnioskach.
W każdym razie: jestem ciekaw rozwiązania i chciałbym się z nim zapoznać.
Panie Michale, spróbuję podać dowod w jednym z najbliższych wpisów, jeśli w międzyczasie nikt go nie poda. Jest to niełatwe także dlatego, ze prawdopodobnie nie obejdzie sie bez rysunku.
mp
PS Wzór Eulera i w ogóle jakikolwiek wzór nie jest potrzebny. Tylko sprytny sposób i logika.
ja próbowałem wykazać, ze musi nastapić jakaś chwila, w której do któregokolwiek z wierzchołków beda się zbliżać mrówki po wszystkich krawędziach z tego wierzchołka, no ale niestety bez sukcesu
Mam pomysł. Po wskazówkach Pana Marka i Pafcia powtórnie zabrałem się do łamigłówki kładąc większy nacisk na rysunki. Nie jestem jednak skłonny nazwać ścisłym dowodem tego co zaraz napiszę.
Rozumowanie zaczęło się od stwierdzenia, że jeśli na jednej krawędzi już znajdują się dwie mrówki (obojętnie gdzie i w jakiej odległości) to spotkanie musiało nastąpić. Po narysowaniu odcinka (krawędzi) stwierdzamy, że po jego prawej stronie jest jakaś powierzchnia, i po lewej. Skoro są dwie, to i dwie mrówki są na pewno. Jakkolwiek byśmy ich nie umieścili na narysowanym fragmencie (na razie: tylko jednej krawędzi) dojdziemy do wniosku, że wkrótce się spotkają lub musiały już spotkać się w przeszłości.
Zauważyłem, że jeśli narysuję na papierze dowolne powierzchnie łączące się ze sobą na pewnej długości (np. koło podzielone na dowolną ilość części, albo kwadrat, etc.) to mrówki wędrujące po najmniejszych częściach tej (regularnej lub nie) figury zawsze się spotkają, pod warunkiem, że jest jeszcze jedna mrówka, która obiega całą figurę dookoła i porusza się przeciwnie do ruchu wskazówek zegara (czyli przeciwnie niż inne mrówki).
Doszedłem do tego przez indukcję, a nie dedukcję. By do tego przekonać może napiszę tylko tyle:
dla koła podzielonego na 2 części i 3 mrówek na pewno nastąpi spotkanie, dla koła podzielonego na 3 części i 4 mrówek też na pewno nastąpi spotkanie (proszę sobie przeanalizować te sytuacje i pamiętać o zachowaniu właściwych kierunków ruchu mrówek).
A właściwy „dowód” 🙂 brzmi tak:
Proszę wyobrazić sobie dowolny wielościan, pusty w środku, jego ściany boczne to cienkie rozciągliwe błony, a krawędzie są giętkie i łatwo się wydłużają.
Usuńmy jedną ścianę boczną tego wielościanu. Teraz rozciągnijmy wielościan na płaskiej powierzchni tak, aby powstała figura, której obwód to jednocześnie krawędzie usuniętej ściany bocznej.
(np. czworościan da trójkąt podzielony na 3 części – a może raczej koło ?;
sześcian da: mały kwadrat w większym kwadracie (kole?), gdzie wierzchołki małego kwadratu są połączone odcinkami z wierzchołkami dużego)
Gdy teraz będziemy analizowali położenie mrówek, musimy pamiętać, o mrówce obiegającej usuniętą ścianę i o tym, że porusza się ona przeciwnie do ruchu wskazówek zegara.
Przeczytałem wywód Michała Gajzlera i muszę powiedzieć, że chociaż zawiera bardzo wiele interesujących spostrzeżeń, to nie można go jednak nazwać formalnym dowodem (co Autor sam poniekąd przyznaje).
Generalnie luka występuje w rozumowaniu uogólniającym: Wykazanie konieczności spotkania trzech mrówek na podzielonym na dwie części kole nie nastręcza trudności, ale z czterema na trzyczęściowym jest już dużo gorzej. Można oczywiście rozważać wszystkie przypadki (wierzę, że Autor to zrobił), ale, jak pokażę dalej, nie jest to konieczne. Poza tym – co najważniejsze – wcale nie oznacza to, że musi tak być w bardziej skomplikowanych sytuacjach.
Dlatego też postanowiłem udowodnić konieczność spotkania mrówek nieco inaczej, choć nie ukrywam momentami występują pewne podobieństwa. Starałem się też, aby nie wymagało to sporządzania rysunku, którego w formie komentarza przesłać się nie da.
Najpierw pewne spostrzeżenia natury ogólnej odnoszące się do sformułowań użytych w treści łamigłówki:
Stwierdzenie, że „każda mrówka przemieszcza się w ciągu godziny o co najmniej 1 milimetr” tak naprawdę nic nie wnosi do zadania. Brak bowiem punktu odniesienia – nic nie wiadomo ani o rozmiarach wielościanu, ani o czasie w jakim miałoby dojść do spotkania. Całkowicie wystarcza więc informacja, że każda mrówka „cały czas wędruje … zgodnie z ruchem wskazówek zegara”.
Zakładam zatem, że prędkość mrówek może być w dowolny sposób zmienna, co w praktyce daje możliwość „czekania” (zwalniając maksymalnie) na przejście innej z nich, natomiast nie ma możliwości wycofania się.
Właściwy dowód przeprowadzę metodą nie wprost.
Załóżmy, że mrówki mają szansę nawzajem się unikać.
Najpierw pewne rozumowanie pomocnicze:
Rozpatrzmy dwa wielokąty mające jedną wspólną krawędź (i dwa wspólne wierzchołki). Wokół każdego z nich w tym samym kierunku biega mrówka. Jeżeli mrówki te nie mogą się spotkać, nie mogą jednocześnie znaleźć się na środkowej krawędzi (gdyż po niej poruszałyby się w przeciwne strony). Oznacza to, że zawsze przynajmniej jedna mrówka (jeżeli obie naraz – niczego to nie zmieni – możemy wtedy w dalszych rozważaniach brać pod uwagę dowolną z nich) musi znajdować się na zewnętrznych krawędziach i będzie się na nich pojawiać niejako „na przemian”.
Jeżeli teraz pominiemy to, co dzieje się na wspólnym odcinku, to efekt będzie taki jakbyśmy mieli jedną mrówkę biegającą w tym samym kierunku dookoła całości.
Wniosek:
Dowolne dwie sąsiednie ściany (z biegającymi wokół nich dwiema mrówkami) możemy zawsze zastąpić jedną powierzchnią (bez krawędzi w środku) z pojedynczą mrówką biegającą po jej obwodzie.
Załóżmy teraz, że nasz wielościan jest wykonany z w miarę elastycznego materiału i będzie się on poddawać operacji „wygładzania krawędzi”.
Wybieramy w tym celu dwie dowolne sąsiadujące ściany i zastępujemy je jedną (nie do końca płaską) powierzchnią. Następnie ją i kolejną ścianę znowu łączymy w jedno. Tak postępujemy do czasu, aż scalimy wszystkie ściany z wyjątkiem ostatniej. Wynikowa figura będzie w tej chwili przypominać półkulę z jedną „wypadkową” mrówką biegającą po obwodzie zgodnie ze wskazówkami zegara. Podstawą tej półkuli będzie zaś ostatnia nie wchłonięta ściana, wokół której również biega mrówka. Ponieważ jednak znajduje się ona „od spodu”, mrówka ta porusza się w przeciwną stronę, a to oznacza, że obie muszą się spotkać.
Dochodzimy do sprzeczności. W związku z tym albo ostatnia mrówka musi spotkać którąś ze swoich sąsiadek, albo spotkanie musiało zajść jeszcze (w sensie toku rozumowania) wcześniej uniemożliwiając w którymś momencie łączenie ścian.
Uważam zatem, że teza została udowodniona.
Pozdrawiam
AB
Stwierdzenie, że mrówki idą o co najmniej 1 milimetr jednak cos wnosi, bo w przeciwnym wypadku mrówki mogłyby iść coraz wolniej i w efekcie np. nie zrobić żadnego obejścia wokól jednej ściany. Ale oczywiscie mozna by to sformulowac na wiele roznych sposobow.
Do Esteona:
Nie zgadzam się z Tobą.
Obawiasz się, rozumiem, sytuacji, gdy mrówka będzie poruszać się tak wolno, że życia jej nie starczy na choć jednokrotne okrążenie ściany (której minimalny wymiar musi być taki, aby mrówka mogła się na niej zmieścić). Ale zauważ, iż równie dobrze należałoby poczynić założenia co do maksymalnych rozmiarów wielościanu. Jeżeli będzie wielkości np. kuli ziemskiej, to nawet maszerując z największą prędkością z jaką mrówki są w stanie się przemieszczać, też nie uda się go obejść.
Biorąc jednak pod uwagę brak wytycznych w tym kierunku, uważam że operujemy sensownymi wartościami i to zarówno długości boków wielościanu jak i szybkości (przynajmniej średniej) każdej mrówki.
Reasumując: Albo zabezpieczamy się i tworzymy kompletne założenia, albo minimalizujemy je zdając się na podejście zdroworozsądkowe.
Takie jest moje zdanie.
Pozdrawiam
AB
Panie Andrzeju, nie jestem przekonany co do tego „przerobienia” dwóch sąsiednich powierzchni na jedną z jedną mrówką.
Dwa twierdzenia dla dwóch sąsiednich boków są pewne:
1) Jeśli mrówki na nich nigdy się nie spotkają, to części obwodu nie będące częścią wspólną będą obchodzone, w pewnym sensie, na przemian (zgadzam się z Panem, że jeśli obie będą jednocześnie poza wspólnym odcinkiem to nadal można uznać tą „przemienność” pokonywania „bezpiecznej” części obwodów).
2) Jeśli poza wspólną krawędzią nie ma ani jednej mrówki to musiało (musi) nastąpić spotkanie.
Jednak czy analogiczne twierdzenia są prawdziwe dla większej ilości powierzchni niż 2? Uważam, że to nie zostało udowodnione, bo „uogólniona” mrówka porusza się jednak już na innych zasadach (teleportuje się w dwóch punktach i ew. rozdwaja) oraz uogólnienie takiej „powierzchni uogólnionej” z inną normalną powierzchnią (albo też raz „uogólnioną”) niekoniecznie da taki sam efekt jak uogólnienie dwóch normalnych.
Być może rzeczywiście można pominąć te różnice w sposobie poruszania się zwykłej i „uogólnionej” mrówki, jednak jakoś tego „nie widzę” i uważam te różnice za istotne.
Całkowicie zgadzam się co do kwestii prędkości mrówek.
Witam.
Andrzeju69, Twój dowód zdaje się nie mieć żadnych słabych stron i spełnia wszelkie wymogi stawiane dowodom. Gratuluję. Nie mogę się jednak zgodzić z uwagą co do prędkości. Mrówki – powiedzmy dwie ostatnie – mogą wystartować z całkiem niemałą prędkością, ale potem wyhamowywać asymptotycznie do zera, i to tak, by droga S=całka z v*dt po [0,nieskończoność] była skończona. Zasadne więc jest założenie, że prędkość jest stale większa od pewnej dodatniej wartości, chociażby maciupeńkiego epsilon.
Pozdrawiam
Anka
Do Andrzeja69:
Dlaczego mrówka nie obejdzie ściany wielkości kuli ziemskiej?
Przeciez idąc min. 1mm /h przejdzie powiedzmy 20000 km w raptem nieco ponad 2283 lata.
A z kolei nawet jeśli sciana ma długość obwodu równą 1 cm, to mogłoby się zdarzyć, że mrówka w chwili t (liczonej w sek) idzie z prędkością np. v(t)=(1/10)^t cm/s. No i wtedy nici z jakogokolwiek rozwiązania.
Uważam, że predkość musi być „oddzielona” od 0 (no i wielkość wielościanu skończona, ale akurat bryła o nieskonczonej srednicy nie jest wieloscianem wedlug zadnej znanej mi definicji).
Po namyśle, jednak i co do kwestii prędkości nie mogę się zgodzić. Stwierdzenie o tym, że mrówka pokonuje minimum 1 mm na 1 h jest konieczne, bo (jeśli dobrze zrozumiałem Esteona to o to chodziło), możliwa byłaby sytacja podobna jak w paradoksie Zenona z Elei – na krótkim odcinku mrówka wciąż by szła od punktu A do B nieustannie zmniejszając prędkość tak, że nigdy nie doszłaby do punktu B.
Pomyślałem, że może powinienem napisać jaśniej:
Ta jedna „uogólniona” mrówka na pewno nie może poruszać się w sposób ciągły, bo jeśli by tak było, to znaczy, że „podmrówki” z których się składa musiały spotkać się na wierzchołku.
„Uogólniona” mrówka z obwodu A dochodząc do wierzchołka musi nagle zniknąć i pojawić się gdzieś na obwodzie B, ale nie na części wspólnej A i B (między wierzchołkiem a punktem gdzie pojawi się mrówka będzie odcinek drogi nie przebytej przez „uogólnioną” mrówkę).
(Jeśli nie zniknie, a przejdzie dalej, to znaczy, że „podmrówki” musiały minąć się na wierzchołku.)
Uważam to za istotną różnicę w sposobie poruszania się mrówki „uogólnionej” i zwykłej. Jeśli ta różnica nie ma znaczenia i można w tym zadaniu rozpatrywać mrówkę „uogólnioną” jako zwykłą, to chciałbym aby to zostało udowodnione.
No i zostałem wezwany do tablicy… 🙂
Było mi siedzieć cicho – nic nie pisać – miałbym teraz spokój. 😉
W każdym razie na zarzuty (wszystkie i wszystkich) jeszcze dzisiaj dam odpowiedź. Mam nadzieję, że będzie satysfakcjonująca. Przepraszam, że tak powoli i że do tej pory jeszcze tego nie zrobiłem, ale cóż… koniec roku się zbliża…
Zabrzmiało to może dość zagadkowo, mimo to pozwolę sobie nie rozwijać tematu. Generalnie, to ci co wiedzą – to wiedzą, a ci co nie – to i tak nie będą w stanie sprawy ocenić. 😉
Na razie idę się zdrzemnąć (chwilę temu wróciłem z pracy 🙁 ).
Pozdrawiam
AB
Andrzeju69, z wielkim żalem muszę wycofać swoją fascynację Twoim dowodem.
Abstrahując od słusznej uwagi Michała G. zakładasz, że przy sklejaniu kolejnych ścian, zawsze zagwarantujesz sobie, że po obwodzie będzie ganiała przynajmniej jedna mrówka, i że obwód zlepek n-1 ścian jest równocześnie obwodem ściany n-tej. Otóż w tym sęk. Zapomniałeś o jednym: dołączając kolejną ścianę, dołączasz ją nie tylko jedną wybraną krawędzią, ale i czasami przyczepiasz do już istniejących. Inaczej z obwodami będzie nie tak. Jeżeli już to uwzględnisz, może się zdarzyć, że po n-1 krokach na obwodzie nie znajdzie się ani jedna mrówka. Łatwo to zauważyć w czworościanie: sklejając trzy trójkąty, zgodnie z Twymi wytycznymi, może się zdarzyć, że trzy mrówki wylądują na krawędziach bocznych. Inna rzecz, że albo wszystkie będą szły ku górze i wtedy i tak się spotkają, albo ku podstawie i wtedy…
No właśnie, wtedy co? Ale to już inna bajka.
Pozdrawiam
Anka
Przedstawię dokładniej swój „dowód przez indukcję” (wnioskowanie przez indukcję jest zawodne, ale może to dobry trop i ktoś wpadnie na pomysł jak udowodnić to co przedstawię za pomocą indukcji matematycznej – zupełnej).
Osoby zdeterminowane do rozwiązania tej łamigłówki proszę o sięgnięcie po kartkę, coś do pisania i uważne realizowanie kolejnych poleceń:
1) Proszę narysować pionową kreskę i nic poza tym.
To będzie krawędź wspólna dwóch ścian bocznych. Jedna ściana jest po prawej stronie kreski, a druga po lewej. Skoro ściany są dwie, to muszą gdzieś być dwie mrówki.
Cały czas będziemy zakładali, że mrówki są na tych fragmentach, które narysowaliśmy – to ważne.
W tym przypadku: dwie mrówki muszą się spotkać na tym jednym odcinku. Zgoda?
2) Proszę do pionowej kreski dorysować dwie kolejne, tak by powstała litera Y.
Punkt łączący te trzy odcinki możemy interpretować jako wierzchołek. Teraz mamy trzy powierzchnie: po lewej, po prawej i u góry – każda oddzielona naniesionym przez nas odcinkiem. Zatem musimy rozstawić trzy mrówki.
Proszę rozważyć rozmaite położenie trzech mrówek na rysunku pamiętając o właściwych kierunkach ruchu mrówek.
Te trzy mrówki zawsze musiały (lub będą musiały) się spotkać. Zgoda?
3) Proszę teraz dorysować kolejne dwa odcinki „rozwidlając” lewy górny koniec naszej litery Y.
Proszę policzyć ile mamy powierzchni. Powinny być 4.
Proszę ponownie rozważyć rozmaite położenie mrówek pamiętając o właściwych kierunkach. Prawda, że znowu musi (lub musiało) nastąpić spotkanie?
***
Moglibyśmy kontynuować zabawę z rozwidlaniem w nieskończoność. Każdą końcówkę możemy rozwidlić na kolejne dwa końce (albo i więcej końców). Jednak zawsze powinniśmy uważnie policzyć ile różnych powierzchni jest oddzielonych i rozważyć właśnie taką ilość mrówek na rysunku.
***
4) Proszę w pewnym oddaleniu od naszego rysunku, gdzieś nad nim i po prawej stronie, postawić punkt. Następnie proszę połączyć końcówki odcinków (naszego zdeformowanego nieco Y) nie przecinającymi się liniami z naniesionym punktem.
Proszę zauważyć, że dorysowane właśnie linie są tylko przedłużeniem dotychczas narysowanych odcinków. Nie powstał żaden nowy odcinek, ani żadna nowa powierzchnia.
Proszę zauważyć, że na pierwszy rzut oka powstały 3 oddzielone od siebie powierzchnie. A gdzie czwarta? Czwarta to w pewnym sensie cały obwód naszej właśnie powstałej figury – proszę się przyjżeć lewej dolnej części rysunku. Z naszego punktu widzenia, mrówka powinna poruszać się po tym fragmencie zgodnie z ruchem wskazówek zegara. To oznacza jednocześnie, że porusza się niezgodnie z ruchem wskazówek zegara po całej figurze.
Nasz obecny rysunek jest wizualizacją czworościanu na płaszczyźnie, ale ta czwarta ściana boczna „nie jest zamknięta”, tj. reprezentuje ją cała powierzchnia kartki na zewnątrz naszego rysunku.
By przekonać, że w momencie nakreślenia punktu poza rysunkiem i połączenia go z końcami odcinków, sytuacja się nie zmieniła, proszę rozważyć położenie jednej mrówki:
Porównajmy rysunki na etapie 3 i 4. Wybierzmy mrówkę, która porusza się po obu krawędziach nowo narysowanych na etapie 3. Ta mrówka zawsze znajduje się na jednym z tych odcinków, albo na drugim (zgodnie z założeniem, że mrówki mogą być tylko na narysowanej części).
Natomiast na etapie 4: ta sama mrówka porusza się albo po linii wewnątrz rysunku albo po linii na zewnątrz rysunku – widać więc, że jej sytuacja się nie zmienia, a linie są tylko przedłużeniem wcześniej narysowanych odcinków. To dotyczy i pozostałych mrówek.
***
By przeprowadzić kompletny dowód, uważam, że należy dowieść tego o czym pisałem w części oddzielonej gwiazdkami między 3 i 4 etapem, tj. że na takich właśnie rysunkach, przy takich a nie innych zasadach poruszania się mrówek – muszą się one spotkać. Dla konkretnych przypadków (nawet jeśli rysunek jest b. rozbudowany) widać gołym okiem, że tak musi być i jest dość proste to udowodnić. Ale jak udowodnić, że w każdym przypadku tak być musi? Oto jest pytanie.
Naszły mnie wątpliwości czy aby nie brakuje czegoś jeszcze oprócz udowodnienia tego o czym wyżej pisałem (bo: powyżej opisany rysunek jednak nie jest wizualizacją czworościanu). Nie mniej jednak polecam zrobić rysunek wg powyższych instrukcji.
Nad „grą w mrówki” jeszcze się nie zastanawiałem.
Zaległą obiecaną odpowiedź, wraz z pewnymi wyjaśnieniami, zamieściłem pod kontynuującym ten wątek aktualnym (1.04.2008 r.) wpisem pt. „Gra w mrówki”:
http://penszko.blog.polityka.pl/?p=187 .
Pozdrawiam
AB