Puzzle : Way to the heaven?

Hi,

So far this blog has been only about cake-cutting. Not that I am going to stop writing about that, but this blogs needs a little change. I remember a very old puzzle which involves logic.

Problem : One fine day, you find yourself dead ( not a very good opening line..eh? ). You start your journey in search of eternal peace and happiness or in other words, you start your journey to search heaven. After traveling for a long long time, you come across a huge gate. You also notice that there is a fork after the gate. One of the path leads to heaven and the other one leads to hell. Two guardians are guarding the gate. One of them is an angel and another is a demon ( or a knight and a knave etc etc ). Angel always speaks the truth and the demon always lies. You are supposed to ask only one question to only one of the guardian. Clearly, you want to go to heaven, so you would try to ask which path would go to heaven. However, given the constraint that you can ask only one question , how would you frame the question??

Solution : The question you would ask is : “If I ask the other guard about which side leads to heaven, what would he answer?”. It should be fairly easy to see that irrespective of whom do you ask this question, you will always get an answer which leads to hell. So you can chose the other path to continue your journey to heaven.

If you do not see how this works. Here is an explanation.

Without loss of generality, let us assume that the left path leads to heaven.

If you ask an angel about which path leads to heaven, as he speaks always the truth, he
would say “left”. Now that the demon always lies, when he is asked what “the other guard (angel) ” would answer, he would definitely say “right”.

Similarly, if you ask the demon about which path leads to heaven, he would say “right”. As the angel speaks nothing but the truth, he would say “right” when he is asked what “the other guard( demon ) ” would answer. So in any case, you would end up having the path to hell as an answer. So you can chose the other path as a way to heaven.

A very trivial puzzle eh? I know, many of us has come across this puzzle sometime. Ok, now try this one :

Problem : Similar to the puzzle above, one guard ( the angel ) always speaks the truth and the other guard ( the demon) always lies. The trouble is that none of them can speak, so they can only nod ( up-down movement of the head ) their head or shake ( left-right movement of the head ) the head. You do not know who is the angel and who is the demon. In addition to that, you even do not know whether a nod means a “yes” or a “no”. And again, you are allowed to ask only one question that would decide your fate for eternity. What would be your question?

I will post the solution to this problem in my next post. Till then, readers ( if any 🙂 ) can scratch their head.

–Saurabh Joshi

Cake Cutting Algorithm -4 : Trimming Algorithm

Hi All,

We have seen already in previous post why we need a better algorithm for simple fair division. Let us see a new algorithm for simple fair division for cake-cutting.

Let’s recall our good old friends Pinku, Rinku and Chinku. Pinku can cut a piece from the cake which he values at . Pinku will pass on this piece to Rinku to scrutinize it. If Rinku values at more than then Rinku will trim the piece to such that . This piece now will be further passed on to Chinku. Chinku can either take it or leave it.

So we have three cases :

Case 1 : Chinku takes the piece passed on to him. Clearly, . Pinku and Rinku can now play “Cut and Choose”. From Pinku’s point of view , so he will be happy to play “Cut and Choose” with the remaining piece. Same argument can be given for Rinku too. Note that, Rinku may or may not trim the cake in which case . If Rinku does not trim the cake, it means she believes that the rest of the cake is worth at least .

Case 2: Chinku leaves the piece trimmed by Rinku. In this case, Chinku and Pinku will play “Cut and Choose”. As Rinku has trimmed the piece, she will be happy to take it.

Case 3: Chinku leaves the piece which was passed on to him without Rinku trimming it. In this case, Pinku will take the piece as he originally valued it at . Remaining two will happily play “Cut and Choose” because both have chosen to leave the piece as they believe it not worth from their perspective.

Let’s now go on to generalize the algorithm.

Base case : n=1, Obviously true.

Induction hypothesis : Trimming algorithm divides the cake fairly amongst contenders.

Induction step : Let first contender cut a piece which he/she values at . Other contenders one by one will be offered the piece for trimming. Let be the last person to trim the piece. Finally, this piece arrives at who can either take it or leave.

Case 1 : takes the piece. By induction the other contender successfully divide the cake. is happy because he/she received a piece which he/she values at . Rest will be happy as they value rest of the cake to be at least .

Case 2: decides to leave the piece. In which case takes the piece and by induction they all lived happily ever after :-). Here can be also.

So it seems that we are able to divide the cake fairly between contenders. But does it actually improve on number of cuts required??? In the worst case, it will so happen that everyone will decide to trim the cake. In which case number of cuts required would be . This is a far better bound as compared to .

Did we manage to solve the problem?? Well, someone said, “People are not as miserable due to their own miseries as they are miserable due to others happiness”. One can clearly see that, even though the first person gets of the cake, he might find from his point of view that someone else received a more worthy piece then he/she already has.

This gives rise to a new problem:

