Prawd\u0119 m\u00f3wi\u0105c, nie przypuszcza\u0142em, \u017ce kto\u015b spr\u00f3buje rozgry\u017a\u0107 ten orzech, zamieszczony w\u0142a\u015bciwie tylko na poparcie stwierdzenia, \u017ce mr\u00f3wcze problemy mog\u0105 by\u0107 bardzo trudne (zadanie pochodzi z eliminacji do rosyjskiej olimpiady matematycznej sprzed kilkunastu lat). Nie doceni\u0142em\u00a0wi\u0119c os\u00f3b, kt\u00f3re podj\u0119\u0142y wyzwanie, tym samym wywo\u0142uj\u0105c mnie do tablicy.<\/p>\n
Nie podejmuj\u0119 si\u0119, przynajmniej na razie, ocenia\u0107 dowod\u00f3w lub szkic\u00f3w dowod\u00f3w zamieszczonych w komentarzach, mi\u0119dzy innymi dlatego, \u017ce niekt\u00f3re fragmenty s\u0105 dla mnie niejasne. Bardzo mo\u017cliwe, \u017ce podany przez Andrzeja69 dow\u00f3d jest poprawny, cho\u0107 r\u00f3\u017cni si\u0119 od znanego mi; jak wiadomo, to samo twierdzenie mo\u017cna rozgryza\u0107 na wiele sposob\u00f3w, na przyk\u0142ad prawo wzajemno\u015bci reszt kwadratowych ma grubo ponad 150 r\u00f3\u017cnych dowod\u00f3w.<\/p>\n
Zgodnie z zapowiedzi\u0105, poni\u017cej wystawiam na krytyk\u0119 \u00f3w dow\u00f3d „oficjalny”. Stara\u0142em si\u0119, by opis by\u0142 zwi\u0119z\u0142y, wi\u0119c nie wykluczam, \u017ce niekt\u00f3re jego fragmenty mog\u0105 wyda\u0107 si\u0119\u00a0„\u015bliskie”, czyli wymagaj\u0105ce dodatkowych wyja\u015bnie\u0144.<\/p>\n
Dow\u00f3d<\/strong><\/p>\n 1. Zak\u0142adamy, \u017ce do spotkania nie dochodzi, czyli mr\u00f3wki obchodz\u0105ce s\u0105siednie \u015bciany nie mog\u0105 znale\u017a\u0107 si\u0119 r\u00f3wnocze\u015bnie na wsp\u00f3lnej kraw\u0119dzi, bo w\u00f3wczas musia\u0142yby si\u0119 na tej kraw\u0119dzi spotka\u0107.<\/p>\n 2. Nazwiemy pozycj\u0105<\/strong> rozmieszczenie wszystkich mr\u00f3wek na konkretnych kraw\u0119dziach, a ruchem<\/strong>, prowadz\u0105cym do powstania nowej pozycji\u00a0– przej\u015bcie jakiej\u015b mr\u00f3wki na nast\u0119pn\u0105 kraw\u0119d\u017a. 3. Rysujemy na powierzchni wielo\u015bcianu map\u0119: na ka\u017cdej \u015bcianie-kraju oznaczamy niebieski punkt-stolic\u0119 i ka\u017cd\u0105 par\u0119 stolic s\u0105siednich \u015bcian \u0142\u0105czymy drog\u0105 (zielona) przecinaj\u0105c\u0105 wsp\u00f3ln\u0105 kraw\u0119d\u017a (czarna). Na skrzy\u017cowaniach kraw\u0119dzi z drogami umieszczamy mr\u00f3wki (br\u0105zowe groty), tworz\u0105c tym samym konkretn\u0105 pozycj\u0119. Ka\u017cda mr\u00f3wka jest przesuni\u0119ta na swoj\u0105 \u015bcian\u0119; grot wskazuje zegarowy kierunek jej ruchu.<\/p>\n 4. Dodatkowo pozycj\u0119 oznaczamy trasuj\u0105c wszystkie drogi przecinaj\u0105ce kraw\u0119dzie z mr\u00f3wkami, czyli zaczerwieniamy je i stawiamy strza\u0142ki okre\u015blaj\u0105ce ich kierunek\u00a0– zawsze z prawa na lewo z punktu widzenia id\u0105cej mr\u00f3wki.<\/p>\n 5. Z ka\u017cdej stolicy wychodzi dok\u0142adnie jedna trasowana droga wiod\u0105ca do s\u0105siedniej stolicy, zatem niekt\u00f3re z tych dr\u00f3g b\u0119d\u0105 w ka\u017cdej pozycji tworzy\u0107 obwodnice\u00a0– jednokierunkowe trasy okr\u0119\u017cne. 6. Wybieramy obwodnic\u0119, wewn\u0105trz kt\u00f3rej nie ma innej obwodnicy (w nast\u0119pstwie ruch\u00f3w w jej wn\u0119trzu mo\u017ce pojawi\u0107 si\u0119 nowa obwodnica, w\u00f3wczas na ni\u0105 si\u0119 przeniesiemy)\u00a0– oznaczona czerwon\u0105 przerywan\u0105 lini\u0105.<\/p>\n Obwodnica zmienia kszta\u0142t i „zacie\u015bnia si\u0119” po ka\u017cdym mo\u017cliwym do wykonania (nie prowadz\u0105cym do spotkania) ruchu dowolnej znajduj\u0105cej si\u0119 na niej mr\u00f3wki. Na przyk\u0142ad, po ruchu mr\u00f3wki M zamiast drogi BA pojawi si\u0119 BC, za\u015b z punktu C ci\u0105g dr\u00f3g dotrze w punkcie D do dotychczasowej obwodnicy, kt\u00f3ra tym samym zmniejszy si\u0119.<\/p>\n W ten spos\u00f3b w nast\u0119pstwie ruch\u00f3w mr\u00f3wek „obwodnicowych” kolejne obwodnice otacza\u0107 b\u0119d\u0105 coraz mniejsz\u0105 liczb\u0119 kraw\u0119dzi z mr\u00f3wkami, a\u017c liczba ta b\u0119dzie tak ma\u0142a, \u017ce spotkanie mr\u00f3wek oka\u017ce si\u0119 nieuniknione, co jest sprzeczne z przyj\u0119tym za\u0142o\u017ceniem.<\/p>\n","protected":false},"excerpt":{"rendered":" We wpisie z 19 marca zamie\u015bci\u0142em poni\u017csze zadanie. Na wielo\u015bcianie wypuk\u0142ym jest tyle mr\u00f3wek, co \u015bcian. Ka\u017cda \u015bciana nale\u017cy do jednej mr\u00f3wki i ka\u017cda z nich ca\u0142y czas w\u0119druje po kraw\u0119dzi wok\u00f3\u0142 swojej \u015bciany zgodnie z ruchem wskaz\u00f3wek zegara. W ci\u0105gu godziny ka\u017cda mr\u00f3wka przemieszcza si\u0119 co najmniej o 1 milimetr. Nale\u017cy dowie\u015b\u0107, \u017ce po […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/193"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=193"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/193\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nLiczba pozycji jest sko\u0144czona, wi\u0119c b\u0119d\u0105 si\u0119 one powtarza\u0107, zatem ci\u0105g ruch\u00f3w bez spotka\u0144 mo\u017cna uzna\u0107 za cykliczny. Inaczej m\u00f3wi\u0105c: wychodz\u0105c od jakiej\u015b pozycji mo\u017cna powr\u00f3ci\u0107 do niej po zaliczeniu pewnej liczby innych pozycji.<\/p>\n![\"Dow_0.JPG\"](\"http:\/\/penszko.blog.polityka.pl\/wp-content\/uploads\/2008\/Dow_0.JPG\" "\\"Dow_0.JPG\\"")
\u00a0<\/p>\n![\"Dow_1.JPG\"](\"http:\/\/penszko.blog.polityka.pl\/wp-content\/uploads\/2008\/Dow_1.JPG\" "\\"Dow_1.JPG\\"")
\u00a0<\/p>\n
\nKa\u017cda obwodnica dzieli powierzchni\u0119 wielo\u015bcianu na dwie cz\u0119\u015bci. T\u0119, kt\u00f3r\u0105 obwodnica okr\u0105\u017ca w kierunku zgodnym z ruchem wskaz\u00f3wek zegara, nazwiemy cz\u0119\u015bci\u0105 wewn\u0119trzn\u0105\u00a0– do niej kieruj\u0105 si\u0119 wszystkie znajduj\u0105ce si\u0119 na obwodnicy mr\u00f3wki-groty, kt\u00f3re mog\u0105 wykona\u0107 ruch.<\/p>\n![\"Dow_2.JPG\"](\"http:\/\/penszko.blog.polityka.pl\/wp-content\/uploads\/2008\/Dow_2.JPG\" "\\"Dow_2.JPG\\"")
\u00a0<\/p>\n![\"Dow_3.jpg\"](\"http:\/\/penszko.blog.polityka.pl\/wp-content\/uploads\/2008\/Dow_3.jpg\" "\\"Dow_3.jpg\\"")
\u00a0<\/p>\n