Stebėtinai sudėtingas tortų pjaustymo menas

Matematikai mėgsta gerą pyragą, todėl vargu ar stebina, kad problema, kaip, tarkime, Viktorijos biskvitą išpjauti ir paskirstyti, juos smarkiai išvargino. Šiandien tortų mėgėjai bus sujaudinti išgirdę apie reikšmingą proveržį.

Problema yra tokia: kaip supjaustyti pyragą ir teisingai jį padalinti n žmonių, kai kiekvienas gali turėti skirtingą nuomonę apie kiekvieno kūrinio vertę?

1980 m. Walteris Stromquistas Swarthmore koledže netoli Filadelfijos įrodė, kad yra be pavydo problemos sprendimas. Kitaip tariant, galima įpjauti tortą n gabalai naudojant n −1 pjūvį ir kiekvienam asmeniui skirti po vieną gabalą, kad kiekvienas vertintų savo gabalą ne mažiau nei bet kurį kitą gabalą.

Tačiau nors sprendimas gali būti įmanomas, jį rasti sunku. Šiandien kyla atviras klausimas, ar yra efektyvus algoritmas, aptinkantis tokį pyrago pjūvį, sako Xiaotie Deng iš Honkongo miesto universiteto ir keli draugai.

Jų indėlis į problemą yra rasti tokį algoritmą, nors ir su keliais nedideliais įspėjimais. Įspūdingai, jų algoritmas veikia daugianario laiku, o tai reiškia, kad sprendimą visada galima rasti pakankamai greitai.

Perspėjimai? Algoritmas veikia dalijant pyragą tik trims žmonėms, o tada tik specialiu atveju, kai yra susiję matematiniai objektai, vadinami išmatuojamomis naudingumo funkcijomis, ir rezultatas yra tik maždaug be pavydo.

Nepaisant to, tai vis tiek turėtų būti naudinga, kai kitame jaunesniojo bendro kambario arbatos vakarėlyje kyla ginčas.

Nuoroda: arxiv.org/abs/0907.1334 : Apie pyrago pjaustymo be pavydo sudėtingumą

paslėpti