Beskonačno mnogo vremena

[Ova priča objavljena je 2016. godine na portalu Kultipraktik kada je ušla u konkurenciju za nagradu Prozak. U međuvremenu je taj portal ugašen pa sam priču odlučio objaviti ovdje. Matematičarima ona može biti zanimljiva i kao jedan pogled na staru raspravu o potencijalnoj i aktualnoj beskonačnosti.]

*

Ovaj zapis govori o slučaju koji još nije riješen, a tiče se zagrobnog života izvjesnog gospodina Slavka M. Taj čovjek na Zemlji nije nikamo žurio: živio je usporeno kao da života ima u izobilju. Govorili su da je lijen, ali to što je studirao deset godina, uvijek kasnio na posao i uzimao stanke za ručak u trajanju od po tri sata, po njegovim riječima nije bilo problematično. Objašnjavao je (onima koji su htjeli slušati njegov polagani govor, isprekidan povremenim odlascima u šetnju) da je njegovo ponašanje odraz svjetonazora koji donosi unutarnji mir i sprječava srčane i mnoge druge bolesti; on je stoga zapravo bio itekako odgovoran čovjek. Poginuo je na autocesti, u pedesetoj godini, u automobilskoj nesreći za koju je očevid utvrdio da joj je glavni uzrok bio prespora vožnja dotičnog Slavka M.

Nakon smrti stigao je u sobicu kamo svi kad-tad pristižu i sjeo za stol s Bogom, vragom i mršavim zapisničarom. Na sastanku je Slavko M. uspio isposlovati da ne ode u pakao na cijelu vječnost, nego samo na konačno mnogo vremena, nakon čega će otići u raj gdje će ostati zauvijek. Nezgodno je bilo što će trajanje vremena provedenog u paklu odrediti vrag, i to potpuno proizvoljno. Slavko će svakako jednom izaći iz pakla, ali kada će se to dogoditi – na vragu je bila odluka.

Slavko M. mirno se zaputio u pakao, znajući da nema tog vremena koje on ne bi mogao provesti u čekanju. On nije bio glup čovjek pa je bio svjestan da će vrag odabrati golem broj godina, veći od svake Slavkove predodžbe. Ali koliko god to vrijeme trajalo, ono je ništavno prema vječnosti koju će Slavko potom provesti u raju; tamo će od izobilja vremena kad-tad zaboraviti da je ikada i bio u paklu.

Slavko M., nažalost, nije znao da vrijeme nadmašuje sve njegovo strpljenje. Možda i nije teško u paklu proboraviti mjesec dana, godinu, pa čak i pet godina. Ali trideset godina, cijeli život, dva života, deset života? Slavku je prekipjelo već nakon pet života – to je već nekoliko stoljeća! – ali nakon toga je dalje čekao tisućljeće, dva tisućljeća, milijun godina, milijardu godina, starost Zemlje, starost svemira – a i to je bila tek sitnica prema onome što ga je čekalo.

Nakon nekoliko tridecilijardi godina Slavko M. rekao je sam sebi da više ovako ne može i odlučio se na žalbu. Nazvao je Boga (morao je čekati čak dvije minute dok se ovaj nije javio) i iznio mu svoj izračun prema kojemu je u paklu proboravio više života nego što ima atoma u svemiru; vrag očito krši dogovor i nikada ga neće pustiti. 

“Hm…” promrmljao je Bog, “tko si ono ti?” 

Slavku je trebalo čak pet minuta objašnjavanja dok se Bog nije napokon sjetio njega i dogovora koji je sklopljen. Tada se javio vrag koji je prisluškivao razgovor.

“Hoću, pustit ću ga, ali još nije došlo vrijeme.”

“Eto vidiš, sve je u redu”, odgovara Bog i poklapa slušalicu. Slavko se pognute glave vratio u pakao psujući Boga i vraga: u beskraju vremena bio je već smislio dugačke psovke čiji je izgovor trajao i po nekoliko tjedana.

Nakon nekog vremena Slavku je postalo jasno da, koliko god eona provede u paklu, ni u jednom trenutku neće znati je li prošlo makar jedan posto od vremena koje mu je vrag predodredio. S tim je mislima ponovno nazvao Boga i rekao mu da je načuo da ga vrag uopće ne namjerava pustiti. Vrag je mirno odgovorio da za to nema nikakvih dokaza. Bogu je čitava stvar postala sumnjiva pa su se u sobici ponovno sastali on, vrag, Slavko M. i mršavi zapisničar. Slavko je Bogu iznio svoju optužnicu.

“Vrag je očito odlučio da me nikada neće pustiti. To je u suprotnosti s dogovorom koji je sklopljen.”

