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.