40
$\begingroup$

You want to prepare a pizza of 12 flavors. You have 12 oddly-shaped pieces of cheese that you decide to use for the pizza. The shapes happen to be ...

Oh, well, forget it! This isn't going to be even remotely realistic. So here is the problem:

I was playing with pentominoes and figured you can pack them nicely in a circle of radius 5.

enter image description here

This immediately cries for the question: Is this optimal? If not, what is the radius of the smallest circle that can accommodate all 12 pentominoes inside without overlap? Show an arrangement that minimizes the radius.

Spoiler alert: the picture above is not optimal.

Scoreboard:
4.84323 loopy wait
4.86594 Florian F
4.88966 Ravi Fernando
4.92443 Daniel Mathias
4.94975 cap
4.98189 Franciszek Remin

Improve this question
$\endgroup$
3
  • 9
    $\begingroup$ The trivial lower bound is $\sqrt{60/\pi} \sim 4.37$ which is a disk with the same area as the 12 pentominoes but of course you can't reach that because there will always be some waste at the edges. $\endgroup$
    – quarague
    Aug 29, 2022 at 6:25
  • 1
    $\begingroup$ My junior's name is Franciszek Remin - if you were so kind to put my son's name on the list of fame. $\endgroup$
    – Przemyslaw Remin
    Jan 3 at 12:30
  • $\begingroup$ It is my pleasure. $\endgroup$
    – Florian F
    Jan 3 at 15:09

6 Answers 6

Reset to default
18
$\begingroup$

UPDATE 2

A minor improvement. New best radius

4.84323

Arrangement

enter image description here

/UPDATE 2

UPDATE

New best radius:

4.8487

using arrangement

enter image description here

/UPDATE

I get a radius of about

4.866

using the following scheme

enter image description here

which is obviously heavily indebted to Ravi Fernando's. The improvement is in the left half.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Congratulations! This matches my result. At last! And your arrangement is even more elegant than mine. $\endgroup$
    – Florian F
    Sep 17, 2022 at 19:05
  • 2
    $\begingroup$ @FlorianF Just managed to shrink it a bit more. $\endgroup$
    – loopy walt
    Sep 18, 2022 at 5:06
  • 1
    $\begingroup$ Fantastic! Checked and validated. Unfortunately, I cannot accept or upvote a second time. But I updated the scoreboard. $\endgroup$
    – Florian F
    Sep 19, 2022 at 19:26
13
$\begingroup$

I can get a radius of:

$\sqrt{\frac{149487}{2} - 975 \sqrt{5873}} \approx 4.88739$.

Method: start with

the following modification of cap's answer (thanks also to Jaap Scherphuis's comment):

enter image description here

and then

shift the rightmost three pentominoes up by $c = \frac{77 - \sqrt{5873}}{2} \approx 0.18225$ units.

The resulting figure has circumcenter located $\frac{7c-c^2}{14} = \frac{5\sqrt{5873} - 383}{2} \approx 0.08875$ units left of the center of the middle square; it intersects the circumcircle at the northwest, southwest, and southeast corners, as well as the corner at top of the eastern edge.

EDIT: I found a second solution with the slightly worse radius

$\sqrt{12110 - 480 \sqrt{634}} \approx 4.88966$.

Method: start with

the following configuration inspired by Daniel Mathias's answer, with four half-square-unit holes:

enter image description here

and then

shift the four rightmost pentominoes up by $c = \sqrt{634} - 25 \approx 0.17936$ units.

The resulting figure has circumcenter $\frac{4c - c^2}{18} = \frac{6 \sqrt{634} - 151}{2} \approx 0.03807$ units left of the center of the middle square; it touches its circumcircle at the top and bottom of the left edge, the bottom of the right edge, and the top corner of the X-pentomino. Note that the four pentominoes in the middle don't touch the circumcircle, so they have a little room to wiggle up and down.

I found both of these with the help of

https://cemulate.github.io/polyomino-solver/ to place the pentominoes, and WolframAlpha for coordinate calculations.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ While I congratulate all of you for your efforts, I am a bit embarrassed to announce that this still does not match the best solution I know. But you start to be really close. $\endgroup$
    – Florian F
    Aug 28, 2022 at 22:25
  • 2
    $\begingroup$ That's great! Really fun problem, I'm looking forward to seeing what further twists it's hiding. $\endgroup$
    – Ravi Fernando
    Aug 28, 2022 at 23:07
  • $\begingroup$ FYI I found another good arrangement, which is unfortunately very slightly worse than my first. I've added it to my answer in case anyone else can gain some insight from it. $\endgroup$
    – Ravi Fernando
    Sep 15, 2022 at 6:18
