Algojáték 6. gyakorlat megoldókulcs

Javaslat

A megoldásokat ne nézd meg rögtön, előbb szánj egy kis időt az önálló gondolkodásra és az ötletelésre! A problémamegoldás képessége olyan mint egy izom: mindenkiben fejleszthető. Ezek a feladatok pontosan ebben segítenek. Ha teljesen elakadnál, ott a hint.

1. feladat

Három játékos osztozkodik a $[0,1)$ intervallumon a Fink-eljárással. A játékosok értékelő eloszlásfüggvénye a következő. $$f_1(x) = \sqrt{x}, \quad f_2(x) = x, \quad f_3(x) = x^2$$ Tudjuk, hogy a második játékos megérkezése után az első a $[0, \frac{1}{4})$, a második pedig az $[\frac{1}{4}, 1)$ intervallumot birtokolja. Mondjuk meg, hogy a harmadik játékos körében mit csinál az algoritmus a $[0, \frac{1}{4})$ intervallumon!

Hint

Fink-eljárás: Online protokoll. Első körben az $1$. játékos megkapja a teljes $[0,1)$-et. Az $i$. körben az $i$. játékos megérkezik és az $1, \dots, (i-1)$ játékosok mindegyike $i$ darab a saját értékelő függvénye szerint egyforma részre osztja a saját részét. Az $i$. játékos mindenkitől egy, a saját értékelő függvénye szerinti legjobb részt elvesz.

Megoldás

Tudjuk, hogy a második körben az 1. játékos felezett, tehát neki a $[0, \frac{1}{4})$ intervallum éppen $\frac{1}{2}$-et ér.

A harmadik körben az 1. játékos harmadolja a $\left[0, \frac{1}{4}\right)$-et.

Tehát keressük az $a$ és $b$ értéket, ahol $$\mu_1\left(\left[0, a\right)\right) = \mu_1\left(\left[a,b\right)\right) = \mu_1\left(\left[b,\frac{1}{4}\right)\right) = \frac{1}{6}$$.

$$f_1(a) - f_1(0) = \frac{1}{6} \\ \sqrt{a}-\sqrt{0} = \frac{1}{6} \\ a = \frac{1}{36}$$ $$f_1(b) - f_1(a) = \frac{1}{6} \\ \sqrt{b}-\sqrt{a} = \frac{1}{6} \\ \sqrt{b} = \frac{1}{6} + \frac{1}{6} = \frac{1}{3} \\ b = \frac{1}{9}$$

Az 1. játékos részei: $\left[0, \frac{1}{36}\right)$, $\left[\frac{1}{36}, \frac{1}{9}\right)$, $\left[\frac{1}{9}, \frac{1}{4}\right)$

A 3. játékos értékelése az 1. játékos által ajánlott részekre:

$$\begin{aligned} \mu_3\left(\left[0, \frac{1}{36}\right)\right) &= \left(\frac{1}{36}\right)^2 - 0^2 &= \frac{1}{1296} \\ \mu_3\left(\left[\frac{1}{36}, \frac{1}{9}\right)\right) &= \left(\frac{1}{9}\right)^2 - \left(\frac{1}{36}\right)^2 &= \frac{15}{1296} \\ \mu_3\left(\left[\frac{1}{9}, \frac{1}{4}\right)\right) &= \left(\frac{1}{4}\right)^2 - \left(\frac{1}{9}\right)^2 &= \frac{65}{1296} \end{aligned}$$ Tehát a 3. játékos az $\left[\frac{1}{9}, \frac{1}{4}\right)$ részt választja, az 1. játékos pedig a $\left[0, \frac{1}{9}\right)$ részt tartja meg.

Ha valakit érdekel, a teljes végső szétosztás egyébként:

$$\begin{aligned} A_1 &= \left[0, \frac{1}{36}\right) \cup \left[\frac{1}{36}, \frac{1}{9}\right) = \left[0, \frac{1}{9}\right) \\ A_2 &= \left[\frac{1}{4}, \frac{1}{2}\right) \cup \left[\frac{1}{2}, \frac{3}{4}\right) = \left[\frac{1}{4}, \frac{3}{4}\right) \\ A_3 &= \left[\frac{1}{9}, \frac{1}{4}\right) \cup \left[\frac{3}{4}, 1\right) \end{aligned}$$

2. feladat

