11 marks] The Moving Knife algorithm is used, as described in GTa.12, to divide

Question

11 marks] The Moving Knife algorithm is used, as described in GTa.12, to divide a cake among n people. Person P is the ith person to call Stop"and hence receives the ith piece cut. No one tries to be greedy (as discussed in GTa.14), and no two players call "Stop at the same time Method GTa.12 (Moving Knife for Proportional Division into n pieces) 1. A knife is passed over the cake from left to right. The first player who assesses the portion to the left of the knife at-says "Stop." is awarded that portion, and drops out. If two players simultaneously say "Stop." one is assigned the piece at random. 2. Repeat Step 1 with the remaining players on the remaining piece of cake. n. There is now one player left, who receives the remaining piece. Dubins and Spanier (cited from Robertson and Webb 1998, 8 Concept GTa.14 (Playing by the Rules) With the Moving Knife algorithm, any player who tries to be greedy risks losing out to a player who is slightly less greedy. Certainly, individuals may have a different tolerance for this risk, and they may feel they have skill at being just greedy enough" relative to others. We assume that players put this aside and go for exactly 7 a) 3 marks If n 3, what is the most we can say for sure about how P2 assesses the size of i. the first piece cut ii. the second piece cut ii the third piece cut? (b) 8 marks) Consider the statement: S,: The player who receive the ith piece assesses her piece as being the ith smallest If n 4, determine with justification whether the statement Si must be true e ust be false, or e could be either true or false. Repeat for S2, S3, S Note that if Christine assesses the pieces as 0.23, 0.25, 0.25, 0.27, then she considers bothe pieces bfno size 0.25 as the second smallest. Go to Settings to a

Explanation / Answer

a) As n=3, first person will say stop when he thinks that cake left side of knife is 1/3 of whole cake, and second person will also repeat the same. Therefore P2 will assess the size of first piece cut.

b) It is not true for n = 4, n=3, n=2 because each player will make sure that piece left on left side of knife is 1/n portion and each person will get same proportion cake but not the 4th smallest one.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.