Wednesday, 18 April 2018

Division of a Huge Cake: An Interesting Mathematical Puzzle

Mathematical puzzles are addictive and lately, my addiction to them has become quite strong.  The ones I like most are those that have some unexpected outcome and, of course, they also should require some struggle to find the solution.  

Division of a Huge Cake is a puzzle which was published in The Guardian a few years ago.  I thought the published solution of the puzzle did not quite do the justice to the beautiful and somewhat counter-intuitive outcome.  This encouraged me to write this blog - hope you enjoy the discussion of the result.  

The puzzle is (reformulated by me): An eccentric duke throws a big party for 100 of his good friends.  He wishes to give bigger portions of the cake to some of his selected important guests who are served first.  The duke concocts a strange (or shall we say eccentric) formula for dividing the cake  
The first guest gets 1% of the cake.  
The second guest gets 2% of the remaining part.  
The third guest gets 3% of the part remaining and so on...  .  
The 50th guest gets 50% of the part left, and 
the 100th guest gets 100% of whatever is left.
Who gets the biggest piece and how much does he get?  Did the duke achieve what he wanted?
Is this a good way to divide the cake?

Solution:  As the guests are served their share of the cake, the amount remaining gets progressively smaller and even though they are taking a bigger percentage of the remaining cake, after a certain stage the size of the serving starts to get smaller.  One of the guests will get the biggest piece and we need to work it out by using some algebra:

Let us say that for guest number the amount of cake left is a fraction P of the original size.  
Guest N will get N% of this; that is - Guest N receives a portion = p x N/100 
After guest N has had his portion, 
the cake left is equal to   P - P x N/100  = P (1 - N/100)
The next guest (number N+1) will take (N+1)% of this remaining size i.e., 
his share will be  (N+1)/100 x P (1 - N/100)

The question is - for what value of N,  the share that guest number (N+1) receives is smaller than the share taken by guest number N?  
Put it another way, we want to find out for what N, the following relation is true:

(N+1)/100 x P (1 - N/100) - P x N/100 < 0

Multiply by 10,000 and divide by P to get:

(N + 1) x (100 - N) - 100 x N < 0 

OR   N x 100 + 100 - N^2 - N - 100 x N < 0

OR   N^2 + N > 100

Equation in red tells us that when N is large enough for the inequality to hold, subsequent guests will get a smaller portion than the previous guest.

Obviously for N less than or equal to 9, the left hand side is smaller than 100; but for N = 10, the left hand side is 110 and is greater than 100.  
One can use a spreadsheet to work out the portion of the cake that each guest receives.  This is shown in the slide below (click on slide to see full page image)

Guest number 10 will receive the biggest slice of the cake and he will receive 6.28% of the initial cake.

Notice that under this plan, guest 30 onwards receive very little cake - guest 32 only receives 0.1% of the cake. Interestingly, guests number 85 onwards receive less than a molecule of the cake - there is no cake left for them to share.

Is there a more equitable way of dividing the cake?  The problem with the duke's method is that the portions served in the beginning are too large.  Consider a 10 kg cake with an average serving of 100 g per guest.  In duke's method, guest number 10 will receive 628 g portion!  
This situation may be moderated by modifying the formula by which the guests receive their portions as the fourth root of their number - Nth guest receives N^0.25 percents of the remaining cake and not N% as suggested by the duke.
If we follow this recipe then the distribution of portions is as shown: 
This method gives a reasonable distribution of cake portions and meets the duke's wishes of serving larger portions to his important guests.  The portion sizes vary from 0.263% for guest 99 to a maximum of 1.576% for guest 13.  The cake remaining is 8.1% after all guests have been served.  

Post a Comment