At the beginning, we had a whole piece of pizza and two people. So we cut the pizza into two slices of the same size. But at the same time, there is another guy joined us. We had to re-cut the pizza into three parts of the same size. This time we only need to cut two more times. But this was not the end yet, people were keep coming one by one. Every time we divided the pizza into equals with a minimum times of cut.$^{1}$ In the end, a total of N people came. How many slices of pizza do we have? Is there a way to figure it out quickly?

$^{1}$ The slices cannot be rearranged to get a smaller number of cuts. We cut the pizza in place, at $n$ equally-placed lines, as in the image below.

Demonstration

  • 3
    You may benefit from studying our guide to new askers. It would be better if you included either your own thoughts, or possibly the origin of this problem? Also the rules are a bit unclear. Do the extra people come one at a time? Is it ok for the share of a single guest to come from a thin slice here, another there, or do they need to get a contiguous slice of $1/n$th of the pizza? – Jyrki Lahtonen Aug 21 at 19:35
  • What if I tilt the pizza ever so slightly before making any cuts? Then I can increase the number of pieces at each stage. To avoid this ambiguity it seems sensible to define the cuts at the $n$-th roots of unity in the complex plane give how you're drawn them so far. – CyclotomicField Aug 21 at 19:35
  • Also, this rings a bell. Did you search the site? – Jyrki Lahtonen Aug 21 at 19:35
  • It's like $2N-1$ pieces. – Anik Bhowmick Aug 21 at 19:38
  • 1
    Cuts look related to the Farey sequence, confirmed by the solutions posted – Mark Bennet Aug 21 at 20:15
up vote 8 down vote accepted

We may identify angles for the slices with real numbers between $0$ and $1$. At step $n$, we cut at angles $0, \frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n}$. (As clarified in the comments, the problem seems to assume this. Note that there is a more interesting question if we are allowed to rearrange the pieces, or if we are allowed to place the cuts at any arbitrary angle as long as the lines are equally spaced.)

Thus, the number of slices after $n$ people have joined is equal to the number of rational numbers in the interval $[0,1)$ with denominator at most $n$. The number with denominator exactly $k$ is $\phi(k)$, where $\phi$ is the totient function which counts how many numbers between $0$ and $k-1$ (numerators) are relatively prime to the $k$ (the denominator).

Therefore, the total number of slices after $n$ people have joined can also be expressed as $$ a_n = \sum_{k=1}^n \phi(k). $$

The sequence $a_n$ begins $2, 4, 6, 10$ as in your picture. More information on the sequence can be found in this Online Encyclopedia of Integer Sequences page.

  • This problem comes from no where but boring. I know almost nothing about the numbers. It's amazing that you can find the solution in such a short time. I checked a few numbers in the sequence and they are all correct. I don't have enough knowledge to verify the function you gave. But I will write a small program to verify the numbers in the sequence. – crazyjin Aug 21 at 21:24
  • @crazyjin It's definitely correct as it's the same answer I arrived at using a slightly different method. – CyclotomicField Aug 22 at 0:01

First, let us consider the cuts to be the $n$-th roots of unity in the complex plane and let $\phi(n)$ be Euler's totient function. I claim that the number of cuts is $\sum_{k=1}^n\phi(k)$. To see this first we note that for some prime $p$ the only divisor is $1$ we must make $p-1$ new cuts since those roots of unity could not be cut yet or it would imply a divisor of $p$. Now for some composite $n$ as we traverse the circle by taking multiples of $e^{2\pi i/n}$ then we note that for some cut $e^{2 \pi i k/n}$ to have already been made implies that $k$ divides $n$. This means we will make a new cut when $k$ is relatively prime to $n$. Summing over these cuts for each $n$ gives us the result.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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