Je l' dosta 3 algoritma? :)
1) Pica se zaseče na jednom mestu i nož se vrti iz centra pice polako ukrug. Kada neka osoba bude zadovoljna parčetom koje bi se dobilo kada bi se pica presekla tamo gde se nož trenutno zadesi uzvike: "Stop!". Tada se to parče iseče i da se osobi koja je uzviknula, i postupak se nastavlja. Ukoliko dve ili više osoba viknu istovremeno parče se daje bilo kojoj od njih.
2) Prva osoba iseče n-ti deo pice (po sopstvenoj proceni). Zatim se odsečeno parče kreće od osobe do osobe i svako ko misli da je veće od n-tog dela može da odseče "višak". Poslednja osoba može da uzme parče ako želi, u suprotnom parče ide poslednjoj osobi koja je sekla. Ostatak ponavljamo bez osobe koja je dobila parče.
3) Ovaj je možda najkomplikovaniji. Prva osoba uzme kod sebe celu picu. Neka broj k uzima vrednosti od 2 do n. U svakom koraku se dešava sledeće: prvih k-1 osoba iseče svoj deo na k delova, a zatim k-ta osoba sebi uzme jedan od njih.
To bi bilo to, ali ovo pitanje poteže još jedno: iako je svaka osoba ovde uverena da može sebi da uzme bar n-ti deo pice, može li se smisliti takav algoritam koji će garantovati još i da nijedna druga osoba ne dobije više? Ovo je mnogo teži problem i algoritam koji sledi je za 3 osobe (kako ide za više ne znam):
a) Prva osoba podeli picu na 3 jednaka dela;
b) Druga osoba od najvećeg dela odstrani toliko koliko je potrebno da ostatak bude jednak sa srednjim delom;
c) Treća osoba bira parče. Ako ostavi "skraćivano" parče onda ga uzima druga osoba, u suprotnom druga osoba bira jedno od preostalih. Prva osoba dobija ono što ostane.
d) Druga ili treća osoba ima "skraćivano" parče - neka je to osoba P, a ona koja ga nema osoba Q. Osoba Q deli "višak" iz koraka b) na 3 dela od kojih po jedan biraju P, prva osoba, Q, redom.
To bi bilo to, ima li pitanja? :)
Ljubičice crvena, što si plava kô zelena trava.
Kako iseći i podeliti pizzu a da svi budu zadovoljni?