Envy free cake-cutting : Divide a cake amongst people such that .

In simple words, people want a piece which is at least as big as others. So, the constraint is not only to divide the cake fairly, but also to make sure that everybody feels that he/she has got the biggest piece. We will look into this direction in the next post.

–Saurabh Joshi

Cake Cutting Algorithms – 3 : Moving Knife Algorithm

Hello all,

Last time we have looked at “Successive Pair Algorithm” for simple fair division of a cake. Let us look at a different algorithm now. Why would we require a different algorithm? Let us see.

In the successive pair algorithm, every time arrives we would require all pieces to be cut into equal pieces. Let total number of pieces required to divide a cake amongst candidates be denoted by ( it is a standard notation for time complexity calculation ). Therefore, total number of pieces would be :

Essentially, it indicates that if 10 candidates are contending for the cake, there will be 3,628,800 pieces at the end. Don’t you think it is a bit too much ? At the end, each candidate will have a fair share of cake powder :-). Certainly, we want a more elegant solution.

Let us see how following strategy works out for old friends Pinku, Rinku and Chinku :

Let the knife be at the leftmost end of the cake. Slowly but gradually shift the knife towards right. Whenever someone says “stop”, we will make a cut there and give the piece to the left of the knife to that person. For the remaining portion, we will play “Cut and Choose” as we only have two contenders left. Why does this strategy works??

Well, assume for example that Pinku is the first one to say “stop”. Let the piece to the left of the knife be denoted by for the first time, for the second time and so on. Clearly, Pinku is smart enough to say “stop” only when . Chinku and Rinku did not bother to say “stop” implies that . Both Chinku and Rinku believes that the remaining piece is at least . Chinku and Rinku will play “Cut and Choose” or rather “I cut you choose” to get their fair share.

This strategy can be extended for contenders. Whether it works or not, can easily be shown by mathematical induction.

Base case : For n=1 it is fairly trivial.

Hypothesis : Assume this stretagy works for contenders.

Induction Step : As we argued earlier, the first person to say “stop” believes that the cake is worth at least and others believe that the rest of the cake is worth at least . The first person is given his/her share to his/her satisfaction. For the remaining persons, the rest of the cake is fairly divided .

This algorithm is called “Moving Knife Algorithm”. It generates exactly pieces with cuts. Still, I would say this algorithm is not good enough. It is obvious that one would require minimum of cuts to divide a cake into pieces, so where is the problem? If you look at this algorithm carefully, you would find out that this algorithm requires all contenders to make decision at each and every point while the knife is on move. If we denote the leftmost point of the cake as 0 and the rightmost point as 1, we will have infinitely many possible values in between. In short, this algorithm is an infinite step algorithm. Even though, this algorithm can work quite well in practice, it does not work well in theory. ( This is a strange example where something works in practice but not in theory :-). In practice, a person has a limitation in measuring, or in simpler words, we would not be able to tell a difference whether the knife is 3.7889213 cm away or 3.7889214 cm away ).

So, even though this is probably the most optimal solution practically, we need better finite step algorithms. We shall see later some of those.

–Saurabh Joshi

Cake Cutting Algorithms – 2

Well,

In the last post we have seen how can we have a fair share division of a cake for two contenders. However, life is not as simple as we believe it to be.

Let’s introduce a new character to our drama. Chinku joins in the party so he also need a fair share of the cake. What do we do now? Let us try examining possible solutions one by one.

Method 1:

Let’s assume that Pinku and Rinku already have their fair share. When Chinku joins in, the cake has to be divided in a way so as to make everyone believe that they got 1/3rd of the cake. We can let Chinku take 1/3rd piece from Pinku as well as Rinku’s share.

This method will fail for obvious reason because Chinku’s evaluation of a piece may differ from that of Pinku and Rinku’s.

Method 2:

Actually, we can again play Cut and Choose with a bit of modification. Let Pinku and Rinku divide their respective pieces into 3 equal pieces ( from Pinku’s perspective, similarly from Rinku’s perspective). and Let Chinku choose one piece from and one piece from .

It is clear that with such a strategy Pinku as well as Rinku will be satisfied. Because and same can be argued for . Now, we need to see whether Chinku will get a fair share or not. Because, Chinku is the chooser, he will choose a piece and . Chinku will get a fair share because

Okay, so far so good. What will we do if Dinku joins the party??? We can go on and on about adding more and more contenders. So let us generalize this algorithm.

1. Assume cake is divided fairly amongst persons. Obviously, for he/she has the whole cake.
2. When person joins, let everyone but divide his/her share into equal pieces from their perspective.
3. Let choose one piece from each person ‘s share.
4. is happy because he/she originally had share and after the new person takes one piece he/she has
5. 
6. Person is happy because he has

The above mentioned algorithm is called “Successive pair algorithm”. In the next post, we will look at more algorithms for fair share division where more than two contenders are involved.