9
$\begingroup$

The radius of the smallest pizza that can accommodate all 12 cheeses is

$\sqrt{3.5^2 + 3.5^2} \approx 4.95$

The cheeses can be arranged like this:

enter image description here (There is square unit of tomato sauce with no cheese on the right)

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Very nice solution. By the way, the cheese van be placed to put that square of tomato sauce anywhere you like. $\endgroup$
    – Jaap Scherphuis
    Aug 27, 2022 at 23:06
  • $\begingroup$ Nice try ...... $\endgroup$
    – Florian F
    Aug 28, 2022 at 0:07
  • $\begingroup$ I am new to this puzzle, on what software can I play this, ie arranging and rearranging the pentominoes?? $\endgroup$
    – Kutsit
    Aug 28, 2022 at 6:16
  • 3
    $\begingroup$ @Kutsit I don't know of any software. I made the pentominoes out of legos and used them to find my arrangement. Then I used a spreadsheet to create the graphic. $\endgroup$
    – caPNCApn
    Aug 28, 2022 at 7:26
  • $\begingroup$ @Kutsit I used an on line solver to find the initial pattern and wrote a java program to render it with the circle background $\endgroup$
    – Florian F
    Aug 28, 2022 at 7:49
7
$\begingroup$

The smallest radius is (apparently less than)

$\frac12\sqrt{9^2+4^2}=\frac12\sqrt{97}\approx4.9244$

One such arrangement is shown here:

Pentomino Pizza

Improve this answer
$\endgroup$
10
  • 5
    $\begingroup$ You claim it's smallest but don't support that claim. $\endgroup$
    – msh210
    Aug 28, 2022 at 5:36
  • 4
    $\begingroup$ On the one side, it is probably difficult to prove optimality, I don't require it. On the other side, I know this one isn't. I know of a better solution. $\endgroup$
    – Florian F
    Aug 28, 2022 at 7:55
  • 4
    $\begingroup$ Via integer linear programming, I have found that Daniel's radius matches half of the minimum diameter of a set of 60 nonoverlapping unit squares with integer coordinates. If @FlorianF and I are both right, that means every optimal solution will have at least one pentomino with non-integer coordinates. $\endgroup$
    – RobPratt
    Aug 28, 2022 at 15:34
  • $\begingroup$ Glad to see you looking in the right direction. Who said cheese has to be placed at integer coordinates on a pizza? $\endgroup$
    – Florian F
    Aug 28, 2022 at 15:44
  • 3
    $\begingroup$ @RobPratt If you can translate that to an actual solution with pentominoes then you clearly beat me. $\endgroup$
    – Florian F
    Aug 29, 2022 at 4:47
7
$\begingroup$

For reference, here is my solution.

With a radius of 4.86594

enter image description here

Improve this answer
$\endgroup$
6
$\begingroup$

I presented your challenge to my 9-year-old son. I gave him a circle with a radius of 5. To my astonishment, he finally came up with a solution. Sorry I have not bothered to calculate the radius of the smallest circle in which these beasts can be packed. The radius is definitely less than 5. So naturally, this solution is in the game.

enter image description here

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Nice! Now let's see. The distance between the left of the lower edge and the right of the upper edge is $\sqrt{9^2+4^2} = 9.8488$, giving a radius of at least 4.9244. But that line isn't centered. For the actual radius I get 4.9547. $\endgroup$
    – Florian F
    Aug 31, 2022 at 11:42
  • 1
    $\begingroup$ How did you inscribe the pentominoes in the smallest circle? Where exactly is the center of the circle? What three vertices of the pentomino pattern land on the rim of the circle? My guess is head of the snake, tail of the fish, and jaw of the crocodile. $\endgroup$
    – Przemyslaw Remin
    Aug 31, 2022 at 20:50
  • $\begingroup$ Hm... I placed the center 2/9 units up from the center of the middle square, which is the feet of the giraffe. The bounding vertices were the top edge and the left of the bottom edge. But I missed the crocodile snout, which reaches out of that circle. Now, with the critical corners: snake head, whale tail, croco head, I place the center at (0.06557377, 0.229508197) from the center of the giraffe feet and the radius is 4.981894119. $\endgroup$
    – Florian F
    Aug 31, 2022 at 21:34
  • $\begingroup$ Congratulations to your son! $\endgroup$
    – Will Octagon Gibson
    Sep 1, 2022 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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