|
||||||||||||||||||||||||||||||||
| Teza. Gra jest skończona. Dowód (a) skończoność Wprowadźmy definicję połączenia: każda kropka posiada 8 połączeń, to znaczy może sąsiadować z 8 innymi kropkami tworząc 'krechę'. Powiemy, że połączenie jest wolne, jeśli nie jest wykorzystane jako element krechy. Wprowadźmy definicję kropki brzegowej: kropka jest brzegowa jeżeli nie sąsiaduje z 8 kropkami. W chwili początkowej mamy 36 kropek, a więc 36*8 = 288 wolnych połączeń. Dodanie dowolnej kropki zwiększa liczbę wolnych połączeń o 8. Zauważmy jednak, że postawieniu każdej kropki musi towarzyszyć wytyczenie krechy, zaś każda krecha wykorzystuje 8 połączeń (po jednym od skrajnej kropki i po dwa od środkowych). Wynika stąd, że liczba wolnych połączeń jest stała i wynosi 288. Niech kropki tworzą pewną figurę lub figury. Każda kropka brzegowa figury ma przynajmniej jedno wolne połączenie (istotnie, jeżeli kropka nie ma żadnego połączenia, to musi być otoczona przez 8 innych kropek, więc nie leży na brzegu). Ponieważ liczba wolnych połączeń jest stała, nie może być więcej niż 288 punktów brzegowych. Figura jest ograniczona, zatem gra jest skończona. === (b) granica Figurą o największym polu przy zadanym obwodzie jest koło. Optymalne ułożenie maksymalizujące liczbę kropek w skończonej figurze to ułożenie kropek w kole. Promień tego koła wynosi r=288/(2*pi). Pole koła jest równe/większe od maksymalnej liczby kropek. Pole równe jest pi*r*r czyli supremum liczby kropek wynosi 6601 minus początkowych 36 = 6565. Liczba dostawionych kropek jest równa liczbie krech, stąd liczba 6565 jest także ograniczeniem na liczbę krech. (b') granica - ostrzejsze ograniczenie wprowadźmy definicję zewnętrznej krawędzi figury złożonej z kropek: jest to łamana ograniczająca obszar zajmowany przez kropki, taka, że każda kropka leży wewnątrz lub na boku wielokąta utworzonego przez tę łamaną. wprowadźmy definicję punktu (kropki) z zewnętrznej krawędzi: jest to punkt (kropka) leżący na boku wielokąta (niekoniecznie wierzchołek) liczba wolnych połączeń dla kropki z zewnętrznej krawędzi jest większa lub równa ('kąt'-pi/4)/(pi/4) gdzie 'kąt' jest kątem zewnętrznym (uwaga 1: kiedy kropka leży w wierzchołku; dla pozostałych punktów z zewnętrznej krawędzi 'kąt' = pi) (uwaga 2: równość zachodzi kiedy w sąsiedztwie kropki wewnątrz wielokąta nie ma wakatów) liczba wolnych połączeń dla wszystkich kropek z zewnętrznych krawędzi jest większa lub równa od sumy powyższych wyrażeń czyli od S S = ('kąt1'-pi/4)/(pi/4)+ ... + ('kątN'-pi/4)/(pi/4)= = ('kąt1'+...' 'kątN')/(pi/4) - N gdzie N jest liczbą kropek z zewnętrznych krawędzi. zachodzi: S mniejsze/równe 'liczba wolnych połączeń dla kropek z zewnętrznych krawędzi' mniejsze/równe 'liczba wszystkich wolnych połączeń' mniejsze/równe 288 korzystamy: suma kątów zewnętrznych wieloboku ('kąt1'+...' 'kątN')= pi*(N+2) otrzymujemy warunek na liczbę kropek z zewnętrznych krawędzi S=4*(N+2)-N mniejsze/równe 288; to N < 280/3 maksymalizujemy pole wewnątrz wielokąta, promień koła r=N/(2*pi), pole pi*r*r=(N*N)/(4*pi), supremum liczby kropek wynosi 694 minus początkowych 36 = 658, liczba 658 jest ograniczeniem na liczbę krech. Jerzy Słaby XIV LO im Stanisława Staszica Warszawa === Podziękowania dla Michała Jóźwikowskiego za pomoc w redakcji tekstu. |