And even if you do, do not try to estimate how many maximum number of slices can be made by $n$ cuts.
Well, at least keep 3 A4 sized rough sheets with you, cause that's how many i scribbled on trying to solve this maximum number of slices problem 😀
The problem appears in 'Concrete Mathematics' as:
'How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?'
or
'What is the maximum number Ln of regions defined by n lines in the plane?'
Well, if you slice the pizza the way you usually do, it looks like $2n$ doesn't it? with every slice having a bit of the rounded hard to chew topping less edge
So, slicing the pizza is kind of an unnatural example, or should we say that math rather itself is a bit unnatural to people like me?
Turns out you can slice the pizza this way too
Well, the color of the pizza changed, that's because my 4.5 year old daughter jumped on to my couch and wanted it this way.. As with most guys who have a girl child, i, too must admit that i haven't really figured out why she likes pink from age 3, but anyways its not that relevant for cutting exotic pizza slices
Now, the explanation offered in the book to establish a recurrence relationship between number of new slices made by $n^{th}$ cut w.r.t to existing number of slices is as follows, and quite convincing:
"And after some thought we realize the appropriate generalization. The $n^{th}$ line (for $n > 0$) increases the number of regions by $k$ if and only if it splits $k$ of the old regions, and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different places. Two lines can intersect in at most one point. Therefore the new line can intersect the $n-1$ old lines in at most $n-1$ different points, and we must have $k \le n$."
After a couple of reads, i 'seemed to understand' this paragraph and started solving the problem with the recurrence $S_n=S_{n-1}+n$ where $S_n$ is number of slices after $n^{th}$ cut and $S_{n-1}$ is number of slices after $n-1^{th}$ cut.
Then reached to the conclusion fairly easily without reading further text that $S_n = 1 + n(n+1)/2$
However, reality about the 'seemed to understand' part of it stuck right in my face or should i say under my skull when i started to solve an extension to this problem given out as an exercise in the book.
The extension kind of asks you to find the number of slices without the round edges after $n^{th}$ cut, or simply the tastier slices 😃
So our $5^{th}$ cut is entering from the left and cuts the rounded slice into two as it touches cut #1.
As our $5^{th}$ cut passes through cut #1 and touches cut #2, it splits the slice bound by cuts 1 and 2. Here we have one slice with a round edge on the top, and one below which is all cheese.
So, it goes on as the $5^{th}$ cut passes through cuts 2, 3, and then on to cut 4.
As we can see, when a cut passes through 2 existing cuts, it creates exactly one new slice without rounded edge.
Finally, as the cut crosses cut #4 and meets the edge of the pizza it splits that right most slice into two.
Looking at all of this, we can now say that every cut creates 1 rounded slice on its way in, and 1 rounded slice on its way out for sure.
And as it runs its course along the pizza, it creates as many slices without rounded edge as the distinct pairs of existing cuts it goes across.
Visually, we can easily see that if there already are $n-1$ cuts, then the $n^{th}$ cut creates $(n-1)-1 = n-2$ full cheese slices (i.e., ones without the round edge).
Putting this together
$S_n = S_{n-1} + 2 + (n - 2) = S_{n-1} + n$
But would this recurrence hold for $n=1$ as there are no existing cuts?
It would, because the first cut just goes across the pizza end to end, and divides it into two slices.
Now that "and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different places." is established properly in the brain, it is quite easy to calculate the number of all cheese slices
$C_n = C_{n-1} + (n-2) = n-2 + n-3 + ... + C_3 = n-2 + n-3 + ... + 1 = (n-2)(n-1)/2$
Lastly, after experiencing this volatility in the brain where you sometimes seem to understand a concept, and sometimes do not. And also you sometimes have solved a problem in past which you cannot now, i was thinking of ways to overcome it.. And the only way i can think of is, start from scratch always.
The only consolation out of this misery that comes to me is a piece of information i read about this great mathematician called Jakob Steiner who apparently presented a solution to this problem, or should we say made this problem popular in 1800 something...
https://en.wikipedia.org/wiki/Jakob_Steiner
" He never prepares his lectures beforehand. He thus often stumbles or fails to prove what he wishes at the moment, and at every such failure he is sure to make some characteristic remark."
Well, at least keep 3 A4 sized rough sheets with you, cause that's how many i scribbled on trying to solve this maximum number of slices problem 😀
The problem appears in 'Concrete Mathematics' as:
'How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?'
or
'What is the maximum number Ln of regions defined by n lines in the plane?'
So, slicing the pizza is kind of an unnatural example, or should we say that math rather itself is a bit unnatural to people like me?
Turns out you can slice the pizza this way too
Well, the color of the pizza changed, that's because my 4.5 year old daughter jumped on to my couch and wanted it this way.. As with most guys who have a girl child, i, too must admit that i haven't really figured out why she likes pink from age 3, but anyways its not that relevant for cutting exotic pizza slices
Now, the explanation offered in the book to establish a recurrence relationship between number of new slices made by $n^{th}$ cut w.r.t to existing number of slices is as follows, and quite convincing:
"And after some thought we realize the appropriate generalization. The $n^{th}$ line (for $n > 0$) increases the number of regions by $k$ if and only if it splits $k$ of the old regions, and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different places. Two lines can intersect in at most one point. Therefore the new line can intersect the $n-1$ old lines in at most $n-1$ different points, and we must have $k \le n$."
After a couple of reads, i 'seemed to understand' this paragraph and started solving the problem with the recurrence $S_n=S_{n-1}+n$ where $S_n$ is number of slices after $n^{th}$ cut and $S_{n-1}$ is number of slices after $n-1^{th}$ cut.
Then reached to the conclusion fairly easily without reading further text that $S_n = 1 + n(n+1)/2$
However, reality about the 'seemed to understand' part of it stuck right in my face or should i say under my skull when i started to solve an extension to this problem given out as an exercise in the book.
The extension kind of asks you to find the number of slices without the round edges after $n^{th}$ cut, or simply the tastier slices 😃
If i really understood "and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different places.", i would not have scribbled away 3 A4 sheets trying to understand how a new cut is changing the existing slices.
So, i would go on to claim here that you have not read a technical book until you solved all the exercises. And also do not look at the solution until you have one. Look at the solution only for comparison. If you cannot solve the problem, either try longer if you can afford the time, or skip it and come back to it on another day or another time of that day, but never look at the solution. Curiosity kills of course.
So, i would go on to claim here that you have not read a technical book until you solved all the exercises. And also do not look at the solution until you have one. Look at the solution only for comparison. If you cannot solve the problem, either try longer if you can afford the time, or skip it and come back to it on another day or another time of that day, but never look at the solution. Curiosity kills of course.
Well now i explain in my own terms as how each $n^{th}$ cut changes the slices:
Lets start with a pizza already sliced out by 4 cuts as below (this time around cuts are labelled 1,2,3 and 4 instead of the slices)
Lets see what happens now if we make a $5^{th}$ cut across these 4 existing cuts
As we can see, when a cut passes through 2 existing cuts, it creates exactly one new slice without rounded edge.
Looking at all of this, we can now say that every cut creates 1 rounded slice on its way in, and 1 rounded slice on its way out for sure.
And as it runs its course along the pizza, it creates as many slices without rounded edge as the distinct pairs of existing cuts it goes across.
Visually, we can easily see that if there already are $n-1$ cuts, then the $n^{th}$ cut creates $(n-1)-1 = n-2$ full cheese slices (i.e., ones without the round edge).
Putting this together
$S_n = S_{n-1} + 2 + (n - 2) = S_{n-1} + n$
But would this recurrence hold for $n=1$ as there are no existing cuts?
It would, because the first cut just goes across the pizza end to end, and divides it into two slices.
Now that "and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different places." is established properly in the brain, it is quite easy to calculate the number of all cheese slices
$C_n = C_{n-1} + (n-2) = n-2 + n-3 + ... + C_3 = n-2 + n-3 + ... + 1 = (n-2)(n-1)/2$
Lastly, after experiencing this volatility in the brain where you sometimes seem to understand a concept, and sometimes do not. And also you sometimes have solved a problem in past which you cannot now, i was thinking of ways to overcome it.. And the only way i can think of is, start from scratch always.
The only consolation out of this misery that comes to me is a piece of information i read about this great mathematician called Jakob Steiner who apparently presented a solution to this problem, or should we say made this problem popular in 1800 something...
https://en.wikipedia.org/wiki/Jakob_Steiner
" He never prepares his lectures beforehand. He thus often stumbles or fails to prove what he wishes at the moment, and at every such failure he is sure to make some characteristic remark."
No comments:
Post a Comment