Question

Use mathematical induction to show that n people can divide a cake (where each person gets one or more separate pieces of the cake) so that the cake is divided fairly, that is, in the sense that each person thinks he or she got at least $\left(\frac{1}{n}\right)$ th of the cake. [Hint: For the inductive step, take a fair division of the cake among the first k people, have each person divide their share into what this person thinks are k+1 equal portions, and then have the $\left(k+1\right)$st person select a portion from each of the k people. When showing this produces a fair division for k + 1 people, suppose that person k+1 thinks that person i got ${\mathit{P}}_{\mathbf{i}}$ of the cake where $\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{k}}\mathbf{ }{\mathit{p}}_{\mathbf{i}}\mathbf{=}\mathbf{1}$.]

Short answer

It is proven that n people can divide a cake so that the cake is divided fairly.

Step-by-step solution

Mathematical Induction

The principle of mathematical induction is to prove that $P\left(n\right)$is true for all positive integer n in two steps.

1. Basic step: To verify that $P\left(1\right)$is true.

2. Inductive step: To prove the conditional statement if $P\left(k\right)$is true then $P(k+1)$ is true.

Basic Step

Let $P\left(n\right)$be the statement that “n people can divide a cake so that the cake is divided fairly”.

Basic step:

Let $n=2$then there are two people and the first-person cuts the cake in half. Both the person believes that they got at least half of the cake since the first person cuts it roughly in half.

Thus, the statement is true for $P\left(2\right)$.

Induction Step

Let $P\left(k\right)$be true then k people divide the cake so that the cake is divided fairly.

Here, the k people divide the slices into k+1 pieces where the k+1th person chooses the largest piece of the k+1th pieces from each of the k persons.

The first k people believed that they received at least role="math" localid="1668609153681" $\frac{1}{k+1}$th of the cake and the (k+1)th person also believes that he/she received at least $\frac{1}{k+1}$th of the cake.

Thus, $P(k+1)$is true.

Therefore, the statement $P\left(n\right)$ is true for every positive integer n.