Három játékos osztozkodik a $[0,1)$ intervallumon a Fink-eljárással. A játékosok értékelő eloszlásfüggvénye a következő. $$\displaystyle f_1(x) = \begin{cases} 4x, & \text{ha $0 \le x \le 1/4$,} \\ 1, & \text{ha $1/4 \le x \le 1$,} \end{cases} \qquad f_2(x) = x, \qquad f_3(x) = x^3$$ Legyen a legjobboldalabbi kiosztott intervallum az $[a,1)$. Mennyi az $a$ értéke és ki kapja ezt az intervallumot?

Megoldás

A Fink-eljárás menete:

A második körben az 1. játékos két a saját értékelő függvénye szerint egyforma részre oszt:

Keressük azt az $x$-et, ahol $$\mu_1([0,x)) = \mu_1([x,1)) = \frac{1}{2}$$.

Az 1. játékosnak az $\left[\frac{1}{4},1\right)$ intervallum semmit nem ér, így a felezéshez $x \lt \frac{1}{4}$ kell:

$$f_1(x) - f_1(0) = 4x = \frac{1}{2} \\ x = \frac{1}{8}$$

Az 1. játékos részei: $\left[0, \frac{1}{8}\right)$ és $\left[\frac{1}{8}, 1\right)$.

A második játékos értékelő függvénye lineáris, tehát ő a hosszabbik intervallumot, az $\left[\frac{1}{8}, 1\right)$-ot szereti, ez neki $\frac{7}{8}$-ot ér.

A feladat kérdésének a megválaszolásához a harmadik körben csak azt kell megnézni, hogy a 2. játékos mit csinál az $\left[\frac{1}{8}, 1\right)$ intervallumon.

Mivel a 2. játékos értékelő függvénye lineáris, ezért a harmadoló pontjai éppen az intervallumok hossza szerint harmadolnak, ezek az $$\frac{1}{8} + \frac{1}{3}\cdot\frac{7}{8} = \frac{5}{12}$$ és az $$\frac{1}{8} + \frac{2}{3}\cdot\frac{7}{8} = \frac{17}{24}$$.

A 2. játékos részei: $\left[\frac{1}{8}, \frac{5}{12}\right)$, $\left[\frac{5}{12}, \frac{17}{24}\right)$, $\left[\frac{17}{24}, 1\right)$

A 3. játékos értékelése a 2. játékos által ajánlott részekre: $$\begin{aligned} \mu_3\left(\left[\frac{1}{8}, \frac{5}{12}\right)\right) &= \left(\frac{5}{12}\right)^3 - \left(\frac{1}{8}\right)^3 = \frac{125}{1728} - \frac{1}{512} \approx 0.0704 \\ \mu_3\left(\left[\frac{5}{12}, \frac{17}{24}\right)\right) &= \left(\frac{17}{24}\right)^3 - \left(\frac{5}{12}\right)^3 \approx 0.3554 - 0.0723 \approx 0.2831 \\ \mu_3\left(\left[\frac{17}{24}, 1\right)\right) &= 1^3 - \left(\frac{17}{24}\right)^3 \approx 1 - 0.3604 \approx 0.6396 \end{aligned}$$ Innen a $\left[\frac{17}{24}, 1\right)$ részt választja, tehát a feladat kérdésére a válasz $a=\frac{17}{24}$ és ezt a 3. játékos kapja.

Ha valakit érdekel, a végső szétosztás:

$$\begin{aligned} A_1 &= \left[0, \frac{1}{24}\right) \cup \left[\frac{1}{24}, \frac{1}{12}\right) = \left[0, \frac{1}{12}\right) \\ A_2 &= \left[\frac{1}{8}, \frac{5}{12}\right) \cup \left[\frac{5}{12}, \frac{17}{24}\right) = \left[\frac{1}{8}, \frac{17}{24}\right) \\ A_3 &= \left[\frac{1}{12}, \frac{1}{8}\right) \cup \left[\frac{17}{24}, 1\right) \end{aligned}$$

3. feladat

Három játékos osztozkodik a $[0,1)$ intervallumon a Tasnádi-eljárással. A játékosok értékelő eloszlásfüggvénye a következő. Hajtsuk végre a rekurzív algoritmus legkülső függvényhívását: a belső rekurzív hívásokat ne hajtsuk végre, csak adjuk meg milyen paraméterekkel hívja őket a külső hívás.

