Mixing
How many slices of pizza do we have?
Clash Royale CLAN TAG#URR8PPP
up vote
16
down vote
favorite
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.
elementary-number-theory recreational-mathematics fractions
edited Aug 21 at 20:06
6005
35k750124
asked Aug 21 at 19:20
crazyjin
835
 |Â
show 8 more comments
up vote
16
down vote
favorite
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.
elementary-number-theory recreational-mathematics fractions
edited Aug 21 at 20:06
6005
35k750124
asked Aug 21 at 19:20
crazyjin
835
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
 |Â
show 8 more comments
up vote
16
down vote
favorite
up vote
16
down vote
favorite
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.
elementary-number-theory recreational-mathematics fractions
edited Aug 21 at 20:06
6005
35k750124
asked Aug 21 at 19:20
crazyjin
835
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.
elementary-number-theory recreational-mathematics fractions
edited Aug 21 at 20:06
6005
35k750124
asked Aug 21 at 19:20
crazyjin
835
edited Aug 21 at 20:06
6005
35k750124
edited Aug 21 at 20:06
6005
35k750124
edited Aug 21 at 20:06
6005
35k750124
35k750124
asked Aug 21 at 19:20
crazyjin
835
asked Aug 21 at 19:20
crazyjin
835
asked Aug 21 at 19:20
crazyjin
835
835
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
 |Â
show 8 more comments
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
3
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
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
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
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
It's like $2N-1$ pieces.
– Anik Bhowmick
Aug 21 at 19:38
1
1
Cuts look related to the Farey sequence, confirmed by the solutions posted
– Mark Bennet
Aug 21 at 20:15
Cuts look related to the Farey sequence, confirmed by the solutions posted
– Mark Bennet
Aug 21 at 20:15
 |Â
show 8 more comments
2 Answers
2
active
oldest
votes
up vote
7
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, frac1n, frac2n, ldots, fracn-1n$. (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.
answered Aug 21 at 20:12
6005
35k750124
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
add a comment |Â
up vote
7
down vote
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^nphi(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^2pi 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.
answered Aug 21 at 20:10
CyclotomicField
1,6141212
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
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, frac1n, frac2n, ldots, fracn-1n$. (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.
answered Aug 21 at 20:12
6005
35k750124
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
add a comment |Â
up vote
7
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, frac1n, frac2n, ldots, fracn-1n$. (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.
answered Aug 21 at 20:12
6005
35k750124
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
add a comment |Â
up vote
7
down vote
accepted
up vote
7
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, frac1n, frac2n, ldots, fracn-1n$. (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.
answered Aug 21 at 20:12
6005
35k750124
We may identify angles for the slices with real numbers between $0$ and $1$. At step $n$, we cut at angles $0, frac1n, frac2n, ldots, fracn-1n$. (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.
answered Aug 21 at 20:12
6005
35k750124
answered Aug 21 at 20:12
6005
35k750124
answered Aug 21 at 20:12
6005
35k750124
answered Aug 21 at 20:12
6005
35k750124
35k750124
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
add a comment |Â
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
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
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
@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
add a comment |Â
up vote
7
down vote
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^nphi(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^2pi 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.
answered Aug 21 at 20:10
CyclotomicField
1,6141212
add a comment |Â
up vote
7
down vote
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^nphi(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^2pi 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.
answered Aug 21 at 20:10
CyclotomicField
1,6141212
add a comment |Â
up vote
7
down vote
up vote
7
down vote
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^nphi(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^2pi 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.
answered Aug 21 at 20:10
CyclotomicField
1,6141212
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^nphi(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^2pi 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.
answered Aug 21 at 20:10
CyclotomicField
1,6141212
edited Aug 21 at 23:45
answered Aug 21 at 20:10
CyclotomicField
1,6141212
answered Aug 21 at 20:10
CyclotomicField
1,6141212
answered Aug 21 at 20:10
CyclotomicField
1,6141212
1,6141212
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2890271%2fhow-many-slices-of-pizza-do-we-have%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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