“Slažem se”, odgovara Bog kimajući glavom. Vrag se na to prestane ljuljati na stolcu, uspravi se i htjedne odgovoriti, no Slavko ga preduhitri.

“Ali on će se uvijek izvući! Kad god ga optužim da krši dogovor, vrag će samo odgovoriti da će me pustiti u budućnosti i da je stoga sve po dogovoru. Ne mogu nikada dokazati da me zapravo neće pustiti.”

“Dakle, nema dokaza!” sa smiješkom ustaje vrag. “Ne znam zašto uopće raspravljamo.”

“Zanimljivo”, reče Bog Slavku, ignorirajući vraga koji je ponovno sjeo. “Tvrdiš dakle da je vrag u zavidnoj poziciji: u mogućnosti je istodobno kršiti i ne kršiti dogovor.”

“Upravo tako”, odgovara Slavko, dodajući riječi “napokon si shvatio” sebi u bradu koja je već padala gotovo do poda.

“Molim?” pita Bog.

“Ništa, ništa…”

“Predlažem sljedeće rješenje”, obznani Bog, a zapisničar se prihvati posla. “Vrag mora odmah odlučiti o broju godina koje ćeš provesti u paklu i šapnuti ga meni. Tako ćemo biti sigurni da će dogovor biti ispoštovan.”

Nakon što je vrag teška srca to učinio, Slavko M. sretno se zaputio natrag u pakao, napokon siguran da će kad-tad izaći: njegov je dan izlaska fiksiran i svakim mu je danom bio bliže za točno jedan dan. Ali stvari nisu išle dobro: nemoguće je i zamisliti koliko je Slavko nakon toga čekao. Sve ono vrijeme prije drugog sastanka u sobici jedva da je činilo milijunti dio vremena koje je Slavko potom proveo u paklu ne dočekavši oslobođenje. Shvatio je da ni sada ne zna je li prošlo makar jedan posto, ili čak tisućiti dio, od vremena koje mu je vrag predodredio – štoviše, vjerojatno nije. Nakon što je i njemu, strpljivom i sporom čovjeku, čak septilijun puta prekipjelo, Slavko M. zatražio je novi sastanak s Bogom i vragom u istoj sobici. 

Slavkov je prijedlog bio sljedeći: vrag će ga odmah pustiti i otići će u raj. Ondje će, međutim, provesti konačno mnogo vremena, koliko on sam poželi, nakon čega se vraća u pakao na cijelu vječnost. 

Bio je to neobičan prijedlog, simetričan početnom dogovoru. Vrag je zaključio da je Slavko M. glup čovjek, ali baš iznimno glup čovjek, jer bi po starom dogovoru on u paklu proveo samo konačno mnogo vremena i poslije se ne bi vraćao, a po novome prijedlogu kad-tad će se vratiti u pakao na cijelu vječnost. Vragu je to odgovaralo pa je prijedlog bio prihvaćen, mršavi je zapisničar u spise dodao novu bilješku, a Slavko se zaputio u raj.

A tamo je, naravno, provodio na tisuće puta više vremena nego što je prethodno bio proveo u paklu i nije mu bilo ni na kraj pameti da uskoro izađe. Vrag, budući da ni on nije bio glup, shvatio je da Slavko može u nedogled boraviti u raju na isti način kao što je vrag prethodno odugovlačio njegov boravak u paklu.

“Onaj idiot krši dogovor i neće nikada izaći”, požalio se vrag Bogu.

“Hoću, izaći ću”, iz ležaljke odgovara Slavko M. “Prema dogovoru, moram izaći, ali onda kada sam odlučim.”

Vrag je podivljao. “Ovo je prevara i podvala! On može čitavu vječnost biti u raju i uvijek odgovarati da ipak nije prekršio dogovor jer će, tobože, jednom u budućnosti izaći. Ponovno imamo isti problem.”

“U redu”, odgovara Bog. “Slavko, evo ti komad papira. Bit će velik koliko god poželiš da bude. U skladu s vlastitim prijedlogom, moraš odlučiti koliko ćeš godina ostati u raju – taj broj, naravno, ne smije biti beskonačan – i napisati ga na ovaj papir. Tako ćemo znati da će tom vremenu doći kraj.”

Češkajući obraslu glavu, Slavko je uzeo olovku razmišljajući što će napisati. Nažalost, koji god broj napisao, u usporedbi s vječnošću je ništavan. Također, koji god broj napisao, uvijek može napisati još veći pa je odluka gotovo nemoguća. 

