MetaMath '25

U nastavku donosim svoj interni tijek rješavanja ovog problema prilikom prvog susreta s Fikom i njegovim mačjim problemima. Pisat ću u prvom licu jednine, što je nekarakteristično za matematički stil, u kojem se uobičajeno piše u prvom licu množine i ponekad u pasivnom obliku (\href{https://math.stackexchange.com/questions/604277/why-are-proofs-written-in-first-person-plural-were-they-ever-written-differentl}{link}). Ovim želim naglasiti suštinu autorskog procesa tijekom rješavanja matematičkog problema. Svako rješenje koje stvaramo malo je autorsko djelo. Izuzetno je korisno da prije čitanja sljedećeg monolog-rješenja \textbf{sam/a utrošiš neko vrijeme na pokušaj rješavanja ovog problema}. Uzmi si vremena, rješavaj opušteno, istraži razne smjerove razmišljanja i isprobaj razne pristupe. Ovaj tjedan neće biti previše zadataka, upravo zato da bi se kvalitetno mogao/la posvetiti svakom postavljenom problemu i izvući maksimalnu korist iz postupka rješavanja. With that said, započnimo naše ,,putovanje u središte problema'', kako bi neki glasoviti autori to sročili. \begin{center} \includegraphics[scale=0.6]{learning-prepositions-help-cat-box-600nw-1897890814.webp} \end{center} Pokušat ću pratiti Polyine korake, opisane u zadatku \href{https://www.skoljka.org/metamath25/task/4078/}{Polya - teorija}, pa da vidimo gdje će me to odvesti. \textbf{Korak 1: Razumijevanje problema.} Nema druge, ako mislimo riješiti problem, prvo ga moramo razumjeti. Inače bismo mogli rješavati krivi problem ili pak riješiti dani problem, a ne biti svjesni toga :D Prva stvar koju ti preporučam da napraviš na početku rješavanja svakog problema jest da ga ... \textbf{prepišeš}! Da, dobro si čuo/la: uzmeš dobri stari (zapravo, radije novi) papir i dobru staru (može i to novo) naoštrenu olovku ili napunjenu tehničku (koje već imaš spremne, jel, khm, dakako) i prepišeš tekst zadatka \emph{riječ po riječ, slovo po slovo}. Iako znam da ovo izgleda kao potpuni gutbitak vremena, pomaže nam na najmanje dva načina: dajemo si vremena da još jednom ,,upijemo'' zadatak svojim tempom te nam omogućuje da se potpuno fokusiramo na rješavanje problema, a ne ni na jednu od $103$ druge stvari koje bismo mogli sada raditi. I nemoj samo prepisivati: razmišljaj o problemu, stvaraj si mentalnu sliku o njemu i pobrini se da sve razumiješ. Dakle, evo za početak tekst zadatka još jednom, u mom krasopisu: \begin{center} \includegraphics[scale=0.6]{20250921_220003.jpg} \end{center} Možda si tijekom prepisivanja nacrtao/la i koju sličicu, recimo neki raspored kutija raznih visina, ili ilustraciju Fikovih dozvoljenih skokova. Možda i samog Fika, što je dobra vježba za sat likovnog, eto interdisciplinarnosti na djelu :) Što nas sad može zanimati je pitanje: kako mogu preformulirati dani problem, na način kako bih ga ja napisao? Meni osobno recimo pada na pamet da malo formaliziramo stvar i uvedemo pojmove \emph{dozvoljenog skoka} i \emph{dobrog rasporeda kutija}. Čini mi se da bi to moglo biti korisno dalje u pisanju rješenja. Tekst zadatka bi onda glasio ovako: U prostoriji se nalazi $10$ kutija visine $1$, $2$, $3$, $\dots$, $10$ koje treba nekim poretkom smjestiti uza zid. Mačak Fiko skače po kutijama počevši s prve kutije u nizu. \emph{Dozvoljeni skok} za Fika je sljedeći: on može skočiti s jedne kutije na sljedeću u nizu ako je sljedeća kutija niža (nije bitno koliko) od one na kojoj se nalazi ili je najviše za $1$ viša od one na kojoj se trenutno nalazi. Raspored kutija zovemo \emph{dobrim} ako Fiko može krenuti s prve kutije u nizu i skočiti redom na svaku iduću kutiju, koristeći pritom samo dozvoljene skokove. Pitanje je sada: koliko postoji dobrih rasporeda kutija? Istina, s ovim nismo ništa bliže rješenju problema, ali ne brinemo se još oko toga. Za sada se samo bavimo razumijevanjem samog problema. Primjetimo ipak kako nakon ove male preformulacije stil problema postaje ,,ozbiljniji'', sličniji nečemu s čime bismo se susreli na nekom ,,ozbiljnom'' natjecanju. Sada bismo već trebali biti u poziciji da odgovorimo na Polyina pitanja vezana uz prvi korak. Evo mojih pokušaja.\\ \textit{Što je nepoznato?} - Broj dobrih rasporeda.\\ \textit{Što su poznati podaci} - Broj i visina kutija, činjenica da ih slažemo jednu do druge nekim redom i pojmovi Fikovog dozvoljenog skoka i dobrog rasporeda kutija.\\ \textit{Jesu li zadani uvjeti dovoljni da se odredi nepoznato?} - Da. Svakako nisu kontradiktorni: trivijalni raspored kutija po rastućoj visini ($1$, $2$, $\ldots$, $10$) je očito jedan dobar raspored. Nadalje, za svaki mogući raspored kutija jednoznačno možemo odrediti je li dobar ili ne. Stoga smo u poziciji da od svih mogućih rasporeda kutija odredimo one dobre i prebrojimo koliko ih je. Toliko o razumijevanju problema. Napokon, okrećem se pokušajima rješavanja. \textbf{Korak 2: Smišljanje plana.} OK, znači zanimaju nas dobri \emph{rasporedi}. Jedan raspored može se ustvari shvatiti kao \emph{permutacija} skupa brojeva $\{1, 2, \dots, 10\}$, pod uvjetom da kutije nazovemo redom brojevima $1$, $2$, $\dots$, $10$. Dodatno, učinimo to na prirodan način: neka je kutija broj $1$ visine $1$, kutija broj $2$ visine $2$, itd. do kutije broj $10$. I da, permutacija nije ništa drugo nego fancy naziv za uređeni (=,,u redu'') raspored nekih objekata. Sad se pitamo koliko uopće postoji permutacija skupa $\{1, 2, \dots, 10\}$. Odgovor na ovo pitanje lijepo je objašnjen \href{https://www.skoljka.org/folder/600/vekijeva-vesela-vjezbenica/predavanja-za-prve-razrede/prebrojavanja/}{u ovom predavanju}. Dakle, ukupno postoji $10!$ različitih permutacija, što je blago rečeno nezanemariv broj. Ovime smo ograničili broj dobrih permutacija na raspon $1$ - $10!$. Nije nešto, ali tek je početak. I barem smo uvjereni da ćemo ovaj zadatak teško riješiti ,,na prste''. Mogu li za početak nekako \textbf{pojednostaviti} problem? (Side note: ne mogu dovoljno naglasiti važnost postavljanja ovog pitanja!) Svakako, pa maloprije smo rješavali pojednostavljenu varijantu ovog problema, sa samo $3$ kutije! Krećem i ja tim putem. Označimo dakle broj kutija s $n$.\\ Za $n=1$, zadatak praktički ne postoji: jedina moguća permutacija je trivijalno dobra. Za $n=2$, problem ostaje trivijalan, ali počinju bar neke kombinacije: obje moguće permutacije $(1, 2)$ i $(2, 1)$ su dobre. Za $n=3$, od mogućih $6$ permutacija, vidim da $4$ čine dobar raspored: $(1, 2, 3)$, $(2, 3, 1)$, $(3, 1, 2)$, $(3, 2, 1)$. Za $n=4$, već postoji $4!=24$ moguće permutacije. Od toga, sljedeće su dobre: $(1, 2, 3, 4)$, $(2, 3, 4, 1)$, $(3, 4, 1, 2)$, $(3, 4, 2, 1)$, $(4, 1, 2, 3)$, $(4, 2, 3, 1)$, $(4, 3, 1, 2)$, $(4, 3, 2, 1)$; dakle $8$ ukupno. Uvjeri se sam/a da su napisani odgovori doista ispravni - nikad ne vjeruj slijepo autoru (pa čak ni meni)! Hm hm, $1$, $2$, $4$, $8$ $\longrightarrow$ nešto tu smrdi, i to na potencije broja $2$! Zašto, kako?! Dobro, da se ne pravim lud previše, priznajem da sam između zadnjih redaka shvatio što se događa i došao do ideje rješenja. Idem sad probati opisati taj proces. Gledam što se događa na prijelazu između $3$ i $4$ kutije. Prva opservacija je sljedeća: jedina novost između tri i četiri kutije je (očito) četvrta kutija visine $4$. Prve tri kutije iz nekog dobrog rasporeda moraju ostati u istom međusobnom položaju kao i dok su bile samo tri, jer se dodavanjem četvrte ništa nije promijenilo ,,što se njih tiče''. Dakle, možemo početi od $4$ dobra rasporeda koja imamo za slučaj s $3$ kutije i pitati se gdje možemo ,,umetnuti" četvrtu kutiju. Uzmem recimo dobru permutaciju $(1, 2, 3)$. Kutiju visine $4$ mogu staviti na početak, jer Fiko sa svojih $9$ mačjih života može podnijeti skok prema dolje s bilo koje visine. Gdje još? Ne mogu iza $1$, to mu je previsoko. Isto tako i iza $2$. Jedino može doći na kraj iza $3$. Time od jednog dobrog rasporeda za $n=3$ dobijem dva dobra rasporeda za $n=4$. Gledam sada sljedeću dobru permutaciju $(2, 3, 1)$. Ponovno, kutiju $4$ mogu staviti na početak, a osim toga opet jedino iza kutije $3$. Primjećujem da nakon što je umetnem tako između $3$ i $1$, nisam ništa ,,pokvario'', ponovno jer su dozvoljeni skokovi prema dolje s bilo koje visine. Dakle, i u ovom slučaju od \textbf{jedne} dobre permutacije za $n=3$ dobivam \textbf{dvije} dobre permutacije za $n=4$. Pattern emerges, ilitiga: \textbf{AHA!} Imam ga! Slutimo da će se broj dobrih permutacija duplo povećavati sa svakim povećanjem broja kutija $n$ za jedan. Plan je smišljen, pokušajmo ga provesti! \textbf{Korak 3: Provedba plana.} Još je Arhimed rekao: ,,Daj mi dobar plan i riješit ću ti problem.'' Ili nešto tako ... Da vidimo je li bio u pravu. Označimo s $D_n$ broj dobrih rasporeda s $n$ kutija. Želimo odrediti broj dobrih rasporeda $D_{n+1}$ za $n+1$ kutiju, u ovisnosti o $D_n$. Za sada znamo $D_1 = 1$, $D_2 = 2$, $D_3 = 4$ i $D_4 = 8$. Uzmimo dakle proizvoljan dobar raspored (bilo koji od $D_n$ mogućih) za $n$ kutija. Označimo ga s $(x_1, x_2, \dots, x_n)$, gdje su jasno $x_1, x_2, \dots, x_n$ međusobno različiti elementi skupa $\{ 1, 2, \dots, n \}$ koji predstavljaju visinu $n$-te kutije u ovom rasporedu. Sad se pitamo kako od ovog rasporeda možemo napraviti dobar raspored za $n+1$ kutiju. Kao što smo prije zaključili, jedina stvar koju moramo napraviti je vidjeti gdje možemo ,,ubaciti'' kutiju $n+1$. Ponovno kao prije, vidimo da je sigurno možemo ubaciti na sami početak niza. Time dobivamo dobar raspored $(n+1, x_1, x_2, \dots, x_n)$ za $n+1$ kutiju. Pitamo se gdje još možemo ubaciti kutiju $n+1$. Sad neće biti na početku, što znači da će biti neka kutija ispred nje. To je ključ: da bi Fiko došao na kutiju $n+1$ dozvoljenim skokom, \emph{jedina mogućnost} je da prije nje bude na kutiji $n$, jer je to jedina manja s koje se može popeti na $n+1$, a više kutije od $n+1$ nema. Dakle, ako je $k$ takav da $x_k=n$ (dakle, kutija visine $n$ je na poziciji broj $k$), još jedan dobar raspored za $n+1$ kutiju je $(x_1, x_2, \dots, x_k, n+1, x_{k+1}, \dots, x_n)$. Zaključak je tu: od jednog, proizvoljnog, dobrog rasporeda za $n$ kutija, dobivamo točno dva dobra rasporeda za $n+1$ kutiju. Možemo li zaključiti da vrijedi $D_{n+1} = 2 \cdot D_n$? Skoro - ostaje dokazati da svi dobri rasporedi za $n+1$ kutiju moraju nastati upravo na ovaj način. Ali to nije teško i možda smo implicitno već dokazali u prijašnjoj raspravi, pa ti ostavljam za zadaću (uputa: uzmemo proizvoljni dobar raspored za $n+1$ kutiju i ,,izbrišemo'' kutiju $n+1$: sada treba dokazati da time dobijemo dobar raspored za $n$ kutija - time dokazujemo da svaki dobar raspored za $n+1$ kutiju nastaje iz nekog dobrog rasporeda za $n$ kutija na opisani način). Sada, konačno je dokazano $D_{n+1} = 2 \cdot D_n$. Krasno! Ostaje riješiti ovu \href{https://hrcak.srce.hr/file/266709}{rekurziju}. Rekurzije znaju biti zeznute, upravo zato što rekurzije znaju biti zeznute. Ali srećom, ova naša je ,,pitoma''. Početna vrijednost je $D_1 = 1$. Za $D_n$ lako možemo razmotati: $$ D_n = 2 \cdot D_{n-1} = 2 \cdot 2 \cdot D_{n-2} = \dotsb = \underbrace{2 \cdot 2 \dotsb 2}_{n -1 \text{ puta}} \cdot D_1 = 2^{n-1} \cdot 1 = 2^{n-1}.$$ Voila, $D_n=2^{n-1}$, za sve $n \in \mathbb{N}$ (uklapa se čak i za polaznu vrijednost $n=1$). Riješeno!!! \textbf{Korak 4: Osvrt.} Često, prečesto zanemarivan korak. Priznajem, i ja sam u tvojim godinama premalo vremena trošio na naknadno razmatranje rjiešenog zadatka. Ali i kratki osvrt može biti jako koristan. Samo prođi još jednom kroz sve korake svog konačnog rješenja i uvjeri se da sve razumiješ i da ćeš moći bez poteškoća riješiti slične probleme u budućnosti. Time prvo izbjegvaš one male glupe greške napravljene u žaru rješavanja te dodatno osnažuješ svoje znanje o temi zadatka. Kad prođem kratko kroz rješenje, prvo mi se sviđa uvođenje pojmova dozvoljenog skoka i posebice dobrog rasporeda, jer su mi olakšali komunikaciju i razmišljanje o problemu. Dalje, potvrđujem činjenicu da je promatranje jednostavnijih problema često put prema rješavanju onih problema koji se ispočetka čine prekomplicirani. Također, svjedočim još jednom da je rekurzivno ili induktivno razmišljanje jako efektivna matematička metoda, pogotovo u kombinatornim problemima. Evo i još jedna potencijalna skrivena korist od osvrta. Osobno, još i sada kao mentoru (s ograničenim iskustvom) mi još nije uvijek jasno kako se netko dosjeti postaviti ovakav ili sličan zadatak. Mislim da je najbolji način za vježbanje ove vještine upravo osvrt na problem nakon što smo našli rješenje, sada iz perspektive nekoga ,,ravnog zadatku'', a ne više ,,podređenog'' i pod teretom traženja rješenja. Sada se možemo pitati kako je autor uopće došao do ideje za zadatak. Možemo se staviti u njegovu kožu i malo se igrati s uvjetima, pokušati neke izmijeniti, napraviti sličan zadatak i vdjeti kako se rješenje mijenja u ovisnosti o tim parametrima. Recimo, ovaj zadatak je idealan za takve mentalne egzibicije. Što ako kutije nisu visina $1$, $2$, $\dots$, $n$, nego nekih drugih? Što ako promijenimo Fikove sposobnosti skakanja uvis ili dolje? Ili još egzotičnije, što ako postoji više redova kutija, a ne samo jedan, pa pustimo Fika neka može skakati s reda na red? Što ako uključimo i Fikovu braću i sestre koji se isto žele igrati skakanja po kutijama? Samo je nebo granica i tvoja mašta. Predlažem da smisliš jednu varijantu Fikovog problema. Pošalji nam svoje zadatak i možda ga i uvrstimo u MetaMath! Još par napomena u sklopu osvrta na proces rješavanja. Ovaj zadatak je prilično jednostavan i zbog toga smo imali sreću da odmah iz prve postavimo dobru slutnju i krenemo pravim putem prema rješenju. No, sam/a znaš da to nije uvijek slučaj u tijeku rješavanja problema. Često krenemo krivim putem koji ne vodi nužno rješenju, barem ne na najelegantniji način. Recimo, ovdje smo mogli ići brojati dobre rasporede metodama klasičnog prebrojavanja, principom sume i uzastopnog prebrojavanja. Možda je moguće ići i tim putem, ali vjerojatno manje u ,,ravnoj crti'' kao u prikazanom rješenju. U svakom slučaju, isprobaj svaki put koji ti padne na pamet, do neke dubine. Time ćeš stvoriti osjećaj za raspoznavanje dobrog puta od pogrešnog i razviti sposobnost samokritičnosti i samoprocjene. Najvažnije od svega, cijeni i poštuj cjelokupni proces rješavanja, sve uspone i padove, slijepe ulice i stranputice, jer je moguće, dapače vrlo vjerojatno, da ćeš više naučiti iz njih nego od čitanja nečijeg već napisanog rješenja. Dosta filozofiranja više, idemo dalje već jednom na zadatke! :) \emph{Kao rješenje upiši ,,Fiko''.}