Dan prije američkih predsjedničkih izbora 1996., New York Times objavio je križaljku u kojoj je jedan od pojmova bio opisan kao sutrašnja glavna vijest: ******* ELECTED. Je li autor križaljke predvidio izbornog pobjednika?

Genijalnost je bila u tome da se križaljka mogla riješiti na dva jednako ispravna načina: kao novi predsjednik mogao je stajati i CLINTON i BOB DOLE, a da ostali pojmovi i dalje odgovaraju svojim opisima. Npr. black halloween animal ispao je CAT u slučaju CLINTON, a BAT u slučaju BOB DOLE. I tako dalje. Križaljku je sastavio matematičar Jeremiah Farrell.

Dva rješenja ove križaljke razlikuju se u jednom pojmu. Može li više?

U tome je uspio još jedan genijalac, filozof Daniel Dennett. Sastavio je križaljku u kojoj se dva rješenja razlikuju potpuno, dakle u svim pojmovima. Osoba A i osoba B mogu ispravno riješiti križaljku, a da im se, kada usporede rješenja, nijedna riječ (ili čak nijedno slovo) ne podudara, iako za svaki opis i A i B imaju dobar pojam na odgovarajućem mjestu. Križaljku je nazvao kvinijskom (Quinian crossword puzzle) jer ju je upotrijebio da bi ilustrirao zamisao filozofa W. V. O. Quinea o nejednoznačnosti prijevoda (što ovdje nije bitno).

Dennettova prva križaljka izgledala je ovako:

Nije baš lagana, pogotovo nama čiji je vokabular engleskog jezika ograničen. Meni je trebalo dosta guglanja da bih pronašao oba moguća rješenja, a pomogao je i rječnik sinonima. Otkrit ću vam da retentive membrane (1 okomito) može biti web ili sac.

Poslije je unaprijedio svoju kvinijsku križaljku, tj. sastavio bolju:

(Oba) rješenja poslije ću otkriti u komentaru. No glavni je cilj ovog posta zadati jedan mnogo teži i ozbiljniji izazov. Vjerojatno ste ga dosad i naslutili.

Sastavimo prvu hrvatsku kvinijsku križaljku.

Sastaviti običnu 3 x 3 ili 4 x 4 križaljku nije naročito teško. No zahtijevamo li da križaljka ima još jedno rješenje, u pojmovima različito ali također ispravno tj. u skladu sa zadanim opisima, problem postaje brutalan. No Dennett ga je riješio, pa valjda možemo i mi. Hrvatski jezik, zbog pravilnije izmjene samoglasnika i suglasnika, pogodniji je od engleskog za sastavljanje križaljki – što možete uočiti i uspoređujući broj “crnih” (neiskorištenih) polja u prosječnoj hrvatskoj i prosječnoj engleskoj križaljci.

Rješenje će sigurno uključivati mnogo mašte u povezivanju naizgled nepovezanih pojmova istim opisom, ali problem ne bih spominjao na ovom mjestu kad ne bih mislio da može imati veze i s programiranjem. Imam neke ideje o smjerovima u kojima bi se moglo ići, ali zasad je bolje da ne utječem ni na koga. Bit će još koji post o tome, a do tada možda netko pametniji od mene ovo i uspije.

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 .

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 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 . Traženih je funkcija, dakle, .

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 , što znači da je za sve ?

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.

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.