Nakon nekog vremena sine mu ideja i on počne pisati broj: jedan, nula, nula, nula, nula, i tako dalje, dakle: 1000000000000000000000000… Dopisivao je nule i nule, papir se sam od sebe povećavao, a Slavko je nule dopisivao danima, tjednima, mjesecima, godinama, životima. Vrag je shvatio da će ga još jako dugo čekati, ali ipak mirno ode spavati znajući da će nulama na papiru kad-tad doći kraj jer zapisani broj ne smije biti beskonačan.

Slavko M. konačno je došao na svoje: eonima je pisao nule na papiru, ne čineći ništa drugo i pitajući se zašto je u zemaljskom životu radio išta drugo kad je ispunjavanje praznoga papira nulama najlakši, najljepši i najopuštajući posao. Papir se povećavao i dosegnuo širinu četrdeset svemira. Videći kamo to ide, vrag se ponovno javi.

“Onaj vucibatina neće nikada završiti zapisivanje tog prokletog broja godina. Njegov broj je beskonačan, a to je protivno dogovoru.”

“Nije tako!” odgovara Slavko grickajući olovku. “Moj broj je konačan i završit ću s njegovim zapisivanjem jednom u budućnosti.”

Nakon još nonilijun kvintilijuna godina, vrag se u raju pojavio sav crven. 

“Dosta je bilo ovoga cirkusa! Već treći put imamo isti paradoks: onaj smrdljivac krši dogovor pišući beskonačno mnogo znamenaka, a istodobno ga ne krši jer bilo kada može reći da će uskoro završiti. Želim garanciju da će pisanje kad-tad završiti!”

“Opet vas dvojica”, odgovara Bog uz duboki uzdah. “U redu: moramo biti sigurni da će Slavko završiti s pisanjem. Zato nam, Slavko, moraš obznaniti koliko još dana planiraš zapisivati te silne znamenke.”

“Pisat ću ih još mnogo dana”, mirno će Slavko. “Ja volim pisati.”

“Moramo znati točan broj dana”, ponovno će Bog brišući znoj sa čela. “Evo, napiši ga ovdje da to napokon riješimo”, reče i pruži mu novi papir.

Slavko M. uzeo je olovku i zamislio se. Potom je polako počeo pisati broj: jedan, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula…

Everybody’s gangsta until you invert

Prijatelj Bruno Gašperov i ja imali smo raspravu oko jednog YouTube videa, točnije jedne slike koja je u njemu prikazana, a navodno oslikava inverz:

Bruno je primijetio da ovaj meme zapravo ne predstavlja inverz funkcije. Štoviše, on nema nikakve veze s inverzom. Što je na prvoj slici x, a što f? Je li riba x a mačka f()? Onda je f preslikavanje x -> pojedeni x, pa bi inverz trebalo biti nešto što pojedeni x vraća u x. Dakle, na drugoj slici bi trebalo biti nešto što pojedenu ribu pretvara u originalnu. Zapravo je povraćanje inverz, zaključio je Bruno.

Odgovorio sam da on želi prikazati f^{-1}(y), ali da slika prikazuje f^{-1}(x). Bruno je zaključio da to baš i nema smisla. Ako je f nešto što neki objekt pretvara u pojedeni objekt, onda je f^{-1} nešto što pojedeni objekt pretvara u nepojedeni. Domena od f su nepojedeni objekti, kodomena pojedeni. f^{-1} nije definiran na elementu domene, tj. na x. Dakle, f^{-1}(riba) ne postoji.

A čak i ako shvatimo da f^{-1}(riba) postoji, objašnjavao je Bruno, f^{-1} i dalje undo-a čin jedenja. Onda bi f^{-1}(riba) (za nepojedenu ribu) bio neki z koji, kad ga pojedeš, dobiješ nepojedenu ribu. Možda neka riba u ovojnici?

Složio sam se i zaključio da slika zapravo ne opisuje inverz nego reverse, okretanje poretka (mačka jede ribu -> riba jede mačku). Ali onda sam krenuo razmišljati može li se slika ipak nekako shvatiti tako da ima smisla kao inverz, tj. postoji li neko drugo, pametnije tumačenje što je x, a što je f. Pasivno razmišljajući dvadesetak minuta uz zujanje i kavu, nakon nekoliko krivih ideja, našao sam odgovarajuće tumačenje.

Ako je f(x) = onaj tko jede x, onda je na prvoj slici f(riba) = macka. To znači da je f^{-1}(macka) = riba. I onda druga slika prikazuje f^{-1} kao što prva prikazuje f!

Neovisno o dojmu da je takav f malo neprirodan, Bruno je primijetio da je onda čudno da je druga slika, koje prikazuje f^{-1}(x), tj onog koga jede x, vizualizirana na isti način. Bilo bi smislenije da je druga slika identična prvoj. Za drugu sliku treba biti f^{-1}(macka)=riba, što znači da mačka jede ribu, no na slici riba jede mačku. Na toj slici, dakle, “biti pojeden” su vizualizirali kao “jede” što nema baš smisla.

