Bakteria

W związku z oficjalnym rozpoczęciem sezonu deszczowego, na poprawę humoru proponuję zadanie z legendarnej serii Andrew Stankevich Contest. W treści niby jest coś o bakterii, ale od razu widać, że tak naprawdę chodzi o kanapkę z dżemorem (bez bakterii). Co prawda w rozwiązaniu będziemy potrzebować odrobiny (prostej) analizy, ale w tym wypadku nawet warto.

Zadanie pochodzi z Andrew Stankevich Contest 14, i można je sobie zobaczyć tutaj, gdzie figuruje jako problem B. Treść jest, na pierwszy rzut oka, dość dziwaczna. Dostajemy bowiem dwie funkcje określone na kwadracie [0,1] \times [0,1]. Pierwsza z nich to \alpha x+\beta, a druga to \gamma y+\delta, gdzie 0\leq \alpha,\beta,\gamma,\delta \leq 100. Teraz naszym celem jest podzielenie rzeczonego kwadratu na dwie części używając jednego cięcia tak, aby dla każdej z tych dwóch funkcji całka (z danej funkcji) po lewej części była równa całce (z tej samej funkcji) po prawej części (nazwanie części lewą i prawą jest być może pewnym nadużyciem, nie przejmujmy się tym jednak; nikt nam przecież za to nie odejmie punktów). Co prawda autor zadania wyraźnie starał się uniknąć słowa całka, lecz przecież nie można go za to winić. Aha, w treści jest jeszcze prośba, aby w wypadku nieistnienia takiego cięcia (czyli linii prostej), wypisać trzy zera. Nie jedno, nie dwa, i nie cztery. Od razu powinno to wzbudzić Waszą podejrzliwość: jeśli rzeczywiście może być tak, że żądane cięcie nie istnieje, to pewnie wypadałoby umieścić taki przykład w treści, prawda?

No, a może i nie prawda. W końcu nie można wykluczyć, że autor jest odrobinę złośliwy. Okazuje się jednak, że takie cięcie zawsze istnieje, co w sumie jest dość ciekawe samo w sobie. Co nawet bardziej ciekawe, pokażemy jak je szybko znaleźć.

Może zacznijmy od wyobrażenia sobie, o co w tym wszystkim tak naprawdę chodzi, i gdzie w tym wszystko można znaleźć obiecaną kanapkę z dżemorem. Funkcję f(x,y)=\alpha x+\beta najlepiej wyobrażać sobie w trzech wymiarach, czyli tak jak na poniższej ilustracji.

bakteria1

Podobnie można myśleć o funkcji g(x,y)=\gamma y+\delta.

bakteria2

Teraz można sobie wyobrażać, że ta pierwsza funkcja mówi nam, jaka jest w danym punkcie wysokość kanapki (jakby trochę krzywo ukrojonej), a druga oznacza wysokość warstwy dżemu (OK, dżem może nie jest tutaj najlepszym przykładem, bo trochę trudno wytłumaczyć czemu jego wysokość nie jest wszędzie taka sama; powiedzmy, że tak po prostu wyszło; lepszy byłby krzywo ukrojony plaster szynki, niestety nie pozwala na to budżet tego wpisu). Chcemy przeciąć kanapkę na dwie części tak, aby nikt nie czuł się poszkodowany.

Powiedzmy, że szukana prosta to y=ax+b. Uważny Czytelnik od razu zauważy, że takim założeniem od razu blokujemy sobie możliwość wybrania prostej pionowej. Taka prosta nie może jednak być rozwiązaniem, co udowodnimy sobie za parę minut, a na razie po prostu uwierzmy. Można więc myśleć, że mamy dwa stopnie swobody: możemy zupełnie niezależnie ustalić a i b. No, to załóżmy sobie, że znamy a, i chcielibyśmy tylko wybrać prawidłowe b. Jak dokonać takiego wyczynu?

Wyobraźmy sobie, jak zmienia się sytuacja dla coraz większych wartości b. Czyli zacznijmy od b=-\infty i przesuwajmy naszą prostą w górę aż do b=\infty. No, takie przesuwanie może trochę zająć, ale nic to. Nie takie rzeczy już robiliśmy! Łatwo zauważyć, że dla b=-\infty cały dżem znajduje się po lewej stronie prostej, a zwiększanie b prędzej lub później doprowadzi do sytuacji, w której w całości znajdzie się on po tej drugiej stronie. W tym momencie wygodnie jest zdefiniować sobie funkcję h(b), która dla danej wartości b zwraca różnicę między zawartością dżemu po lewej i po prawej stronie. Mamy h(-\infty)>0 i h(\infty)<0, czyli na pewno istnieje b\in (-\infty,\infty), dla którego h(b)=0!

OK, to "na pewno" być może nie jest takie oczywiste. Po pierwsze pewnym nadużyciem jest pisanie h(\infty) czy h(-\infty). Po drugie, chyba skorzystaliśmy z jakiejś specyficznej własności funkcji h. Wspomniane nadużycie nie jest jednak takie wielkie: wystarczy myśleć, że \infty to po prostu bardzo duża liczba (a, biorąc pod uwagę niski limit na współczynniki podane na wejściu, nawet nie tak bardzo duża). Co do specyficznej własności funkcji h, wystarczy nam, że jest ona ciągła. Tak naprawdę skorzystaliśmy więc z twierdzenia o wartości średniej, czyli nie wydarzyło się nic szczególnie ciekawego.

