Pārsteidzoši sarežģītā kūku griešanas māksla

Matemātiķiem ļoti patīk laba kūka, tāpēc diez vai ir pārsteigums, ka problēma, kā, teiksim, Viktorijas švammīti sagriezt un sadalīt, viņus ir smagi nomocījusi. Šodien kūku cienītāji būs priecīgi dzirdēt par nozīmīgu izrāvienu.

Problēma ir šāda: kā sagriezt kūku un godīgi sadalīt to starp n cilvēkiem, kad katram var būt atšķirīgs viedoklis par katra gabala vērtību?

1980. gadā Valters Stromkvists Swarthmore koledžā netālu no Filadelfijas pierādīja, ka problēmai ir bezskaudīgs risinājums. Citiem vārdiem sakot, kūku var iegriezt n gabalus izmantojot n −1 izcirtums un katram cilvēkam piešķirt vienu gabalu, lai katrs savu gabalu novērtētu ne mazāk kā jebkuru citu gabalu.

Bet, lai gan risinājums var būt iespējams, to atrast ir grūti. Šodien atklāts jautājums ir par to, vai ir kāds efektīvs algoritms, kas atrod šādu kūkas griezumu, saka Sjaotie Denga no Honkongas pilsētas universitātes un pāris draugi.

Viņu ieguldījums problēmas risināšanā ir šāda algoritma atrašana, lai gan ar pāris nelieliem brīdinājumiem. Iespaidīgi, ka viņu algoritms darbojas polinoma laikā, kas nozīmē, ka risinājumu vienmēr var atrast pietiekami ātri.

Brīdinājumi? Algoritms darbojas, sadalot kūku tikai starp trim cilvēkiem un pēc tam tikai īpašā gadījumā, kad tiek izmantoti matemātiski objekti, ko sauc par izmērāmām lietderības funkcijām, un rezultāts ir tikai aptuveni bez skaudības.

Tomēr tam joprojām vajadzētu būt parocīgiem, ja nākamajā junioru koptelpas tējas ballītē izceļas strīds.

Atsauce: arxiv.org/abs/0907.1334 : Par kūkas griešanas sarežģītību bez skaudības

paslēpties