Odgovorio sam da nije tako nelogično ako shvatimo na sljedeći način. Za početak zaboravimo ikakvo jedenje i samo definirajmo f(riba)=macka, dakle f^{-1}(macka)=riba. Dalje uzmimo da slika vizualizira proizvoljnu funkciju na način da stavi x u usta onoga u koga se on preslikava. I sad jednostavno prva slika vizualizira f, a druga f^{-1}. Kao graf! Je li graf funkcije sinus identičan grafu njenog inverza (arcsin)? Ovdje je analogna situacija.

Bruno odgovara da onda relacija jedenja oslikana na slici zapravo samo indicira što je x a što je y, a ne govori ništa o samoj funkciji f. Nisam se baš složio: indiciranje što je x a što y jednoznačno opisuje funkciju. Funkcija nije drugo nego skup parova x, f(x). Slika prikazuje taj skup, točnije, jedan njegov dio. Govori nam o jednom paru x \to y (riba i mačka). Možda ih ima još, možda nema.

Bruno je ponovio prigovor od ranije. Ako je f(riba) = macka, onda je f^{-1}(macka)=riba. f(x) je onaj tko jede x, f^{-1}(x) je onaj koga jede x. Problem je što f(x) i f^{-1}(x) nisu vizualizirane na isti način. Trebale bi biti ista slika!

Odlučio sam se bolje izraziti. Zapravo, nije točno da je f(x) onaj tko jede x. Nego samo na slici vrijedi da je za funkciju na slici f(x) onaj koji jede x. Jedenje je samo vizualizacija neke funkcije koja sama po sebi neme veze s jedenjem. Isto kao što sinus nije “valovit” sam po sebi nego tek kad mu nacrtaš graf u Kartezijevoj ravnini. U tom smislu, f i f^{-1} jesu vizualizirane na isti način i sve je smisleno. Primjerice, “9 jede 3” bila bi analogna slika koja vizualizira kvadriranje, a “3 jede 9” korjenovanje i ništa nije čudno.

Bruno je shvatio. Dakle, imamo neku funkciju koja preslikava x (ribu) u y (mačku), i ta funkcija je (sasvim slučajno) prikazana tako da y jede x (mogli smo prikazati i kao da y pije x ili nešto treće). Jedenje samo indicira što je element domene x (jedeno), a što odgovarajući element kodomene y (jedač). I onda na drugoj slici želimo nacrtati inverz i stavimo obrnuto, da x (riba) jede y (mačku) jer su sad domena i kodomena obrnute. (Kao u slučaju grafova sinusa i arcsinusa.) I u tom smislu relacija jedenja ništa ne govori o samoj funkciji f jer smo funkciju mogli vizualizirati i nekom drugom relacijom, već je proizvoljno odabrana ta relacija da poveže element domene i kodomene. Slika je samo oznaka.

Bruno je onda predložio bolji meme za inverz:

… jer sad ne moramo toliko apstraktno ići, u skladu je sa slikama. f(x) je dobiti na lutriji, f^{-1}(x) potrošiti novac u kockarnici.

Komentirao sam da bih ovaj cijeli razgovor (u ispoliranom obliku) volio staviti na Blogaritam. (Ovaj meme na kraju, doduše, može se doimati politički nekorektnim. Kao, muškarac dobiva novac, a žena ga spiska. No dobro je što muškarac na slici nije zaradio novac, nego dobio na lutriji, pa ne ispada da muškarac zarađuje za ženu.)

Za kraj, Bruno je primijetio da autor originalnog memea sigurno nije imao našu interpretaciju na umu. On je zabrijao, ali ipak je dobro ispalo. Kao kad izgovorite nešto glupo, ali to iz nekog razloga na koji niste računali ispadne duhovito pa slučajno impresionirate ljude. Događalo mi se nekoliko puta.

Statistika i (neki) statističari

COVID! Napokon nešto o Covidu! Aaaaa! Prije mjesec dana pojavio se kontroverzni preprint (preprint znači znanstveni članak koji tek treba proći recenziju i biti prihvaćen za objavljivanje u časopisu) među čijim je autorima nekoliko naših znanstvenika (između ostalih Alemka Markotić, Dragan Primorac i Gordan Lauc). Ugrubo, članak na temelju određenih podataka o europskim pacijentima zaključuje da je ljetni covid manje opasan od zimskog. Kontroverzan je zato što je, s jedne strane, dobio dosta medijskog publiciteta i u nas i u inozemstvu, a s druge strane kritike od izvrsnog mladog znanstvenika Jana Homolaka i njegovih suradnika. Oni su kritizirali statističke metode kojima su Lauc i ekipa iz podataka došli do odgovarajućih zaključaka. Statistika nije moje područje pa toj raspravi (koja se proširila na Twitter i Facebook) ne mogu doprinijeti, osim ovakvim dijeljenjem koje nas, ako ništa drugo, može zainteresirati i dati dobar uvid u znanstvenu metodologiju.