a) $f_1(x) = x$, $\displaystyle f_2(x) = \begin{cases} x/2, & 0 \le x \le 1/2 \\ (3x - 1)/2, & 1/2 \le x \le 1 \end{cases}$, $\displaystyle f_3(x) = \begin{cases} 2x, & 0 \le x \le 1/4 \\ (2x + 1)/3, & 1/4 \le x \le 1 \end{cases}$

Hint

Tasnádi-eljárás: Rekurzív protokoll. Az első játékos a saját értékelő függvénye szerint $n$ egyforma részre osztja az elosztandó halmazt, és mind az $n$ részhez előkészít $n-1$ darab jegyet. A többi játékos mindegyike elvesz $n-1$ darab különböző jegyet, kihagyva a saját értékelő függvénye szerinti egyik legrosszabbat. A fennmaradó $n-1$ darab jegyet az első játékos kapja. Ezután az $n$ rész mindegyikén $n-1$ játékos osztozkodik tovább a Tasnádi-eljárással, ebben az első játékos megfelelő multiplicitással vesz részt.

Megoldás

A Tasnádi-eljárás menete:

1. szint: Az 1. játékos három a saját értékelő függvénye szerint egyforma részre osztja a $[0,1)$ intervallumot:

Keressük $a$ és $b$ értéket, ahol $$\mu_1([0,a)) = \mu_1([a,b)) = \mu_1([b,1)) = \frac{1}{3}$$

$$f_1(a) - f_1(0) = a = \frac{1}{3}$$ $$f_1(b) - f_1(a) = b - \frac{1}{3} = \frac{1}{3} \\ b = \frac{2}{3}$$

Az 1. játékos részei: $R_1 = \left[0, \frac{1}{3}\right)$, $R_2 = \left[\frac{1}{3}, \frac{2}{3}\right)$, $R_3 = \left[\frac{2}{3}, 1\right)$.

Minden részhez 2-2 jegy tartozik: $(R_1, R_1)$, $(R_2, R_2)$, $(R_3, R_3)$.

Jegyválasztás:

A 2. játékos értékelése:

$$\begin{aligned} \mu_2(R_1) &= \mu_2\left(\left[0, \frac{1}{3}\right)\right) = \frac{1/3}{2} = \frac{1}{6} \\ \mu_2(R_2) &= \mu_2\left(\left[\frac{1}{3}, \frac{2}{3}\right)\right) = \frac{3 \cdot 2/3 - 1}{2}-\frac{1/3}{2} = \frac{1}{3} \\ \mu_2(R_3) &= \mu_2\left(\left[\frac{2}{3}, 1\right)\right) = 1 - \frac{3 \cdot \frac{2}{3} - 1}{2} = \frac{1}{2} \end{aligned}$$

A 2. játékos az $R_3$-ra és az $R_2$-re vesz jegyet.

A 3. játékos értékelése:

$$\begin{aligned} \mu_3(R_1) &= \mu_3\left(\left[0, \frac{1}{3}\right)\right) = \frac{2 \cdot \frac{1}{3} + 1}{3} = \frac{5}{9} \\ \mu_3(R_2) &= \mu_3\left(\left[\frac{1}{3}, \frac{2}{3}\right)\right) = \frac{2 \cdot \frac{2}{3} + 1}{3} - \frac{2 \cdot \frac{1}{3} + 1}{3} = \frac{7}{9} - \frac{5}{9} = \frac{2}{9} \\ \mu_3(R_3) &= \mu_3\left(\left[\frac{2}{3}, 1\right)\right) = 1 - \frac{2 \cdot \frac{2}{3} + 1}{3} = 1 - \frac{7}{9} = \frac{2}{9} \end{aligned}$$

A 3. játékos az $R_1$-re biztosan vesz jegyet, a másik kettő közül pedig tetszőlegeset választ. Válassza az $R_2$-t.

Tehát a rekurzív hívások a következőképpen alakulnak:

Ha valakit érdekel, a végső szétosztás:

$$\begin{aligned} A_1 &= \left[0, \frac{1}{6}\right) \cup \left[\frac{5}{6}, 1\right) \\ A_2 &= \left[\frac{5}{9}, \frac{2}{3}\right) \cup \left[\frac{2}{3}, \frac{5}{6}\right) = \left[\frac{5}{9}, \frac{5}{6}\right) \\ A_3 &= \left[\frac{1}{6}, \frac{1}{3}\right) \cup \left[\frac{1}{3}, \frac{5}{9}\right) = \left[\frac{1}{6}, \frac{5}{9}\right) \end{aligned}$$

