How to divide the cake so that everyone is happy
There is a task - to divide a certain whole between several applicants and at the same time everyone should be satisfied. Moreover, it is not very convenient to run a pie in real living conditions - a pie, for example - with a ruler and compasses around it, and the whole is heterogeneous.
The first divides, the second chooses. Accordingly, the first tries to share equally, to subsequently rejoice at any share.
Why not remain dissatisfied? Because everyone has the full choice, while - lo and behold - not oppressing the neighbors. Almost 200% of freedom :-) With the decision of an external judge - the chosen person or fate during the draw - they can always disagree (at least internally), but here everyone participates in the fulfillment of their own destiny because they do something and not only accept someone else's verdict.
')
Alternative solutions and similar tasks are welcome.
a) N1 divides the cake into three parts as it can; and leaves the stage again.
b) N2 and N3 choose their piece. If their choice is different, this is where the division ends - N1 takes what remains.
c) (If both claim to be the same piece.) Now we need to get rid of some piece so that there are two of them left - throw off one number to the first.
d) So, there are two pieces and two bidders left. The task is reduced to the division "for two" two times. One piece cuts N1, chooses N2. The second piece is the opposite:
In the worst case, the cake is cut into 5 pieces.
This algorithm does not save from collusion between two of the three participants. Well, with a further increase in the number of people, whom organizational difficulties will grow in progression. I wonder if it is possible to improve these moments ...
For two
The first divides, the second chooses. Accordingly, the first tries to share equally, to subsequently rejoice at any share.
Philosophical idea
Why not remain dissatisfied? Because everyone has the full choice, while - lo and behold - not oppressing the neighbors. Almost 200% of freedom :-) With the decision of an external judge - the chosen person or fate during the draw - they can always disagree (at least internally), but here everyone participates in the fulfillment of their own destiny because they do something and not only accept someone else's verdict.
')
Alternative solutions and similar tasks are welcome.
For three (already more difficult)
a) N1 divides the cake into three parts as it can; and leaves the stage again.
b) N2 and N3 choose their piece. If their choice is different, this is where the division ends - N1 takes what remains.
c) (If both claim to be the same piece.) Now we need to get rid of some piece so that there are two of them left - throw off one number to the first.
Just letting the first pick your piece is impossible, in order to keep it from the temptation to cut the cake knowingly unevenly and get hold of the largest share, as a result,
N2 and N3 should choose what gets N1, as well as in the division "for two". Each of them now chooses a piece for N1. In the case of a consensus, N1 eats its own piece; otherwise, he chooses from the two proposed to him and again removes his share.
d) So, there are two pieces and two bidders left. The task is reduced to the division "for two" two times. One piece cuts N1, chooses N2. The second piece is the opposite:
In the worst case, the cake is cut into 5 pieces.
Further reading
This algorithm does not save from collusion between two of the three participants. Well, with a further increase in the number of people, whom organizational difficulties will grow in progression. I wonder if it is possible to improve these moments ...
Source: https://habr.com/ru/post/54536/
All Articles