No i fajnie, ale jak na razie wiemy tylko, że (dla ustalonego a), istnieje b, dla którego h(b)=0. Ale przecież nie znamy a, a co gorsza powyższe rozumowanie nie do końca pomaga w wyznaczeniu takiego b.

Wyznaczenie b tak naprawdę nie jest wielkim problemem. Przede wszystkim, możliwe (choć niewyobrażalnie męczące) jest wyznaczenie wzoru na h(b), no i następnie rozwiązanie odpowiedniego równania. Można też prościej: spróbujmy wyznaczyć b z dokładnością do, powiedzmy, 10^{-10}. Wiemy, że h(-\infty) < 0, gdzie \infty to, powiedzmy, 10^{10}. Mamy więc przedział [x,y], dla którego h(x)  < 0 i h(y) > 0. Teraz wystarczy wybrać z=\frac{x+y}{2} i wyznaczyć h(z). Jeśli h(z) > 0, zastępujemy y przez z. Jeśli zaś h(z) < 0, zastępujemy nim x. W pojedynczym kroku długość aktualnego przedziału spada o połowę, czyli nie potrzeba wielu kroków, aby zwęzić go do 10^{-10}. No, o ile tylko potrafimy policzyć dowolne h(z). Jak się do tego zabrać? Wystarczy scałkować f(x,y) w odpowiedniej części kwadratu [0,1] \times [0,1]. Funkcja f(x,y) jest na tyle prosta, że można sobie wyprowadzić na to wzór.

Wiemy więc już, że mając a możemy efektywnie wyznaczyć b_a, dla którego prosta y=ax+b_a dzieli dżem na dwie części o równej objętości. Pozostaje poradzić sobie z kwestią odpowiedniego wyboru a. Skoro rozwiązaliśmy już kwestię dżemu, celem tego wyboru powinno być podzielenie chleba na dwie równe części za pomocą prostej y=ax+b_a. No, o ile rzeczywiście jest to zawsze możliwe.

Otóż jest. Zdefiniujmy sobie bowiem funkcję h'(a), która dla danej wartości a zwraca różnicę między zawartością chleba po lewej i po prawej stronie prostej y=ax+b_a, no i wyobraźmy sobie sytuację dla a=0. Mamy wtedy b_0=\frac{1}{2}, gdyż dżem jest rozłożony symetrycznie względem płaszczyzny y=\frac{1}{2}. Następnie wyobraźmy sobie, co się dzieje dla coraz mniejszych wartości a. Dość łatwo dojść do wniosku, że skoro wysokość warstwy dżemu jest coraz większa dla coraz większych wartości x, dzieje się mniej więcej to co na poniższym rysunku.

bakteria3

Teraz patrząc na h'(a) i pamiętając, że wysokość warstwy chleba jest coraz większa dla coraz większych wartości y dostajemy, że h'(0) > 0 i h'(-\infty) < 0. Oznacza to, że na pewno istnieje a\in (-\infty,0), dla którego h'(a)=0!

No, prawie. Aby skorzystać z twierdzenia o wartości średniej musimy najpierw upewnić się, że nasza funkcja h' jest ciągła. Jest to o tyle kłopotliwe, że „wewnątrz” jej definicji szukamy zero innej funkcji h. Powiedzmy, że nie będziemy drążyli tej lekko niewygodnej kwestii, i zamiast tego po prostu wyobrazimy sobie, co się dzieje przy minimalnej zmianie a. Powinno to wystarczyć, żeby uwierzyć w ciągłość h.

Skoro wiemy już, że istnieje a, dla którego h'(a)=0, możemy skorzystać z opisanej wyżej metody, aby wyliczyć je z dokładnością do, powiedzmy, 10^{-10}. Musimy tylko umieć policzyć dowolne h'(a), czyli tak naprawdę scałkować g(x,y) w odpowiedniej części kwadratu [0,1] \times [0,1] (dokładniej: na prawo od y=ax+b_a). Niczym nie różni się to od całkowania f(x,y).

To w zasadzie daje rozwiązanie całego zadania: wyliczamy a, następnie wyznaczamy odpowiadające mu b_a, i wypisujemy prostą y=ax+b_a. Wiemy, że dzieli ona dżem na dwie równe (co do objętości) części, gdyż tak właśnie zdefiniowaliśmy b_a. Podobnie, wiemy, że dzieli ona chleb na dwie równe części, gdyż taki był warunek nałożony na a.

Można by się zastanawiać, dlaczego funkcje f(x,y) i g(x,y) były takie a nie inne. Czy dlatego, żeby zadanie zawsze miało rozwiązanie? Okazuje się, że nie: sztuczka, której użyliśmy, w zasadzie działa dla dowolnych innych (przyzwoitych) funkcji. Co nawet lepsze, uogólnia się na więcej wymiarów! Zainteresowanych odsyłam tutaj.

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s