b) $f_1(x) = x$, $f_2(x) = x^2$, $f_3(x) = x^4$

Megoldás

A Tasnádi-eljárás menete:

1. szint: Az 1. játékos három a saját értékelő függvénye szerint egyforma részre osztja a $[0,1)$ intervallumot:

Keressük $a$ és $b$ értéket, ahol $$\mu_1([0,a)) = \mu_1([a,b)) = \mu_1([b,1)) = \frac{1}{3}$$

$$f_1(a) - f_1(0) = a = \frac{1}{3}$$ $$f_1(b) - f_1(a) = b - \frac{1}{3} = \frac{1}{3} \\ b = \frac{2}{3}$$

Az 1. játékos részei: $R_1 = \left[0, \frac{1}{3}\right)$, $R_2 = \left[\frac{1}{3}, \frac{2}{3}\right)$, $R_3 = \left[\frac{2}{3}, 1\right)$.

Minden részhez 2-2 jegy tartozik: $(R_1, R_1)$, $(R_2, R_2)$, $(R_3, R_3)$.

Jegyválasztás:

A 2. játékos értékelése:

$$\begin{aligned} \mu_2(R_1) &= \mu_2\left(\left[0, \frac{1}{3}\right)\right) = \left(\frac{1}{3}\right)^2 = \frac{1}{9} \\ \mu_2(R_2) &= \mu_2\left(\left[\frac{1}{3}, \frac{2}{3}\right)\right) = \left(\frac{2}{3}\right)^2 - \left(\frac{1}{3}\right)^2 = \frac{4}{9} - \frac{1}{9} = \frac{3}{9} = \frac{1}{3} \\ \mu_2(R_3) &= \mu_2\left(\left[\frac{2}{3}, 1\right)\right) = 1^2 - \left(\frac{2}{3}\right)^2 = 1 - \frac{4}{9} = \frac{5}{9} \end{aligned}$$

A 2. játékos az $R_3$-ra és az $R_2$-re vesz jegyet.

A 3. játékos értékelése:

$$\begin{aligned} \mu_3(R_1) &= \mu_3\left(\left[0, \frac{1}{3}\right)\right) = \left(\frac{1}{3}\right)^4 = \frac{1}{81} \\ \mu_3(R_2) &= \mu_3\left(\left[\frac{1}{3}, \frac{2}{3}\right)\right) = \left(\frac{2}{3}\right)^4 - \left(\frac{1}{3}\right)^4 = \frac{16}{81} - \frac{1}{81} = \frac{15}{81} = \frac{5}{27} \\ \mu_3(R_3) &= \mu_3\left(\left[\frac{2}{3}, 1\right)\right) = 1^4 - \left(\frac{2}{3}\right)^4 = 1 - \frac{16}{81} = \frac{65}{81} \end{aligned}$$

A 3. játékos az $R_3$-ra és az $R_2$-re vesz jegyet.

Váltott jegyek tehát:

Tehát a rekurzív hívások a következőképpen alakulnak:

Ha valakit érdekel, a végső szétosztás:

$$\begin{aligned} A_1 &= \left[0, \frac{1}{3}\right) \\ A_2 &= \left[\frac{1}{3}, \frac{\sqrt{10}}{6}\right) \cup \left[\frac{2}{3}, \frac{\sqrt{26}}{6}\right) \\ A_3 &= \left[\frac{\sqrt{10}}{6}, \frac{2}{3}\right) \cup \left[\frac{\sqrt{26}}{6}, 1\right) \end{aligned}$$

4. feladat

Három játékos osztozkodik a $[0,1)$ intervallumon a diszkrét mozgó késes eljárással. A játékosok értékelő eloszlásfüggvénye a következő. Legyen a legbaloldalabbi kiosztott intervallum a $[0,b)$. Mennyi a $b$ értéke és ki kapja ezt az intervallumot?

a) $f_1(x) = x$, $f_2(x) = x^2$, $f_3(x) = x^4$

Hint