A statističari bi ovu priču mogli rasvijetliti, te iz gomile složenih podataka koje je moguće tumačiti na tisuću načina izvući uzročno-posljedične veze. Statistikom se inače bavi naš prvi zlatni IMO-vac Domagoj Ćevid, a o nekim zanimljivostima govorio je ovdje (ako vas zanima više, poslušajte cijeli intervju).

Nedavno sam čitao o jednoj pogrešnoj, a nažalost vrlo utjecajnoj statistici. Krajem prošlog stoljeća istraživanja su (ugrubo) kazivala da ljudi koji piju prosječno 1-2 alkoholna pića dnevno imaju najbolje zdravlje, točnije, bolje od onih koji piju više ili ne piju ništa. Takav narativ svakako je poticao konzumaciju alkohola, no on je pogrešan:

But there was a problem with many of these studies: They compared drinkers to non-drinkers (…). And people who don’t drink are pretty fundamentally different from drinkers in ways that are hard to control for in a study. Their lives probably look dissimilar. Most importantly, they may be sicker at baseline (perhaps they quit drinking because of alcoholism, or because of a health issue like cancer). And something in these differences — not their avoidance of alcohol — may have caused them to look like they were in poorer health than the moderate drinkers. (This became known as the “sick quitter” problem in the world of alcohol research.)

Matematičarima je to možda strano, ali u znanosti (nažalost) ključnu demonstrativnu ulogu igraju eksperimenti i njihova analiza. U računarstvu, gdje se u znanstvenom radu obično predlaže neki algoritam, model, metoda ili protokol, eksperiment se sastoji od testiranja ili simulacije predložene metode na odabranim testnim podatcima, pri čemu je često važna usporedba s alternativnim, postojećim metodama. U medicini ili psihologiji eksperimenti se rade na ljudima koji se dijele na ove ili one skupine i moguće je pogriješiti na stotinu načina – što u izvedbi eksperimenta, što u tumačenju rezultata. Jedno od najvažnijih svojstava je ponovljivost, što znači: ako neki drugi istraživač neovisno izvede isti eksperiment, morao bi dobiti vrlo slične rezultate. Ovdje je zanimljivo da je 2015. godine provedena studija koja je pokušala replicirati razne rezultate prethodnih psihologijskih istraživanja, nažalost s razočaravajućim rezultatima.

Čovjek bi rekao da je u matematici provjera najlakša, jer riječ je o egzaktnoj znanosti – dokaz ili je ispravan, ili ima grešku u zaključivanju i ozbiljni matematičari (gotovo) uvijek će se međusobno složiti jer logika govori sama za sebe. Nekad je tu grešku lako detektirati – godišnje se pojavi stotinjak amaterskih “rješenja” velikih matematičkih problema poput dokaza da je P ≠ NP. Ipak ima i slučajeva kada su i najozbiljniji matematičari u nesuglasju, no takvi slučajevi vrlo su rijetki. O jednom od njih pisao sam u postu Matematika i (neki) matematičari.

Ljetna poslastica: dvadeset i jedan (“židovski”) matematički zadatak

Najprije mala digresija, naime, zašto sam napisao dvadeset jedan umjesto 21? Zato što ovo drugo nije u duhu jezika. U kontekstu formula je naravno drugačije, ali u običnom tekstu nije; pokušajte zamisliti npr. Šenou, Krležu ili nekog pjesnika da ima znamenke u rečenici. Ružno je! Kao što bi rekao Goran Bare: “Tko razumije, razumije. Tko ne razumije, neće nikad ni razumjeti!” (Ako koga zanima, to je rekao na 0:45 na ovom koncertu.)

Jučer sam naletio na zanimljiv članak sa zadatcima s prijamnih ispita moskovskog matematičkog fakulteta. Članak se zove Jewish Problems jer je riječ o malo težim zadatcima koje su na usmenom ispitu postavljali židovskim kandidatima koje očito nisu naročito voljeli:

“Among problems that were used by the department to blackball unwanted candidate students, these problems are distinguished by having a simple solution that is difficult to find. Using problems with a simple solution protected the administration from extra complaints and appeals.”

