The cake is a lie!

Discrete Mathematics Level 3

Suppose a group of \(n\) people want to split a group of whole cakes among each other. Each cake is of one type only e.g. vanilla, chocolate, strawberry, etc.

Each person also has a value function associated with each type of cake, which denotes how much each cake is "worth" to each player. The sum of all the value functions for a given person is \(1\), and every person values nothing at \(0\). Note that a value function must be \(\geq 0\) and \(\leq 1\).

For example, person 1 might value vanilla at \(0.05\), while person 2 values vanilla at \(0.8\). Person 1 might value chocolate at \(0.77\), while person 2 values chocolate at \(0.00002\).

In addition, a person values a fraction \(f\) of a cake at a fraction \(f\) of the value function he/she associates it with. For example, given the above value functions, person 2 would value half a vanilla cake at \(0.4\), while person 1 values \(\frac{1}{7}\) of a chocolate cake at \(0.11\).

The total value a person receives is the combined values of all the cakes he/she has, based on his/her own value functions. For example, if person 1 receives a vanilla cake and a chocolate cake, his total value would be \(0.05 + 0.77 = 0.82\). If person 2 receives half a chocolate cake and half a vanilla cake, her total value would be \(0.00001 + 0.4 = 0.40001\).

Is it possible to divide the cakes among all \(n\) people such that each person receives at least a total value of \(\frac{1}{n}\)?

Source: AMST 2015 Power #1b

Problem Loading...

Note Loading...

Set Loading...