Diszkrét mozgó késes eljárás: Minden játékos megjelöli a saját értékelő függvénye szerint azt a legkisebb $[0, x)$ intervallumot, ami neki $\frac{1}{n}$-et ér. A legbaloldalibb jelölővel rendelkező játékos megkapja a kért szeletét, a többi játékos a megmaradt intervallumon folytatja az eljárást.

Megoldás

A diszkrét mozgó késes eljárás menete:

1. kör: Minden játékos megjelöli azt a legkisebb $[0,x)$ intervallumot, ami neki $\frac{1}{3}$-ot ér.

Az 1. játékos jelölése:

$$\mu_1([0,x_1)) = \frac{1}{3}$$ $$f_1(x_1) = x_1 = \frac{1}{3} \approx 0.3333$$

A 2. játékos jelölése:

$$\mu_2([0,x_2)) = \frac{1}{3}$$ $$f_2(x_2) = x_2^2 = \frac{1}{3}$$ $$x_2 = \sqrt{\frac{1}{3}} = \approx 0.5774$$

A 3. játékos jelölése:

$$\mu_3([0,x_3)) = \frac{1}{3}$$ $$f_3(x_3) = x_3^4 = \frac{1}{3}$$ $$x_3 = \sqrt[4]{\frac{1}{3}} = \approx 0.7598$$

A legbaloldalibb jelölés az 1. játékosé, tehát ő kapja meg a $\left[0, \frac{1}{3}\right)$ intervallumot. Azaz a feladat kérdésére a válasz $b=\frac{1}{3}$ és az 1. játékos kapja az intervallumot.

Ha valakit érdekel, a végső szétosztás:

$$\begin{aligned} A_1 &= \left[0, \frac{1}{3}\right) \\ A_2 &= \left[\frac{1}{3}, \frac{\sqrt{5}}{3}\right) \\ A_3 &= \left[\frac{\sqrt{5}}{3}, 1\right) \end{aligned}$$

b) $f_1(x) = x$, $f_2(x) = x^2$, $f_3(x) = \sqrt{x}$

Megoldás

A diszkrét mozgó késes eljárás menete:

1. kör: Minden játékos megjelöli azt a legkisebb $[0,x)$ intervallumot, ami neki $\frac{1}{3}$-ot ér.

Az 1. játékos jelölése:

$$\mu_1([0,x_1)) = \frac{1}{3}$$ $$f_1(x_1) = x_1 = \frac{1}{3} \approx 0.3333$$

A 2. játékos jelölése:

$$\mu_2([0,x_2)) = \frac{1}{3}$$ $$f_2(x_2) = x_2^2 = \frac{1}{3}$$ $$x_2 = \sqrt{\frac{1}{3}} \approx 0.5774$$

A 3. játékos jelölése:

$$\mu_3([0,x_3)) = \frac{1}{3}$$ $$f_3(x_3) = \sqrt{x_3} = \frac{1}{3}$$ $$x_3 = \left(\frac{1}{3}\right)^2 = \frac{1}{9} \approx 0.1111$$

A legbaloldalibb jelölés a 3. játékosé, tehát ő kapja meg a $\left[0, \frac{1}{9}\right)$ intervallumot. Azaz a feladat kérdésére a válasz $b=\frac{1}{9}$ és a 3. játékos kapja az intervallumot.

Ha valakit érdekel, a végső szétosztás:

$$\begin{aligned} A_1 &= \left[\frac{1}{9}, \frac{5}{9}\right) \\ A_2 &= \left[\frac{5}{9}, 1\right) \\ A_3 &= \left[0, \frac{1}{9}\right) \end{aligned}$$

5. feladat

Öt játékos osztozkodik a $[0,1)$ intervallumon az Even-Paz eljárással. A játékosok értékelő eloszlásfüggvénye a következő. $$f_1(x) = x, \qquad f_2(x) = x^2, \qquad f_3(x) = \sqrt{x}, \qquad f_4(x) = x^4, \qquad f_5(x) = \min (2x,1)$$ Hajtsuk végre a rekurzív algoritmus legkülső függvényhívását: a belső rekurzív hívásokat ne hajtsuk végre, csak adjuk meg milyen paraméterekkel hívja őket a külső hívás.

Hint

