10
$\begingroup$

This question occurred to me a while ago when taking leftover slices of a pizza to go.

Suppose you have a unit-radius circular disc divided into $n$ equal sectors ("slices"). What is the smallest square that will contain $k$ of those $n$ sectors? You are permitted to translate and rotate the slices as desired, but they must all fit within the perimeter of the square, and they must not overlap.

For instance, if $k = 1$, $n = 4$, the answer is trivially a square of side $1$, but if $k = 1$, $n = 8$, then the smallest square has side $$ \cos \left(\frac{\pi}{8}\right) = \frac{\sqrt{2+\sqrt{2}}}{2}. $$

At least, I think it does. I haven't proved it yet. Anyway, I'm also interested in finding, for any $n$, which values of $k$ will not fit in a square of side less than $2$? By way of analogy in packing problems, it is known that $n^2-2$ squares will not fit into a square of side less than $n$. But I'm interested in pizza slices.

If it makes it easier to start things going, I'm also interested in various solutions for $k$ for a selected fixed $n$.

$\endgroup$
  • $\begingroup$ Shouldn't the side for $k=1$, $n=8$ be $\pi \over {8^{1/2}}$. As the area of the sector must be equal to $side^2$ $\endgroup$ – model_checker Jan 30 '16 at 11:00
  • 1
    $\begingroup$ @ShreyAryan: How do you figure? The sector can't be rearranged; it has to fit, whole, into the square, so the square will have plenty of empty space in it (especially in the $k = 1, n = 8$ case). Moreover, your value is greater than $1$; it should be obvious that the answer must be no more than $1$, shouldn't it? $\endgroup$ – Brian Tung Jan 30 '16 at 21:59
  • $\begingroup$ I think this question boils down to the classical Bin packing problem. $\endgroup$ – Vlad Jan 31 '16 at 9:53
  • 1
    $\begingroup$ I'm pretty sure this is the exact same question: www2.stetson.edu/~efriedma/mathmagic/0112.html $\endgroup$ – Colm Bhandal Aug 12 '17 at 10:04
  • $\begingroup$ @ColmBhandal: Nice find, thanks! $\endgroup$ – Brian Tung Aug 13 '17 at 7:14
2
+100
$\begingroup$

Partial, incomplete answer:

We can show that when $n$ is not a multiple of 4, we can fit at least $n-1$ slices in a square of side less than 2. If $n$ is a multiple of 4, we can fit at least $n-2$ slices in a square of side less than 2. Here is the argument:

Assume the slices are numbered $S_1,...,S_n$.

Case $n$ not multiple of 4: Put all the slices together, according the the way they are numbered, forming the unit circle. Let $\ell=\lfloor\frac{3n}{4}\rfloor$, as in the first picture (image to the left). If we remove $S_\ell$, rotate the slices in the darker area by $\alpha/2$ to the left and the slices in the lighter area by $\beta/2$ to the right, we can fit the remaining $n-1$ slices in a square of side $1+\cos(\beta/2)<2$, as in the first picture (image to the right). Also in this case $1+\cos(\beta/2)<2$ is an upper bound on the size of the side of the smallest square.

enter image description here

Case $n$ multiple of 4: Put all the slices together, according the the way they are numbered, forming the unit circle. Let $\alpha=\frac{\pi}{n}$ and $\ell=\lfloor\frac{3n}{4}\rfloor$, as in the second picture (image to the left). We see that rotating all the slices together by $\alpha/2$ to the right and then removing $S_{n/2}$ and $S_\ell$, we can fit the remaining $n-2$ slices in a square of side less than 2, as shown in the second picture (image to the right). Also, in this case $1+\cos(\alpha/2)<2$ is an upper bound on the size of the side of the smallest square.

enter image description here

Now. Whenever $k<n/4$, I think the smallest square containing $k$ slices has side $\alpha=\cos\left(\frac{\pi}{4}-\frac{k\pi}{n}\right)$. (or, at least, this value is a "decent" upper bound). The argument is, pick $k$ slices, put them together, as in the third picture. The sides of the square containing those slices have length $\alpha$. If we rotate the slices in some angle $\theta$, either the maximum value of $x$ or the maximum value of $y$ for an "extreme" point in the arc of the circle defined by the slices, will increase.

Now, if we "separate" the slices but keep them centered in the origin, it is clear the square containing them will be bigger than the one in the third picture. As well as is the case when the slices aren't even around the same "center".

enter image description here

$\endgroup$
  • $\begingroup$ Thanks! That's worth the bounty, for sure. $\endgroup$ – Brian Tung Feb 2 '16 at 1:11
  • $\begingroup$ Well, thank you. Nice to have been helpful : ). $\endgroup$ – Nate River Feb 2 '16 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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