Jak skąpy matematyk firany zawieszał

Życie jest matematyką, matematyka jest życiem. Często nie zdajemy sobie sprawy z tego, że codzienne czynności mają w tle całkiem poważny aparat matematyczny. Zapraszam do lektury małej próbki. Aktorami dzisiejszego spektaklu są rekurencje liniowe.

Są ludzie skąpi, są ludzie szczodrzy. Każdemu z nas podoba się chyba perspektywa pomnożenia własnego kapitału. Moja córka (obecnie 10-letnia, jest w III klasie szkoły podstawowej) na kółku matematycznym otrzymała następujące zadanie:

Czarodziej rzekł do skąpca: ile razy przejdziesz przez kładkę i wrzucisz do strumienia cztery talary, to podwoi się kwota, która ci pozostanie. Skąpiec przeszedł przez kładkę trzy razy i został bez pieniędzy. Ile miał początkowo?

Oczywiście rozwiązała je metodą prób i błędów. Natomiast tata–matematyk od razu dostrzegł coś głębszego.

Niech skąpiec dysponuje przed rozpoczęciem przechodzenia przez kładkę kwotą $a_0=a$ talarów. Niech $a_n$ oznacza kwotę, jaką będzie dysponował po $n$ przejściach przez kładkę. Przypuśćmy, że dokonał już $n$ przejść. Przed kolejnym, o numerze $n+1$, wrzuca do strumienia $4$ talary, więc zostaje mu kwota $a_n-4$ talarów. Po przejściu o numerze $n+1$ jej wartość podwaja się, dlatego mamy $a_{n+1}=2(a_n-4)$.

Powyższa analiza pokazuje nam, że potrzeba wyznaczenia kwot, jakimi skąpiec dysponuje po kolejnych przejściach, doprowadza nas do jednorodnej rekurencji liniowej pierwszego rzędu (proszę nie przerazić się tą nazwą):\[\begin{cases}a_0=a,&\\ a_{n+1}=2(a_n-4)&\text{dla }n=0,1,2,\dots\,.\end{cases}\]

Ponieważ za cel tego artykułu wyznaczyłem sobie pokazanie związków problemów życia codziennego z matematyką, rozwiązując tę rekurencję nie będę wchodził w szczegóły i oprę się bardziej na intuicji.

Wprowadźmy więc liczbę $b_n=a_n-8$. Dlatego \[b_{n+1}=a_{n+1}-8=2(a_n-4)-8=2(a_n-8)=2b_n.\] Dochodzimy więc do rekurencji\[\begin{cases}b_0=a-8,&\\ b_{n+1}=2b_n&\text{dla }n=0,1,2,\dots\,,\end{cases}\]która jest znacznie prostsza do rozwiązania. Istotnie,\begin{align*}b_0&=a-8\,,\\b_1&=2b_0=2(a-8)\,,\\b_2&=2b_1=2\cdot 2(a-8)=2^2(a-8)\,,\\b_3&=2b_2=2\cdot 2^2(a-8)=2^3(a-8)\,,\\\vdots&\\b_{n}&=2^n(a-8)\,.\end{align*} Teraz już, wobec $b_n=a_n-8$, łatwo wyliczamy $a_n=b_n+8$, skąd\[a_n=2^n(a-8)+8\,.\]

Zanalizujmy powyższy wzór.

1. Jeśli na początku skąpiec ma $a=8$ talarów, to zawsze $a_n=8$ i ta kwota nie będzie się ani zmniejszać, ani zwiększać.
2. Jeśli $a>8$, to $a-8>0$ i $a_n>8$. Co więcej, $a_{n+1}-a_n=2^n(a-8)>0$, więc $a_{n+1}>a_n$ i wraz z każdym kolejnym przejściem przez kładkę skąpiec zwiększa swój kapitał (mniej więcej dwukrotnie).
3. Jeśli jednak $0\xle a<8$, to $a-8<0$ i $a_{n+1}<a_n$ (porównajmy to z rachunkami z poprzedniego punktu) i wraz z każdym kolejnym przejściem przez kładkę skąpcowi ubywa pieniędzy. Będzie tak do czasu, aż braknie mu środków na opłacenie następnego przejścia, a to zdarzy się na pewno.

Wróćmy teraz do naszego zadania. Skoro po trzech przejściach przez kładkę skąpiec został bez pieniędzy, to $a_3=0$, co prowadzi nas do równania\[0=a_3=2^3(a-8)+8\,,\]skąd $a=7$. Dlatego skąpiec miał początkowo $7$ talarów. Dał się skusić perspektywie szybkiego pomnożenia kapitału, a wyszedł na tym tak jak Zabłocki na mydle.

Szkoda, że nie wysupłał z kieszeni dodatkowych dwóch talarów. Wtedy po iluś przejściach doszedłby do pokaźnej fortuny. Dla $a=9$ mamy bowiem $a_n=2^n+8$ i po $n=10$ przejściach przez kładkę skąpiec miałby do dyspozycji aż $2^{10}+8=1032$ talary. Nie mówmy już o następnych przejściach przez kładkę.

Powyższe zadanie sprzedałem koledze, matematykowi Andrzejowi z miasta Łodzi. Andrzej zrewanżował się taką historyjką:

Mi takie rekurencje zawsze kojarzyły się z firanami. Gdy wieszam uprane firanki, to najpierw wieszam końce, a potem chciałbym za każdym razem przyczepiać środkową żabkę do środka firanki. Potem to samo w połówkach, ćwiartkach, itd. Ale do tego musi być dobra liczba żabek.

Matematycy to dziwni ludzie. Nawet przy prozaicznych pracach domowych myślą o swojej ulubienicy (bynajmniej nie mam tu na myśli żony).

Aby zakończyć wieszanie firanek po pierwszym kroku, potrzeba nam tylko $a_1=2$ żabek. Ale życie jest ciężkie, trzeba pracować dalej. Przyjmijmy więc, że wykonaliśmy już $n$ kroków przypinając $a_n$ żabek. Tak jak pomiędzy pięcioma rozpostartymi palcami dłoni mamy cztery przerwy, tak pomiędzy $a_n$ przypiętymi żabkami mamy $a_n-1$ przerw, a w każdą z nich musimy przypiąć po jednej żabce. Dlatego potrzeba nam\[a_{n+1}=a_n+(a_n-1)=2a_n-1\]żabek. Dochodzimy do rekurencji\[\begin{cases}a_1=2,&\\ a_{n+1}=2a_n-1&\text{dla }n=1,2,\dots\,.\end{cases}\]Wprowadzając $b_n=a_n-1$ mamy $b_1=1$ oraz $b_{n+1}=2b_n$. Rozumując tak samo jak w zadaniu o skąpcu otrzymujemy $b^n=2^{n-1}$ i ostatecznie na przypięcie firanki w $n$ krokach potrzebujemy\[a_n=2^{n-1}+1\]żabek. Proponuję Czytelnikom sprawdzić czy liczby żabek uzyskane z tego wzoru zgadzają się z liczbami otrzymanymi przez proste wyliczenie dla niewielkiej liczby kroków. Np. aby przypiąć firankę w dwóch krokach potrzebujemy $3$ żabek, w $3$ krokach potrzebujemy $5$ żabek itd.

Gdy staną przed nami kolejne domowe porządki, kupując nowe żabki na pewno przypomnimy sobie o tych wyliczeniach. A może w drodze do sklepu trzeba będzie przejść przez kładkę? Czyż nie jest prawdą, że każdy z nas jest po trosze matematykiem?