Special Cake Division Method that Makes Everyone Extra Happy


The following theorem was found from an interesting book called "A Mathematical Plum" by Honsberger. The theorem guarantees that some linear combination of matrices, whose sum of all the elements equals to unity results in another matrix of the same kind, if the sum of linear indices equal to unity. The proof of the theorem is straightforward.

Lyapunov's Theorem
Suppose we denote a set S of all matrices M(C) whose elements Mij C, where C represents the complex space. Also let S only contains special matrices that Σ Mij = 1. Now consider a linear combination of k matrices from a set S, L(M) = λ1M1 + λ2M2 + … + λkMk.

Then the components of L(M) are expressed as,

L(M)ij= λ1(M1)ij + λ2(M2)ij + … + λk(Mk)ij
So Σ L(M)ij = λ1Σ (M1)ij + λ2Σ (M2)ij + … + λkΣ (Mk)ij = λ1*1+ λ2*1 + … + λk*1 = Σ λk = 1
But observe that L(M) M(C). So by definition L(M) S.
In the book, the author Kenneth Rebman uses the theorem to prove the following interesting statement. Assume that there is a cake which is to be divided into pieces so that it can be shared.

If all the people have different individual standards on "the amount of a piece needed to get a greatest satisfaction," then it can be shared to all of them to their fullest satisfaction.

(no one becomes unhappy during the process of sharing a cake. Also, here I rephrased the original statement in the book greatly –maybe too greatly -- since it is too dry.)

Eventually, there will be some people who will get more of a cake than some others, but the assumption that their satisfaction is totally dependent on the initial amount of cake that they think they need to get the fullest satisfaction guarantees us this amazing result. I'm afraid I rephrased and simplified things to much that I can't get rid of feeling that I distorted what the book is saying. But for someone who is really intrigued by this result, it's definitely worth to read.

No comments: