{"id":3495,"date":"2022-10-01T19:14:31","date_gmt":"2022-10-02T00:14:31","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3495"},"modified":"2022-10-02T00:25:08","modified_gmt":"2022-10-02T05:25:08","slug":"perfect-pizza-sharing","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/perfect-pizza-sharing\/","title":{"rendered":"Perfect pizza sharing"},"content":{"rendered":"<p>This week&#8217;s <a href=\"https:\/\/fivethirtyeight.com\/features\/can-you-crack-the-safe\/\">Riddler Classic<\/a> is about how to cut a pizza to achieve precise area ratios between the slices.<\/p>\n<blockquote><p>\nDean made a pizza to share with his three friends. Among the four of them, they each wanted a different amount of pizza. In particular, the ratio of their appetites was 1:2:3:4. Therefore, Dean wants to make two complete, straight cuts (i.e., chords) across the pizza, resulting in four pieces whose areas have a 1:2:3:4 ratio.<\/p>\n<p>Where should Dean make the two slices?<\/p>\n<p><em>Extra credit:<\/em> Suppose Dean splits the pizza with more friends. If six people are sharing the pizza and Dean cuts along three chords that intersect at a single point, how close to a 1:2:3:4:5:6 ratio among the areas can he achieve? What if there are eight people sharing the pizza?\n<\/p><\/blockquote>\n<p>My solution:<br \/>\n<a href=\"javascript:Solution('soln_pizza_ratio','toggle_pizza_ratio')\" id=\"toggle_pizza_ratio\">[Show Solution]<\/a><\/p>\n<div id=\"soln_pizza_ratio\" style=\"display: none\">\n<h3>Deriving formulas for the areas<\/h3>\n<p>Let&#8217;s start by assuming the pizza is a circle of radius 1, and let&#8217;s use a coordinate system where the origin is at the center of the pizza. Since all cuts must intersect at a common point on the inside of the circle, we can rotate the circle such that the intersection point lies on the positive $x$-axis. Let the intersection point be $X$ and have coordinates $(x,0)$. We make $n$ cuts through this point, which will result in $n$ chords that intersect the circle at $n$ points above the $x$-axis and $n$ points below, so $2n$ total points.<\/p>\n<ul>\n<li> Let $\\theta_i$ denote the angle that point $i$ makes with the positive $x$-axis, measured with respect to the intersection point $X$.\n<li> Let $\\phi_i$ denote the angle that point $i$ makes with the positive $x$-axis, measured with respect to the origin $O$.\n<li> Let $L_i$ denote the length of the line segment between point $i$ and the intersection point $X$.\n<\/ul>\n<p>The figure below illustrates one possible set of cuts for the case $n=3$.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio_diagram.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio_diagram.png\" alt=\"\" width=\"1128\" height=\"1121\" class=\"aligncenter size-full wp-image-3508\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio_diagram.png 1128w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio_diagram-300x298.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio_diagram-1024x1018.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio_diagram-150x150.png 150w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio_diagram-768x763.png 768w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>Now we must compute the areas of the different slices. One such slice, between cuts $1$ and $2$, is shaded in the diagram above. We will split each slice into its triangular part $\\triangle_{12}$ and its rounded part $\\bigcirc_{12}$.<\/p>\n<ul>\n<li> The triangular part is the triangle $XP_1P_2$. Based on the side lengths $XP_1=L_1$ and $XP_2=L_2$ and angle $\\angle P_1XP_2=\\theta_2-\\theta_1$, the area is<br \/>\n\\[<br \/>\n\\triangle_{12} = \\frac{1}{2}L_1L_2 \\sin(\\theta_2-\\theta_1)<br \/>\n\\]<\/p>\n<li> The rounded part is the difference between the circular sector $O P_1P_2$ and the triangle $OP_1P_2$. Since the pizza has radius $1$, $OP_1=OP_2=1$. The circular sector has area $\\frac{1}{2}(\\phi_2-\\phi_1)$ and the triangle has area $\\frac{1}{2}\\sin(\\phi_2-\\phi_1)$. Therefore, the slice between cuts $1$ and $2$ has total area:<br \/>\n\\[<br \/>\n\\bigcirc_{12} = \\frac{1}{2}\\left( (\\phi_2-\\phi_1)-\\sin(\\phi_2-\\phi_1)\\right)<br \/>\n\\]\n<\/ul>\n<p>Our next task will be to express $\\phi_i$ and $L_i$ in terms of $x$ and $\\theta_i$. Consider the point $P_i$. We can write its coordinates in two different ways depending on whether we arrive there via $O\\to P_i$ or $O\\to X\\to P_i$. This yields<br \/>\n\\[<br \/>\nP_i = \\begin{bmatrix}\\cos\\phi_i \\\\ \\sin\\phi_i\\end{bmatrix}<br \/>\n= \\begin{bmatrix}x + L_i \\cos\\theta_i \\\\ L_i\\sin\\theta_i \\end{bmatrix}<br \/>\n\\]squaring these equations and summing them to eliminate $\\phi_i$, we obtain<br \/>\n\\[<br \/>\n1 = (x+L_i\\cos\\theta_i)^2+L_i^2\\sin^2\\theta_i<br \/>\n\\]Solving for $L_i$ and keeping the positive root (since $L_i \\gt 0$), we find<br \/>\n\\[<br \/>\nL_i = \\sqrt{1-x^2\\sin^2\\theta_i}-x\\cos\\theta_i.<br \/>\n\\]Putting everything together, we now have a formula for the area of a slice! In the case of the slice between cuts $1$ and $2$, the area would be:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 70px 5px 70px 5px;\">$\\displaystyle<br \/>\n\\begin{aligned}<br \/>\nA_{12}(x,\\theta_1,\\theta_2) &#038;= \\frac{1}{2}L_1L_2 \\sin(\\theta_2-\\theta_1) + \\frac{1}{2}\\bigl( (\\phi_2-\\phi_1)-\\sin(\\phi_2-\\phi_1)\\bigr) \\\\<br \/>\n\\text{where:}\\,\\,&#038; \\left\\{\\begin{aligned}<br \/>\nL_i &#038;= \\sqrt{1-x^2\\sin^2\\theta_i}-x\\cos\\theta_i \\\\<br \/>\n\\phi_i&#038;= \\arccos\\left(\\cos\\theta_i\\sqrt{1-x^2\\sin^2\\theta_i} + x \\sin^2\\theta_i \\right)<br \/>\n\\end{aligned}\\right.<br \/>\n\\end{aligned}<br \/>\n$<\/span><\/p>\n<p>Similar formulas hold true for the remaining slices, so if we have $n$ cuts and we specify the location $x$ of the intersection and the angles $\\theta_1,\\dots,\\theta_n$, we can find formulas for areas of each of the slices $A_{ij}$.<\/p>\n<h3>Finding an optimal set of cuts<\/h3>\n<p>If we have $n$ cuts, there will be $2n$ slices. To keep things simple, let&#8217;s normalize the areas so that the total area is $1+2+\\dots+2n=2n^2+n$, and let&#8217;s label the normalized areas $A_1,\\dots,A_{2n}$ (in counterclockwise order, starting from $A_{12}$). The reason for doing this is that for example in the case $n=2$, we want the $4$ slices to be in the ratio $1:2:3:4$. So we normalize the total area to be $1+2+3+4=10$. That way we can directly try to make $A_1=1$, $A_2=2$, etc.<\/p>\n<p>Each area will be a function of the parameters $\\{x,\\theta_1,\\dots,\\theta_n\\}$. The goal is to find the set of parameters that give areas that are as close to the numbers $1,2,\\dots,2n$. There are many ways to define &#8220;closeness&#8221;. I will use the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Least_squares\">least squares<\/a> criterion, which does a good job in this case because it ensures that all areas are &#8220;roughly equally close&#8221; to what they should be and there are no large deviations.<\/p>\n<p>For example, in the case $n=2$, our task would be to pick $(x,\\theta_1,\\theta_2)$ such that the following function is minimized:<br \/>\n\\[<br \/>\nJ_1 = (A_1-1)^2 + (A_2-2)^2 + (A_3-3)^2 + (A_4-4)^2<br \/>\n\\]But there is more&#8230; What if the slices do not occur in this particular order 1,2,3,4? We should also check other permutations! For example, we should also try the functions:<br \/>\n\\begin{align}<br \/>\nJ_2 &#038;= (A_1-1)^2 + (A_2-2)^2 + (A_3-4)^2 + (A_4-3)^2 \\\\<br \/>\nJ_3 &#038;= (A_1-1)^2 + (A_2-3)^2 + (A_3-2)^2 + (A_4-4)^2 \\\\<br \/>\n&#038;\\cdots<br \/>\n\\end{align}In all, there will be $(2n)!$ permutations, or $24$ in the case $n=2$. This number can be reduced by a factor of $2$ if we leverage symmetry in reflection.<\/p>\n<p>So our process will be as follows:<\/p>\n<ol>\n<li> pick a permutation $p$ of $\\{1,2,\\dots,2n\\}$\n<li> Find $(x,\\theta_1,\\dots,\\theta_n)$ that minimizes the least squares cost<br \/>\n\\[<br \/>\nJ_p = \\sum_{i=1}^{2n} \\bigl(A_i(x,\\theta_1,\\dots,\\theta_n)-p_i\\bigr)^2<br \/>\n\\]subject to the constraints $0\\leq x\\leq 1$ and $0\\leq \\theta_1\\lt\\cdots\\lt\\theta_n\\leq \\pi$.<\/p>\n<li> If we can obtain $J_p=0$, then we have a perfect match and we can stop. Otherwise, return to step 1 and pick a different permutation $p$. Repeat until all permutations have been tested.\n<\/ol>\n<p>The function $J(x,\\theta_1,\\dots,\\theta_n)$ is a difficult (read: nonconvex) function, but still relatively well-behaved (read: continuously differentiable), so standard off-the-shelf solvers are adequate for the task. I used Matlab&#8217;s constrained nonlinear optimizer <a href=\"https:\/\/www.mathworks.com\/help\/optim\/ug\/fmincon.html\" class=\"broken_link\">fmincon<\/a>.\n<\/div>\n<p>To jump straight to the results:<br \/>\n<a href=\"javascript:Solution('soln_pizza_ratio2','toggle_pizza_ratio2')\" id=\"toggle_pizza_ratio2\">[Show Solution]<\/a><\/p>\n<div id=\"soln_pizza_ratio2\" style=\"display: none\">\n<h3>The case of 4 slices<\/h3>\n<p>For the case $n=2$ (4 pieces), it is possible to achieve the exact desired ratio. Here is one solution that works, where I labeled each slice with its normalized area.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4.png\" alt=\"\" width=\"552\" height=\"546\" class=\"aligncenter size-full wp-image-3501\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4.png 552w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4-300x297.png 300w\" sizes=\"auto, (max-width: 552px) 85vw, 552px\" \/><\/p>\n<p>In the case above, $x=0.3406$, and $\\theta = \\{0^\\circ, 69.838^\\circ\\}$. This case is nice because $1+4=2+3$, so one of the cuts is actually a diameter and cuts through the center! In all, there are six permutations that lead to valid solutions for the case of 4 slices:<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4b.png\" alt=\"\" width=\"971\" height=\"1346\" class=\"aligncenter size-full wp-image-3504\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4b.png 971w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4b-216x300.png 216w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4b-739x1024.png 739w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio4b-768x1065.png 768w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><br \/>\nEach solution in the left column has a &#8220;twin&#8221; next to it in the right column, which comes from reflecting the solution about the $x$-axis. <\/p>\n<h3>The case of 6 slices<\/h3>\n<p>In this case, it is not possible to achieve the exact desired ratio. Some permutations can get &#8220;closer&#8221; (in the least squares sense), so in order to find the best one, we must try all possible permutations. The smallest least squares error achievable turns out to be $0.0024$, and it is achieved by a single permutation (and its twin). Here is that solution. Again, I labeled each slice with its normalized area.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio6.png\" alt=\"\" width=\"542\" height=\"542\" class=\"aligncenter size-full wp-image-3502\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio6.png 542w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio6-300x300.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio6-150x150.png 150w\" sizes=\"auto, (max-width: 542px) 85vw, 542px\" \/><\/p>\n<p>This solution corresponds to $x=0.3488$ and $\\theta=\\{19.200^\\circ, 80.363^\\circ, 160.910^\\circ\\}$.<\/p>\n<h3>The case of 8 slices<\/h3>\n<p>This case is similar to the previous one. This time, the smallest least squares error achievable is $0.0032$, and again it is achieved by a single permutation (and its twin). Here is that solution.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio8.png\" alt=\"\" width=\"542\" height=\"541\" class=\"aligncenter size-full wp-image-3500\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio8.png 542w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio8-300x300.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2022\/10\/pizzaratio8-150x150.png 150w\" sizes=\"auto, (max-width: 542px) 85vw, 542px\" \/><\/p>\n<p>This solution corresponds to $x=0.1875$ and $\\theta=\\{ 13.768^\\circ,   28.356^\\circ,   68.600^\\circ,  135.310^\\circ\\}$. Interestingly, even though there are permutations that would lead to an even split, such as $2+3+5+8=1+4+6+7$ (such a split would mean that one of the cuts goes through the center), none of these even splits produce a solution that comes as close to the desired ratio as the one above.\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>This week&#8217;s Riddler Classic is about how to cut a pizza to achieve precise area ratios between the slices. Dean made a pizza to share with his three friends. Among the four of them, they each wanted a different amount of pizza. In particular, the ratio of their appetites was 1:2:3:4. Therefore, Dean wants to &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/perfect-pizza-sharing\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Perfect pizza sharing&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3504,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[37,10,26,2],"class_list":["post-3495","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-coding","tag-geometry","tag-optimization","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3495","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=3495"}],"version-history":[{"count":15,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3495\/revisions"}],"predecessor-version":[{"id":3516,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3495\/revisions\/3516"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/3504"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3495"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3495"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3495"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}