Even-Paz-eljárás: Oszd meg és uralkodj elvű protokoll. Minden játékos megjelöli a saját értékelő függvénye szerinti $\lfloor n/2 \rfloor : \lceil n/2 \rceil$ vágópontot. A játékosokat a jelölőik szerinti növekvő sorrendbe rendezzük (az egyenlőséget véletlenszerűen feloldva) és az első $\lfloor n/2 \rfloor$ játékost balra, a maradék $\lceil n/2 \rceil$ játékost pedig jobbra küldjük. Az intervallumot a balra küldött játékosok maximális jelölőjénél vágjuk, a bal oldali részen a balra küldött játékosok, a jobb oldalin pedig a jobbra küldöttek osztozkodnak tovább, szintén az Even-Paz-eljárással.

Megoldás

Az Even-Paz-eljárás menete:

1. szint: Minden játékos megjelöli a saját értékelő függvénye szerinti $\lfloor 5/2 \rfloor : \lceil 5/2 \rceil = 2:3$ vágópontot.

Az 1. játékos jelölése ($\mu_1([0,x)) = \frac{2}{5}$):

$$f_1(x_1) = x_1 = \frac{2}{5}$$

A 2. játékos jelölése ($\mu_2([0,x)) = \frac{2}{5}$):

$$f_2(x_2) = x_2^2 = \frac{2}{5}$$ $$x_2 = \sqrt{\frac{2}{5}} \approx 0.6325$$

A 3. játékos jelölése ($\mu_3([0,x)) = \frac{2}{5}$):

$$f_3(x_3) = \sqrt{x_3} = \frac{2}{5}$$ $$x_3 = \left(\frac{2}{5}\right)^2 = \frac{4}{25} = 0.16$$

A 4. játékos jelölése ($\mu_4([0,x)) = \frac{2}{5}$):

$$f_4(x_4) = x_4^4 = \frac{2}{5}$$ $$x_4 = \sqrt[4]{\frac{2}{5}} \approx 0.7952$$

Az 5. játékos jelölése ($\mu_5([0,x)) = \frac{2}{5}$):

$$f_5(x_5) = \min(2x_5, 1) = \frac{2}{5}$$ $$2x_5 = \frac{2}{5}$$ $$x_5 = \frac{1}{5}$$

Rendezzük a játékosokat jelölőik szerint növekvő sorrendbe:

$$x_3 = 0.16 < x_5 = 0.2 < x_1 = 0.4 < x_2 \approx 0.6325 < x_4 \approx 0.7952$$

Az első $\lfloor 5/2 \rfloor = 2$ játékost balra küldjük: 3. és 5. játékos

A maradék $\lceil 5/2 \rceil = 3$ játékost jobbra küldjük: 1., 2. és 4. játékos

Vágópont: a balra küldöttek maximális jelölője, azaz $\max(x_3, x_5) = x_5 = \frac{1}{5}$.

Tehát a rekurzív hívások a következőképpen alakulnak:

Ha valakit érdekel, a végső szétosztás:

$$\begin{aligned} A_1 &= \left[\frac{1}{5}, \frac{7}{15}\right) \\ A_2 &= \left[\frac{7}{15}, \frac{\sqrt{137}}{15}\right) \\ A_3 &= \left[0, \frac{1}{20}\right) \\ A_4 &= \left[\frac{\sqrt{137}}{15}, 1\right) \\ A_5 &= \left[\frac{1}{20}, \frac{1}{5}\right) \end{aligned}$$

6. feladat

Négy játékos osztozkodik a $[0,1)$ intervallumon az Even-Paz eljárással. A játékosok értékelő eloszlásfüggvénye a következő. $$f_1(x) = \sqrt[5]{x}, \qquad f_2(x) = \sqrt[3]{x}, \qquad f_3(x) = x^2, \qquad f_4(x) = x$$ Legyen a legbaloldalabbi kiosztott intervallum a $[0,c)$. Mennyi a $c$ értéke és ki kapja ezt az intervallumot?

Megoldás

Az Even-Paz-eljárás menete:

1. szint: Minden játékos megjelöli a saját értékelő függvénye szerinti $\lfloor 4/2 \rfloor : \lceil 4/2 \rceil = 2:2$ vágópontot.

Az 1. játékos jelölése ($\mu_1([0,x)) = \frac{1}{2}$):

$$f_1(x_1) = \sqrt[5]{x_1} = \frac{1}{2}$$ $$x_1 = \left(\frac{1}{2}\right)^5 = \frac{1}{32}$$

A 2. játékos jelölése ($\mu_2([0,x)) = \frac{1}{2}$):