Malo sam škicnuo rješenja i čini se da nisu sva baš tako kratka i jednostavna, ali izgleda da su zadatci odlični. Ono što je osobito dobro jest da prije poglavlja Solutions postoji poglavlje Ideas koji sadrži hintove za sve zadatke. To je odlična praksa! Kad sam se ja natjecao, u materijalima toga uglavnom nije bilo. Možda je sad drugačije, ali ako nije, svakako treba biti.

I za kraj, što drugo mogu nego preporučiti knjigu AHA! Matije Bašića! Pod uvjetom da se na ovoj vrućini ne razlijemo po kaučima i mozak nam ne postane toplo varivo.

Male tajne velikih brojeva

O nuli sam već pisao u postu I nula je broj. Ondje nisam spomenuo jedno zanimljivo svojstvo nule o kojemu ću sada govoriti, a bez kojeg matematički doživljaj ovog broja ne bi bio potpun.

Poanta nule nije u ništavilu, nego u potencijalu. Recimo, ako imam slobodan dan ili dio godišnjeg odmora s nula obaveza i planova, dakle, ako uopće ne znam kako ću ga provesti, osjećam se izvrsno jer potencijalno dopuštam svemu da se dogodi. John C. Parkin napisao je: “All things manifest from nothing. Leave space, lots of space, in your life.” Toga je bio svjestan i naš poznati matematičar Vladimir Devidé kada je ovako komentirao sljedeću japansku haiku pjesmu:

Koliba u proljeće:
ničega u njoj –
u njoj je sve!

(Sodō, 1642. – 1716.)

“Pročitavši to, bio sam kao ošinut. U proljeće, kad se sve budi, eto prazne kolibe koja upravo time što je prazna omogućava da sve uđe u nju, upravo ga zove. Nema ničega, nikakvih nepotrebnih stvari koje bi to priječile. Svo bujanje proljeća puni praznu kolibu svojim beskrajnim bogatstvom.”

Poanta minimalizma nije u redukciji broja stvari, nego u činjenici da oslobađanjem od suvišnih stvari ostavljamo mjesta za nove stvari. Recimo, jednom sam riješio jednadžbu tako što sam odlučio da je uopće neću riješiti. Neke sam knjige namjeravao pročitati, ali taj sam problem riješio odlukom da ih uopće neću pročitati. Idealno matematičko predavanje bilo bi ono u kojemu se ne bi govorilo o ničemu. Mnoge stvari u životu unaprijed su riješene odlukom da ih neće biti.

U sličnom smjeru ide i sljedeća ideja: možda je bolje kupiti ručni sat nego, recimo, gitaru ili bicikl. Naime, gitaru treba svirati, bicikl treba voziti, a sat radi sam od sebe: on uzima nula vremena i kao takav daje sve vrijeme svijeta! Nastavimo li ovako zaključivati, možda je još bolje kupiti zidnu sliku jer ona traži još manje od sata (ne treba je ni nositi na ruci). Potom, još je bolja neka stvar koju uopće ne možemo kupiti jer s njom ne moramo baš ništa, ni kupiti je ni išta s njom činiti. A najbolja je ona stvar za koju uopće ne znamo da postoji, jer onda ni ne znamo da s njom ne moramo ništa. Eto, to je poanta nule, to je poanta slobode i to je poanta godišnjeg odmora.

Dokaz ostavljamo čitateljici za vježbu

U opisima algoritama, koji su dio objavljenih rješenja većine domaćih natjecanja, nerijetko se na kraju opisa rješenja pojedinog zadatka pojavljuje rečenica “Dokaz točnosti algoritma ostavljamo čitatelju za vježbu”. Ili čitateljici, da ne bi tko pomislio da autori imaju predrasude. Tako smo u rješenjima Studentskog 2018. u čak tri zadatka ostavili dokaz točnosti ili efikasnosti algoritma za vježbu upravo čitateljici.

Navedena rečenica nije karakteristična samo za opise algoritama, ona se često viđa i u matematici i sličnim znanostima. No koje je njezino pravo značenje?

Iz iskustva, rečenica može imati tri moguća značenja:

  1. Dokaz ostavljamo čitatelju za vježbu jer je točnost ili efikasnost algoritma, ako se on čita s razumijevanjem i ako se o njemu malo promisli, prilično očita i dokaz je bolje izostaviti da bi čitatelj malo zastao i razmislio o pročitanom. (Ovo je slučaj u zadatku Stablo u stablu sa spomenutog Studentskog.)
  2. Dokaz ostavljamo čitatelju za vježbu jer smo u se u točnost tvrdnje uvjerili intuitivno, a znali bismo je i dokazati, ali dokaz nije lako ukratko napisati i vjerojatno bi bio ružnjikav. (Ovo je slučaj u zadatku Ploča sa spomenutog Studentskog, kao i npr. u zadatku Sails – IOI 2007.)
  3. Dokaz ostavljamo čitatelju za vježbu jer tvrdnju ne znamo sami dokazati. (Ovo je slučaj u zadatku Načitan sa spomenutog Studentskog za neparan N, a skoro je bio slučaj i u zadatku GTA s Izbornih priprema 2014.)

