Formulujeme si jednu teoretickú úlohu a jednu súťaž pre všetkých, ktorí si myslia, že sú programátorskí machri.
Úloha: Dokážte, že existuje najväčší trojfarebný chaotický trojuholník. Inými slovami, ukážte, že existuje prirodzené číslo n také, že trojfarebný chaotický trojuholník veľkosti n už principiálne nie je možné skonštruovať. Môžete použiť Peťove riešenie predchádzajúceho príkladu a Van der Waerdenovu vetu, na ktorú nás upozornil Nanyk.
Súťaž: Pomocou počítača nájdite trojfarebný chaotický trojuholník s veľkosťou aspoň 15, t.j. väčší ako ten, ktorý som našiel ja:
Nie som si úplne istý s tým, že existuje väčší trojfarebný chaotický trojuholník ako ten môj, ale považujem to za veľmi pravdepodobné. Môj trojuholník je totiž výsledkom krátkeho výpočtu jednoduchého programu v pomalom jazyku R. Každopádne ak sa do riešenia tejto úlohy pustíte, pošlite nám najväčší trojfarebný chaotický trojuholník aký nájdete.
28.8.: Mišo našiel chaotický trojfarebný trojuholník veľkosti 16! Tu je:
Kto Miša prekoná má môj obdiv! To už ale bude asi poriadne ťažké...
5 komentárov:
Bol som celkom zvedavý, ako si s tým poradí nejaký všeobecný solver, tak som zobral prvý SAT solver čo mi prišiel pod ruku (relsat) a zgeneroval som mu príslušný vstup.
N=16 dal za niekoľko sekúnd, výsledok tu, na N=17 zatiaľ hodinu beží bez úspechu.
misof: hmmmm. no dobre, dufam, ze ti neodbehol prilis daleko. :-)
inak, mam otazku na autora blogu: co su to tam tie hieroglyfy vedla chaotickeho trojuholnika?
misof: Super! To musela byť teda riadna spústa premenných; som trochu prekvapený, že to tie solvery tak rýchlo riešia. Mohol by si nám k tomu napísať trochu viac (napríklad na svoj blog, alebo aspoň sem do komentárov). Je totiž jasné, že sa takto dajú parádne riešiť podobné kombinatorické problémy. Sám by som si možno potom odskúšal nájsť čo najväčší trojfarebný štvorec neobsahujúci monochromatické obdĺžniky. Tiež prosím napíš, ako dopadol ten solver pre n=17.
Anonym: Vedel som, že to niekomu nedá a spýta sa :-). No dobre, prezradím. Je to hieroglifický zápis mena Sutekh, čo bol Egyptský boh chaosu.
Premenných je 3N(N+1)/2, tri pre každú guličku: pre každú pozíciu X a farbu Y mám premennú je_gulička_X_farby_Y?
Potom vieme zostrojiť SAT formulu v konjunktívnej normálnej forme (čo je štandardná forma vstupu pre väčšinu solverov), ktorá bude splniteľná práve vtedy, ak sa trojuholník dá ofarbiť.
V našom prípade potrebujeme:
* Každá pozícia má aspoň jednu farbu.
* Žiadna pozícia nemá dve farby.
* Pre žiadne tri pozície vo vrcholoch trojuholníka a žiadnu farbu nie sú súčasne všetky tri pozície tej farby.
Pre N=16 je to 408 premenných a 3508 podmienok.
Inak, pre N=17 to ani za noc nič nenašlo, ak ešte nejaké také trojuholníky sú, už asi budú dosť "nariedko" :)
Mišo: Paráda. Je to úplne jasné. Už len neviem, ako si tam tých 3508podmienok zadal. Určite si ich nepisal ručne...
Zverejnenie komentára