$$f_2(x_2) = \sqrt[3]{x_2} = \frac{1}{2}$$ $$x_2 = \left(\frac{1}{2}\right)^3 = \frac{1}{8}$$

A 3. játékos jelölése ($\mu_3([0,x)) = \frac{1}{2}$):

$$f_3(x_3) = x_3^2 = \frac{1}{2}$$ $$x_3 = \sqrt{\frac{1}{2}} = \frac{1}{\sqrt{2}} = \frac{\sqrt{2}}{2} \approx 0.7071$$

A 4. játékos jelölése ($\mu_4([0,x)) = \frac{1}{2}$):

$$f_4(x_4) = x_4 = \frac{1}{2}$$

Rendezzük a játékosokat jelölőik szerint növekvő sorrendbe:

$$x_1 = \frac{1}{32} = 0.03125 < x_2 = \frac{1}{8} = 0.125 < x_4 = \frac{1}{2} < x_3 \approx 0.7071$$

Az első $\lfloor 4/2 \rfloor = 2$ játékost balra küldjük: 1. és 2. játékos

A maradék $\lceil 4/2 \rceil = 2$ játékost jobbra küldjük: 3. és 4. játékos

Vágópont: a balra küldöttek maximális jelölője, azaz $\max(x_1, x_2) = x_2 = \frac{1}{8}$

2. szint, bal oldal: Az 1. és a 2. játékos osztozkodik a $\left[0, \frac{1}{8}\right)$ intervallumon.

Mindkét játékos megjelöli a saját értékelő függvénye szerinti $\lfloor 2/2 \rfloor : \lceil 2/2 \rceil = 1:1$ vágópontot.

Az 1. játékos jelölése $\mu_1([0,x)) = \mu_1\left(\left[0,\frac{1}{8}\right)\right) \cdot \frac{1}{2}$:

$$\mu_1\left(\left[0,\frac{1}{8}\right)\right) = \sqrt[5]{\frac{1}{8}} = \frac{1}{\sqrt[5]{8}} = \frac{1}{2^{3/5}}$$ $$\sqrt[5]{x} = \frac{1}{2^{3/5}} \cdot \frac{1}{2} = \frac{1}{2^{8/5}}$$ $$x = \frac{1}{2^8} = \frac{1}{256}$$

A 2. játékos jelölése $\mu_2([0,x)) = \mu_2\left(\left[0,\frac{1}{8}\right)\right) \cdot \frac{1}{2}$:

$$\mu_2\left(\left[0,\frac{1}{8}\right)\right) = \sqrt[3]{\frac{1}{8}} = \frac{1}{2}$$ $$\sqrt[3]{x} = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$$ $$x = \frac{1}{64}$$

Mivel $x_1 = \frac{1}{256} < x_2 = \frac{1}{64}$, az 1. játékos megy balra, a 2. játékos jobbra.

Vágópont: $\frac{1}{256}$

Az 1. játékos kapja: $\left[0, \frac{1}{256}\right)$

A 2. játékos kapja: $\left[\frac{1}{256}, \frac{1}{8}\right)$

Tehát a legbaloldalabbi kiosztott intervallum a $\left[0, \frac{1}{256}\right)$, azaz $c=\frac{1}{256}$ és ezt az 1. játékos kapja.

Ha valakit érdekel, a végső szétosztás:

$$\begin{aligned} A_1 &= \left[0, \frac{1}{256}\right) \\ A_2 &= \left[\frac{1}{256}, \frac{1}{8}\right) \\ A_3 &= \left[\frac{9}{16}, 1\right) \\ A_4 &= \left[\frac{1}{8}, \frac{9}{16}\right) \end{aligned}$$

7. feladat

Három játékos osztozkodik a $[0,1)$ intervallumon irigységmentesen a Selfridge-Conway-eljárással. A játékosok értékelő eloszlásfüggvénye a következő. $$f_A(x) = \sqrt{x}, \qquad f_B(x) = \min(2x,1), \qquad f_C(x) = x^2$$ Mi lesz a szétosztás eredménye?

Hint

