Polish version    English version  
  XVIII OI 2010/2011


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
Terminarz
Zadania
II Etap
Przepisy
Wyniki I etapu
Wyniki II etapu
Dla zawodników
Przydatne zasoby
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
W trakcie gry rysujemy na planszy kreski, z których każda łączy 5 kropek. Każda
taka kreska składa sie z 4-ech elementarnych odcinków łączacych sąsiednie kropki.
Każda kropka może być końcem co najwyzej 8-miu takich elementarnych odcinków.
                 \  |  /
                -- 0 --
                 /  |  \

Liczbą oddechów danej kropki będę nazywał ilość nie wykorzystanych jeszcze
możliwości dorysowania do niej odcinków elementarnych.

Na początku gry każda kropka ma 8 oddechów, a ilość kropek wynosi 36 (3*3*4).

Wykonanie każdego ruchu polega na postawieniu 1 nowej kropki na planszy i
połączeniu 5-ciu kropek kreską. Postawienie kreski wymaga zużycia 8-miu oddechów
(3*2 w środku kreski i 2 na końcach).

  o--o--o--o--o

Jednocześnie dodanie nowej kropki dodaje na planszę 8 nowych oddechów. Zatem ilość
oddechów na planszy pozostaje stała i wynosi 8*36=288 w ciągu całej gry.

Intuicyjnie rzecz biorąc oddechy są niezbędne do tworzenia "brzegu" narysowanej
figury z kropek - figura taka nie może zatem być zbyt duża.

Przez prostą kratową poziomą lub pionową będę rozmumiał prostą poziomą lub pionową
przebiegającą poprzez istniejące kropki lub miejsca na nie. W dowolnym momencie
gry opiszmy na jej konfiguracji najmniejszy prostokąt taki, że jego boki
przebiegają równolegle do prostych kratowych. Niech ponadto każdy bok leży
dokładnie pośrodku dwóch sąsiednich prostych kratowych. Boki tego prostokąta można
wówczas wyskalować w kropkach.  Przyjmijmy na początek, że konfiguracja gry
jest spójna tj. nie można jej przedzielić prostą kratową poziomą 
lub pionową nie zawierającą kropki. Prosta bedąca symetralną dowolnego jednostkowego
odcinka boku jest prostą kratową tj. taką, na której leżą kropki. Posuwając się po
takiej symetralnej od środka odcinka jednostkowego w kierunku wnętrza prostokąta
musimy (zgodnie z założeniem spójności konfiguracji) napotkać w pewnym momecie
pierwszą kropkę należącą do naszej konfiguracji. Ponieważ jest to pierwsza
napotkana kropka, to musi miec ona wolny oddech w kierunku, z którego przyszliśmy.

Powtarzając to postępowanie dla każdego jednostkowego odcinka obwodu bądź będziemy
natrafiać za każdym razem na różne kropki chyba, że jakaś kropka się powtórzy, ale
wtedy przyjdziemy do niej z różnych kierunków, zatem trafimy na różne jej oddechy.
Każdemu jednostkowemu odcinkowi opisanego prostokąta przyporząkowujemy zatem
wzajemnie jednoznacznie pewien wolny oddech. A więc długość obwodu takiego
opisanego prostokąta nie może przekroczyć 288 jednostek - ilość kropek w grze jest
zatem ograniczona.

Rozważmy teraz przypadek, w którym konfiguracje gry w momencie opisywania
prostokąta nie jest spójna w sensie zdefiniowanym powyżej. Usuńmy zatam z planszy
wszystkie kratowe proste rozspójniające. Otrzymamy w ten sposób poprawną rozgrykę
na zmodyfikowanej planszy. Zatem i w tym przypadku ilość kropek jest ograniczona
poprzez wpisanie ich w prostokąt o obwodzie ograniczonym do 288 jednostek.
                                                                    c.n.d.

Najwiecej kropek możemy w ten sposób uzyskać gdy prostokąt jest kwadratem o boku
288:4=72 jednostki. Nie jest to jednak zbyt dobre ograniczenie, choćby dlatego, że
uwzględnie tylko pionowe i poziome oddechy brzegowe konfiguracji a pomija oddechy
"po przekątnych". Takie rozumowanie wydaje się jednak trudniejsze do
przeprowadzenia. Skądinąd należy oczekiwać, że największa ilość kropek, jakie mogą
się pojawić w grze powinna silnie zależeć od konfiguracji startowej. Trudno
powiedzieć jak możnaby taką informację wprowadzić do oszacowania.

Rozumując nieprecyzyjnie nt. oddechów brzegu po przekątnych możemy wyobrazić sobie
najliczniejszą konfigurację w postaci ośmiokąta, którego każdy punkt brzegu
(pomijając wierzchołki) ma 3 oddechy. Wychodzi wówczas ok. 11 kropek na bok, co
dawałoby wpisanie w kwadrat o boku 33 jednostek z obciętymi rogami. Jest to mniej
więcej 1000 ruchów, najprawdopodobniej jednak wciąż o wiele za dużo.

                                                                      Marek
Warpechowski.