Postoji i četvrti slučaj – autor rješenja izostavlja ne samo dokaz, nego i navedenu rečenicu, praveći se da je sve jasno, iako nije. Krunski primjer je zadatak Mravograd (Državno 2007.) koji je poznat po kratkom i lijepom rješenju za koje nije očita ni točnost, a pogotovo efikasnost tj. složenost algoritma. Do ključne zamjedbe dolazi se određenim koracima u razmišljanju koji su u službenom opisu izostavljeni. Drugim riječima, rješenje nije napisano metodički. No budući da se radi o zadatku za malo jaču publiku, autor (Luka Kalinovčić, ako se ne varam) nije nas podcijenio: čitatelji (i čitateljice, naravno) sposobni su sami ispuniti rupe u rješenju. A ta je rupa generiranje slučajnih primjera i promatranje u kojim se oblicima pojavljuju traženi “mokri trgovi”. Odatle se dolazi do tražene ideje.

U praksi je, dakle, i empirijski dokaz često dovoljan. Ionako u implementaciji griješimo češće nego u ideji. Testiranje rješenja usporedbom sa brute-forceom i generatorom slučajnih primjera u praksi je odličan dokaz. (To zaboravljaju neki natjecatelji naviknuti na online evaluatore i full feedback i onda griješe na županijskom ili HONI natjecanju.) Nedavno je Errichto pisao o jednom manje uobičajenom načinu testiranja. Ja sam je iskoristio nedavno, kada sam za zadatak Dionice (autora Domagoja Bradača) s ovogodišnjeg županijskog natjecanja pisao rješenje radi provjere. Nisam htio implementirati potpuno isti algoritam kao Domagoj (jer što ako je slučajno pogrešan), nego sam odlučio zadani niz gledati unatrag i primijeniti analogan algoritam u obrnutom smjeru. Dobio sam iste rezultate, što je empirijski potvrdilo točnost algoritma. Domagoj je doduše napisao dokaz, ali kao što ovaj odlomak sugerira, matematički dokaz nikad nije dovoljan jer ljudi griješe (zabrijavaju). U matematici se stvari dokazuju, a u drugim znanostima (kao i u životu) stvari se testiraju.

Dakle, pravo značenje rečenice “Dokaz ostavljamo čitatelju za vježbu” upravo je ono koje čitatelj svjesno ili nesvjesno percipira čim pročita tu rečenicu. Ono glasi: “Formalni dokaz nije bitan”. Bitno je da se čitatelj na ovaj ili onaj način uvjeri u istinitost tvrdnje. Primjerice, ako želimo podijeliti prirodne brojeve A i B tako da količnik zaokružimo na više, možemo ga dobiti kao (A + B – 1) div B. Na jednoj radionici nije mi se dalo objašnjavati zašto je tako pa sam rekao “dokažite za domaću zadaću”. Naravno, nisam očekivao da itko to formalno dokaže koristeći najveće cijelo i nejednakosti. U ovom slučaju dovoljno se uvjeriti na primjerima promatrajući nekoliko bitnih slučajeva. Dokazivanje je samo formalizacija intuicije, iako je taj stav općenito diskutabilan. Razmislite o njemu sami, za vježbu.

Digresija: Dedekindovi brojevi

Na koliko načina možemo svakom broju iz skupa S = {1, 2, …, N} pridružiti 0 ili 1? Drugim riječima, koliko ima funkcija iz S u {0, 1}?

Well, that’s easy – dvije mogućnosti za 1, puta dvije mogućnosti za 2, puta dvije mogućnosti za 3, i tako dalje, ukupno 2^N.

Idemo dalje: na koliko načina možemo svakom podskupu od S pridružiti 0 ili 1? Drugim riječima, koliko ima funkcija iz skupa svih podskupova – partitivnog skupa P(S) u {0, 1}?

Analogno prethodnome, to je 2^K gdje je K broj podskupova, jer za svaki podskup biramo 0 ili 1. A koliki je K? Podskup kreiramo tako da svaki broj u njega stavimo ili ne stavimo (dvije mogućnosti), dakle K = 2^N. Traženih je funkcija, dakle, 2^{2^N}.

Idemo dalje…

Na koliko načina možemo svakom podskupu od S pridružiti vrijednost 0 ili 1, ali tako da dodavanjem elemenata u podskup njegova vrijednost može samo porasti? Drugim riječima, koliko ima monotonih funkcija f : P(S) \to \{0, 1\}, što znači da je f(A)\le f(B) za sve A\subset B?

