Tag: Kombinatorika

  • „Justin Sun Prize“ paskelbė pirmuosius laureatus: DI ir žmonių tandemas sprendė Erdőso uždavinius

    „Justin Sun Prize“ paskelbė pirmuosius laureatus: DI ir žmonių tandemas sprendė Erdőso uždavinius

    Šveicarijoje įsikūrusi „Justin Sun“ biuras spalio 5 dieną pranešė apie pirmuosius patvirtintus „Justin Sun Prize“ laureatus. Apdovanojimas atiteko nepriklausomam tyrėjui Wouteriui van Doornui, matematikos doktorantui Quanyu Tang ir Nandzingo Pietryčių universiteto tyrėjai Yanyang Li už darbus, susijusius su šešiais vadinamaisiais Erdőso uždaviniais.

    Erdőso uždaviniai – tai vengrų matematiko Paulo Erdőso suformuluoti arba išpopuliarinti klausimai skaičių teorijoje ir kombinatorikoje. Jie dažnai skamba paprastai, tačiau jų sprendimui prireikia metų ar net dešimtmečių, o dalis problemų iki šiol lieka atviros.

    Kas įvertinta ir kodėl svarbu

    Pasak apdovanojimo organizatorių, van Doornas, Tang ir Li bendradarbiavo spręsdami Erdőso problemą Nr. 650, kurioje siekta tiksliai nustatyti, kiek sveikųjų skaičių visuomet galima suporuoti su skirtingais jų kartotiniais apibrėžtame intervale. Tai tipinis Erdőso stiliaus klausimas: formuluotė trumpa, tačiau už jos slypi sudėtinga struktūra apie skaičių išsidėstymą ir dėsningumus.

    Kartu pabrėžiama, kad apdovanojime vertinamas ne tik naujas matematinis rezultatas, bet ir įrodymo patikrinamumas. Dėl to dalis darbų buvo parengti taip, kad juos būtų galima formaliai verifikuoti naudojant „Lean“ – programinę aplinką, leidžiančią kompiuteriu tikrinti matematinių įrodymų logiką.

    DI vaidmuo sprendimuose

    Vienas ryškiausių šio pranešimo akcentų – žmonių ir DI bendradarbiavimo elementas. Nurodoma, kad rengiant problemos Nr. 650 sprendimą DI įrankiai prisidėjo kuriant įrodymo strategiją, o formalizavimo etape padėjo rasti ir užtaisyti spragą, kad įrodymas atitiktų griežtus kompiuterinės verifikacijos reikalavimus.

    „Ši patirtis parodė, kaip viešas grįžtamasis ryšys gali patikslinti tyrimo klausimą, o DI padedamas atradimas gali sujungti matematinį sprendimą, bendradarbiavimą ir griežtą verifikaciją“, – sakė Quanyu Tang.

    Pranešime taip pat teigiama, kad van Doornas parengė kompiuteriu patikrinamus „Lean“ įrodymus kelioms kitoms Erdőso katalogo problemoms, susijusioms su pirminių daugiklių apribojimais ir skaičių aibių savybėmis. Tuo metu Tang atskirai išsprendė problemą Nr. 1 044, kurioje buvo nustatyta tiksli apatinė riba tam tikrų polinomais apibrėžtų sričių ribų ilgiams, o kartu su Li prisidėjo prie problemos Nr. 1 196 sprendimo komandoje.

    Ką tai reiškia matematikai

    Pastaraisiais metais matematikoje ryškėja dvi lygiagrečios kryptys: DI įrankių naudojimas idėjoms generuoti ir formaliųjų įrodymų tikrinimo plėtra, siekiant išvengti klaidų sudėtinguose argumentuose. Šiame kontekste „Justin Sun Prize“ pristatomas kaip iniciatyva, bandanti sujungti abi kryptis, skatindama tiek sprendimų paiešką, tiek jų patikimumą.

    Organizatoriai pabrėžia, kad apdovanojimas orientuotas į įrodymo stiprumą ir patikrinamumą, o ne į autorių statusą ar institucijų prestižą. Tai ypač aktualu šiandien, kai augant tyrimų apimtims ir sudėtingumui vis didesnę reikšmę įgauna skaidrumas, atkartojamumas ir aiškiai patikrinamos metodikos.

  • Matematikai sukūrė sąžiningiausią kauliuką: 60 sienelių mįslė spręsta 15 metų

    2010 metais stalo žaidimų kūrėjas Jamesas Ernestas iškėlė, iš pirmo žvilgsnio, paprastą klausimą: ar įmanoma sukurti tokį kauliukų rinkinį, kad pranašumas sprendžiant, kas pradeda žaidimą, būtų vienodai sąžiningas bet kokiam žaidėjų skaičiui.

    Užduotis atiteko matematikui Ericui Harshbargeriui iš Auburn universiteto Alabamoje. Netrukus paaiškėjo, kad vien „teisingai“ sunumeruoti kauliuką neužtenka, nes sąžiningumas turi galioti ne tik visam rinkiniui, bet ir bet kuriam jo poaibiui.

    Kaip veikia 60 sienelių idėja

    Sprendimas galiausiai virto penkių kauliukų rinkiniu, kuriame kiekvienas kauliukas turi 60 sienelių. Ant jų išgraviruoti skaičiai nuo 1 iki 300, o nė vienas skaičius rinkinyje nesikartoja.

    Toks rinkinys leidžia išvengti lygiųjų be pakartotinių metimų: kiekvienas žaidėjas meta po vieną kauliuką, o didžiausia iškritusi reikšmė lemia, kas pradeda. Esmė ta, kad skaičių išdėstymas parenkamas taip, jog nė vienas kauliukas nesuteiktų sisteminio pranašumo.

    Kodėl tai užtruko 15 metų

    Didžiausia kliūtis buvo kombinacijų skaičius: norint įrodyti, kad rinkinys sąžiningas skirtingiems žaidėjų skaičiams, reikia tikrinti milžinišką skaičių išdėstymo variantų. Praktikoje tai reiškia ne vien kūrybą, bet ir sudėtingą tikimybių bei kombinatorikos uždavinį.

    „Lygiųjų išvengti paprasta: tereikia ant kauliukų užrašyti skirtingus skaičius. Tačiau sunkumas prasideda tada, kai privalai užtikrinti vienodą tikimybę ne tik visam rinkiniui, bet ir kiekvienam jo poaibiui“, – sakė Ericas Harshbargeris.

    Ankstesni bandymai davė dalinę sėkmę: per trumpesnį laiką buvo sukurti variantai, kurie veikė konkrečiam žaidėjų skaičiui, pavyzdžiui, trims. Tačiau reikalavimas, kad sprendimas išliktų teisingas bet kokiai grupei, ilgai atrodė nepasiekiamas.

    Proveržis atėjo iš šalies

    2023 metais situacija pasikeitė, kai kanadiečių inžinierius Paulas Meyeris, susidomėjęs problema, sukūrė programą, leidžiančią efektyviau ieškoti tinkamo skaičių išdėstymo. Šis etapas parodė, kaip šiuolaikiniai skaičiavimai ir programavimas gali pagreitinti sprendimų paiešką net ir ten, kur grynai rankiniai skaičiavimai praktiškai neįmanomi.

    Vis dėlto istorija dar nėra visiškai užbaigta: sprendimai skirtingiems žaidėjų skaičiams gali būti plečiami etapais, nes kiekvienas naujas atvejis reikalauja atskiro patikrinimo ir įrodymų. Šiandien kai kurie rinkinio variantai jau gaminami ir platinami, o pačios idėjos populiarumas paskatino platesnę diskusiją apie tai, kas iš tiesų yra „teisingas atsitiktinumas“ žaidimuose.

    Įdomu ir tai, kad projektas peržengė vien teorijos ribas. Auburn universitete atsirado ir vizualus šio darbo įprasminimas: matematikos erdves papuošė didelės skulptūros, atkurtos pagal sukurtų kauliukų formas, taip pabrėžiant, jog abstraktūs tikimybių uždaviniai gali virsti apčiuopiamais objektais.