Selfridge-Conway eljárás: Irigységmentes elosztás három játékosra ($A$, $B$, $C$). Az $A$ harmadol, a $B$ a darabokat sorrendezi és ha van legnagyobb akkor azon igazít: levág belőle annyit, hogy ugyanakkora legyen mint a következő. A levágott maradékot félreteszik. A három fő darabból $C$, $B$, $A$ sorrendben választanak egyet-egyet, de $B$-t megkérjük, hogy ha teheti, akkor az igazítottat előzékenyen ő vigye el (neki ez egy legjobb szelet), ne maradjon az $A$-ra. Ha $C$ viszi el az igazítottat, akkor a maradékot $B$ harmadolja és $C,A,B$ sorrendben osztoznak. Egyébként a $B$ viszi el az igazítottat, ekkor a maradékot a $C$ harmadolja és azokon $B,A,C$ sorrendben osztoznak.

Megoldás A szétosztás eredménye:

8. feladat

Adjunk eljárást arra az esetre, amikor az $n$ játékos nem egyenlő mértékben akar osztozni a $[0,1)$ intervallumon, hanem minden $i \in \{1, \ldots, n\}$ esetén az $i$-edik játékoshoz adott egy $d_i \in \mathbb{Z}_+$ követelés, és olyan $(A_1, \ldots, A_n)$ elosztást keresünk, melyre tetszőleges $i \in \{1, \ldots, n\}$ esetén $\mu_i(A_i) \ge d_i / D$ teljesül, ahol $D \coloneqq \sum_{i=1}^n d_i$.

Hint

Klónozzuk a játékosokat.

Megoldás

Készítsünk $d_i$ darab klónt az i. játékosból és osztoszkodjunk bármelyik eljárás, például az Even-Paz használatával. A klónok arányosan osztoznak, tehát mindenki legalább $\frac{1}{D}$ részesedést kap a saját értékelő függvénye szerint. Az eredeti játékos a végén a klónjai részét kapja meg, ezért legalább $\frac{d_i}{D}$ értékű részt kap.

9. feladat

ZH 2024, *-os feladat: A $[0, 1)$ intervallumon szeretne irigységmentesen osztozkodni $n$ játékos (ahol $n$ tetszőleges pozitív egész szám). Tudjuk, hogy az első $n-1$ játékos értékelő eloszlásfüggvénye azonos, azaz $f_1 = \dots = f_{n-1}$, az $n$-edik játékoséról viszont nem tudunk semmit. Javasoljunk hatékony algoritmust a feladat megoldására, és határozzuk meg az eljárás végrehajtásához szükséges mérés- és vágás műveletek számát.

Hint

Az osztó és az elsőnek választó játékos biztosan nem lesznek irigyek senkire.

Megoldás

Ossza fel az első játékos a $[0,1)$ intervallumot számára $n$ egyforma értékű részre, ezt $(n-1)$ darab vágással meg tudja tenni. Mérje meg ezeket az $n$-edik játékos és válasszon közülük egyet, ehhez $(n-1)$ darab mérésre van szüksége. A többiek ezután tetszőleges sorrendben választanak egy-egy darabot. Ekkor az $n$-edik játékos nem lehet irigy, hiszen ő választhatott először. A többiek sem lehetnek irigyek, hiszen számukra minden rész egyforma értékű.

Megjegyzés: Az osztozkodási feladatban feltételezzük, hogy mindenki igazat mond. Ha valaki szeretne olyan protokollt készíteni, ami hazug, de racionális játékosokra is működik, akkor ahhoz annyit kell módosítani az előzőkön, hogy kikötjük hogy az osztó játékos választ utoljára. Ekkor az osztó játékos a saját nyereségét szeretné maximalizálni, ehhez pedig számára egyenlő értékű részekre kell osztania.

10. feladat

Adjunk eljárást arra az esetre, amikor az $n$ játékos úgy akar osztozni a $[0,1)$ intervallumon, hogy tetszőleges $i \in \{1, \ldots, n\}$ esetén $\mu_i(A_i) \le 1/n$ teljesüljön (azaz például torta helyett házimunkán osztoznak a játékosok).

(Pöttyös feladat.)

11. feladat

Vegyük az osztozkodási játék diszkrét változatát: $n \in \mathbb{N}_+$ darab játékos osztozik a $[0,1)$ intervallumon oly módon, hogy $k$ darab, előre megadott $0 < p_1 < \dots < p_k < 1$ osztópontban vághatnak, ahol $n-1 \leq k$. Lássuk be, hogy ebben a játékban annak az eldöntése, hogy létezik-e arányos elosztás egy NP-teljes feladat.

(Pöttyös feladat.)