9
$\begingroup$

In this question the OP mentions the following problem as an exercise on Krein-Milman theorem:

You have a great circular pizza with $n$ toppings. Show that you can divide the pizza equitably among $k$ persons, which means every person gets a piece of pizza with exactly $\frac{1}{k}$ of any of the $n$ topping on it.

I would like to ask both about interpretation (formalization) of this exercise and about the solution.

I am not sure whether I interpreted it correctly. To me it seems that mathematical reformulation of the problem could be that I have functions $f_i\colon X\to [0,1]$ for $i=1,\dots,n$ corresponding to how the toppings are distributed on the surface of pizza - the space $X$. And I would like to obtain a decomposition $X=A_1,\dots,A_k$ such that for any $i=1,\dots,n$ I have $\int_{A_1} f_i = \dots = \int_{A_k} f_i$, i.e., each person has the same portion from each of the toppings.

I am not sure whether this is the correct formalization. (Certainly the fact that Krein-Milman is supposed to be used is some kind of a hint on how the problem is supposed to be interpreted.)

But even if my interpretation is correct, I am not sure where to start. To apply Krein-Milman theorem, I need some locally convex topological vector space and some compact convex subset. I am not sure what space I could choose, since based on the above formulation it seems that the elements of this spaces should be somehow related to divisions of the circle.

Another possible interpretation I can think of is that I work with the functions $\{1,2,\dots,k\} \to \mathbb R^n$ representing how much of each topping gets the $k$-the person. It is certainly possible that $k$-the person gets the whole pizza, which would correspond to $f(k)=(1,1,\dots,1)$ and $f(i)=(0,0,\dots,0)$ for $i\ne k$. By I do not see how to show that the set of all admissible possibilities is convex. And if I can show that it is convex, then I do not really need Krein-Milman theorem.

$\endgroup$
5
+50
$\begingroup$

I think this refers to the range of vector valued measures: If $\mu_1,\ldots,\mu_n$ are real nonatomic measures on a measurable space $(\Omega,\mathcal B)$ then $\mu:\mathcal B \to \mathbb R^n$, $B\mapsto (\mu_1(B),\ldots,\mu_n(B))$ has a compact and convex range.

This is Theorem 5.5 in Rudin's Functional Analysis and indeed an application of the Krein-Milman theorem.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer. This certainly sounds like a reasonable interpretation of that question. After your post I was able to find that this is sometimes called Lyapunov Convexity theorem (for example, Theorem 13.33 in the book by Aliprantis and Border) and there is even a post on this site with some references for various proofs. $\endgroup$ – Martin Sleziak Jun 7 '17 at 10:03
  • $\begingroup$ I am curious about Rudin's Theorem 5.5, surely each $\mu_k$ must also be finite? Clearly if we take each $\mu_k$ to be the Lebesgue measure, then the range of the above function is the (non compact) line $t \mapsto (t,\cdots,t)$? I presume this is a misprint in the book, but am unable to find an erratum. $\endgroup$ – copper.hat Dec 2 '18 at 20:24
  • $\begingroup$ A * real* measure has real values. $\endgroup$ – Jochen Dec 2 '18 at 20:52
  • $\begingroup$ @MartinSleziak Could you please explain why this theorem fits the analogy? if $(\Omega, \mathcal{B})$ is the pizza, and $\mu_1,\dots ,\mu_n$ measure the individual toppings, what does convexity say(and compactness)? $\endgroup$ – pitariver Jan 30 at 18:49
  • 2
    $\begingroup$ @pitariver From $\emptyset,\Omega\in\mathcal B$ we get that both $(0,0,\dots,0)$ and $(1,1,\dots,1)$ are in the range. From convexity we get that $(\frac1k,\frac1k,\dots,\frac1k)$ belongs in the range, i.e., there is a set $B\in\mathcal B$ such that $\mu_1(B)=\mu_2(B)=\dots=\mu_n(B)=\frac1k$, so if we split the $B$ for one person, they get the right amount from each topping. We can then continue with dividing $\Omega\setminus B$. $\endgroup$ – Martin Sleziak Jan 30 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.