Nemamo pojma, ali na prvi pogled možemo brutati, tj. napisati program koji ovo prebraja za dovoljno mali N. Što mislite, koliko mali?

Riječ je o N-tom Dedekindovom broju, a ono što je fascinantno je da već za N = 9 nitko nije uspio izračunati taj broj. Postoji formula, ali ona nije zatvorena, tj. sadrži sumaciju pa u suštini i nije formula nego spori pseudokod.

Osmi Dedekindov broj izračunat je još 1991. godine i to uz pomoć pametnih trikova za smanjenje složenosti. Osim u izvornom članku, taj algoritam možete pronaći i ovdje. Iako su se od tada računala ubrzala stotinu i više puta, deveti Dedekindov broj još uvijek je nedohvatljiv. A ima 40ak znamenaka, prava sitnica. Evo vam prilike da se upišete u povijest matematike.

Čini mi se da trenutačno znanje o Dedekindovom problemu nije dovoljno da bi se osmislio dovoljno efikasan algoritam za N = 9, ma koliko ga pametno optimizirali. Potrebna je nova spoznaja o samom problemu, neki novi teorem koji će omogućiti pojednostavljenje formule.

Ok, so what? Ima mnogo neriješenih problema u matematici; zašto sam baš o ovome pisao? Zato što izgleda rješiv (naglasak je na izgleda, a ne na rješiv :)) i zato što, čini mi se, trenutačno ne zanima ozbiljne matematičare pa konkurencija nije jaka. Ako nas dvadeset navali na problem, dovoljno je da svatko izračuna samo dvije ili najviše tri znamenke. Računala će se još ubrzati, a iskustvo nas uči da zadatak s ograničenjem N ≤ 10 ne može biti težak.

Digresija: matematika i (neki) matematičari

Prekjučer se pojavio zanimljiv članak o nesporazumu nekolicine velikih matematičara o tome je li Japanac Shinichi Mochizuki dokazao ABC hipotezu ili nije, a budući da jedan od sudionika te priče ima veze s matematičkim natjecanjima i jednom sam ga prilikom upoznao, došlo mi je napišem ovaj post.

Ne razumijem se u područje nimalo, ali koliko sam shvatio, Mochizukijev dokaz u četiri rada na ukupno 500 stranica ne razumije nitko osim samog Mochizukija; riječ je o novoj teoriji koja uvodi hrpu novih koncepata te osim ABC hipoteze rješava još neke otvorene probleme. Ozbiljni matematičari možda bi ignorirali takve nastranosti da Mochizuki i sam nije ozbiljan matematičar s prethodnim značajnim rezultatima. Ovako je privukao pažnju 30-godišnjeg matematičara Petera Scholzea koji je zajedno sa svojim kolegom Jakobom Stixom u ožujku otputovao u Kyoto da bi Mochizukiju objasnio zašto mu dokaz ne valja, na što je Japanac odgovorio da oni ništa ne kuže.

Peter Scholze nije bilo tko, on je dobitnik Fieldsove medalje, “matematičkog nobela”. Prije deset godina potražio sam ga na IMO-u 2008. (tada je vodio njemački tim) jer je prethodnih godina bio iznimno uspješan natjecatelj. Kad sam ga pitao postoji li osoba koja može riješiti bilo koji zadatak koji se pojavi na IMO-u ili Shortlistu, rekao je da je on takva osoba, ali to nije rekao hvalisavim ili ponosnim tonom. Također mi je rekao da, kad se pripremao za natjecanja, uglavnom nije čitao rješenja nego bi zadatak koji ne zna riješiti uvijek ostavljao za poslije.

Suprotnu stvar rekao mi je još uspješniji IMO-vac Iurie Boreico, osvajač nekoliko perfect scoreova na IMO-u i posebne nagrade za rješenje nejednakosti na IMO-u 2005. Njega nisam upoznao, ali sam ga bio kontaktirao na MSN-u (messenger iz nekih davnih vremena). On mi je tada savjetovao da, barem u početku, bez pardona čitam rješenja zadataka koje ne znam riješiti. Zanimljivo. Ne sjećam se svega, no možda je taj savjet bio u kontekstu mog početništva, jer tada još nisam bio IMO-vac.

Kome je bolje vjerovati? Vjerojatno osvajaču Fieldsove medalje. Uz Iuria se vežu neke zanimljivosti, npr. to da je trenutačno “Algorithmic Trader at Jump Trading LLC” (info s LinkedIna). Dakle, jedan ima više para, drugi je veća faca, ali obojica su legende.