19
$\begingroup$

When I arrived at Ernie's place last weekend I had some exciting news for him. "did you know", I announced "that a new Kzijekistanian fast-food shop has just opened in town?". "I did", Ernie replied, "because this just arrived in the letter-box", and he held up a glossy flyer that announced:

enter image description here

Spicy Kzijekistanian Filled Flat-Bread Shop

$10.00 per piece

Free delivery*

In accordance with regulations of the Kzijekistanian Ethnic Food Committee (KEFOC), each flat-bread is precisely 1.000 m diameter and will be delivered to your home on a square cardboard tray** designed to keep the bread crisp and fresh as possible (Note: dimensions of the tray will be the smallest possible to minimize any over-lapping or under-lapping of your pre-cut*** flat-bread. (Note: Flat-breads will only be placed one layer deep on the tray)

"I ate those when I was visiting Kzijekistan," said Ernie, "very tasty - and $10 seems to be a very fair price too!".

I scanned down the flyer to the small print:

*Free delivery within 3 km of the shop: In accordance with the wishes of the KEFOC our company has made a permanent arrangement with the local Cargo-Bike Appreciation Club. In exchange for bicycle-delivery of flat-breads, the KEFOC will provide free jerseys and accommodation for club members competing at the Annual National Cargo-Bike Olympic Trials. Your orders will help them in training so they can bring home this year's ANCBOT cup.

"That sounds like a noble cause, shall we order one for lunch?", Ernie asked.

I scanned a little further down the flyer:

**In accordance to the demands of the KEFOC, our company has declared itself to be carbon-neutral. In the interests of minimizing packaging waste, there will be a surcharge of one cent per square cm of cardboard tray that is not covered by flat-bread (surcharge rounded down to the nearest cent).

"But that is preposterous", said Ernie, "an un-cut flat-bread would cost an extra $21.46 in packing surcharge! There is no way I would pay that much for one".

I scanned down a little further:

***As directed by existing KEFOC regulations flat-breads can be pre-cut and optimally re-arranged to fit the smallest possible square cardboard packing tray. Each cut**** must be straight, must reach from circumference to circumference, and all cuts must be made before any pieces are moved or re-arranged.

"Well that solves the problem" I replied (feeling very proud of myself), "all we need to do is order a flat-bread with 99 evenly spaced vertical cuts and 99 evenly spaced horizontal cuts. The little 1 cm squares (plus extra edge bits) would certainly fit into a box no more than 90 cm square..." (I did a quick calculation on the back of an envelope) "...so we wouldn't be paying more than $2.46 for the packaging".

"That is a ridiculous solution!" Ernie replied scathingly, "Firstly, I don't want lots of tiny splinters of flat-bread - I want nice big bits wherever practical, so the minimum number of cuts would be preferable, secondly, the packing charges would still be too much, and thirdly you didn't read the final bit of small print."

I scanned down to the end of the document:

****in agreement with KEFOC edicts, the company must charge a cutting levy of one cent per cut.

"So you would be adding an extra $1.98 just in cutting charges" Ernie explained. "To be honest, I wouldn't be happy eating it unless the total cost of extras (packing surcharge plus cutting levy) made up no more than 10% of the total bill." In the end we decided to order pizza instead.

Now I know Ernie does love Kzijekistanian flat-bread and it would be great to surprise him with a home delivery next weekend. But I know he won't be happy if it is too expensive - even if someone else is paying the bill. Can anyone think of a way to cut the bread that will meet with Ernie's requirements?

Hint 1: Looks like a first hint is in order. Ernie and I did manage to find a solution (flat-bread was lovely and tasty), in which the positioning of the pieces of bread in the box had at least two planes of mirror symmetry (when looked at from directly above the box of course).

Hint 2: The round flat-bread, after it has been cut up, but before any pieces have been moved, has exactly the same rotational symmetry and mirror symmetry as it does after the pieces are rearranged and placed in the square box.

$\endgroup$
  • $\begingroup$ do you get a refund if they are late? $\endgroup$ – JonMark Perry Aug 9 '17 at 5:38
  • 3
    $\begingroup$ @JonMarkPerry Refund? They'd probably charge you. :P $\endgroup$ – Lawrence Aug 9 '17 at 8:07
  • $\begingroup$ I presume that although the last sentence talks about "requirements" and the first bolded sentence merely says "would be preferable" that an answer must come with a proof that no possible dissection with fewer cuts meets the surcharge limit? $\endgroup$ – Peter Taylor Aug 9 '17 at 18:49
  • $\begingroup$ I think that if two (or more) people present solutions that match Ernie's price limit, I would just choose the one that required the minimum number of cuts. $\endgroup$ – Penguino Aug 9 '17 at 21:51
  • $\begingroup$ Well, I think a diagram from my side would be better but right now it seems the problem can be thought of as an 'efficient way of Squaring a Circle' which is a classic old problem of Geometry and an initial investigation suggests an area of ( (Pi)/4 - 1/4) sq.m would be wasted of the flat-bread. And therefore the size of the box would be a square of length 1/(Square root (2)) or apprx. equal to 0.7 m $\endgroup$ – Mea Culpa Nay Aug 12 '17 at 15:36
8
$\begingroup$

Finally, after 5 months of attempting this on and off, I have a solution that meets all of the requirements!

I'll go into a bit more depth below, but here's where the cuts are:

Location of cuts on the flatbread

These pieces can be rearranged:

To fit in an 89x89cm box. While there are 48 pieces total, we'll treat some connected pieces as one, to make rearranging easier:
Pieces in the box

The total cost of this method can be calculated like so:

Wasted area: $$89^2 cm^2 - \pi \times 50^2 cm^2 = 67.01 cm^2$$ So 67 cents from unused area, with 14 cuts, leads to 81 cents in extra charges. This is less than 10% of the total cost!


In depth description:

Box Dimensions:

I found the area (that I used) for the box using a spreadsheet, where the first column has the desired edge length of the box, and the subsequent columns show area, wasted area, cost due to wasted area, and the number of cuts allowed with the given dimensions. I chose 89 cm per edge because it was a whole number that would allow me to make several cuts to get the pieces to fit.
Spreadsheet

The cuts are at:

Horizontal:
- 1cm from the top
- 5.5cm from the bottom
- Directly centered - 5.5cm from the top
- 1cm from the top
Vertical:
- 1cm from the left
- 5.5cm from the left
- Directly centered
- 5.5cm from the right
- 1cm from the right
Diagonal:
- At 45 degrees from horizontal, such that the following lengths are equal:
Required matching lengths

This meant that the flatbread was:

Split into quarters, and each quarter of the flatbread had to fit into a quarter of the box.
The centered vertical and horizontal cuts quartered the flatbread, and the vertical and horizontal cuts 5.5cm in made the majority of each quarter fit in its quarter of the box, like so:
Quarter of the flatbread

The rest of the pieces had to be cut down:

I liked how the right angle filled the edge of the box so nicely, so I made another one with the 45 degree cuts, spaced so that the entire perimeter of the quarter of the box would have flatbread on it:
Quarter of the flatbread, more filled

Unfortunately, those pesky pieces were still too big, so...

I added the extra cuts at 1cm from each edge, to make the pieces thinner. These were able to just barely fit without overlapping:
Quarter of the flatbread entirely in a quarter of the box!

I don't know if this solution is entirely satisfying to me, because:

I had to rely on a graphics editor, as opposed to geometry equations, to fit everything in place, so I don't have a concrete proof that this works, but I'm still fairly confident that it does.

$\endgroup$
  • $\begingroup$ Excellent solution. I have added Ernie's one, which was a little more expensive but in which the cuts themselves were more symmetrical, and less cuts were needed. $\endgroup$ – Penguino Jan 31 '18 at 0:12
4
$\begingroup$

My first idea was to

Cut the flatbread into equal wedges and rearrange them, alternating which end is pointing up.

As you can imagine, there's still a fair bit of inefficiency in the packing, especially at the edges. A simple adjustment greatly improves this, without changing much of the math.

By making one extra cut, we can greatly decrease the length of the required rectangle. Except for very narrow slices, well worth the 1 cent.
Packing strategy
We can find the area that this type of box would take by finding the width and height of the triangle defined by each wedge, and adding them together.

Triangle in a wedge

If there are n + 1 cuts (because of the extra, final cut), we're left with 2n wedges. Given the labeled dimensions above, the width of the resulting rectangle would be:
$W = (2*n) * w$
And the height would be:
$H = 2*r - h$

To find h and w, we use a bit of trig. We find angle a by dividing the circle into 2*n equal parts:
$a = 360 / (4*n) = 90 / n$

Then,
$h = r*\cos(a)$
$w = r*\sin(a)$

The total area of box required is found by combining the equations, to get:

$A = (2nr\sin(90/n)) * ((2 - \cos(90/n)) * r)$

The wasted area is just:
$A - \pi r^2$

We now know enough to find the cost of extras:

Assuming area is calculated in $cm^2$, the cost would be:
$ \$0.01 * (A - \pi r^2 + n + 1)$

For the extras to be less than 10 percent of the total cost, we must reduce them to at most \$1.11. This gives us the final inequality:
$ 1.11 \ge \$0.01 * ((2nr\sin(90/n)) * ((2 - \cos(90/n)) * r) - \pi r^2 + n + 1) $

Plugging that equation into an excel sheet, we find that, using this method, we can meet Ernie's standard with as few as

9 cuts. The cost of extras with this method is \$1.08.

$\endgroup$
  • 6
    $\begingroup$ I was going to post essentially the same answer two days ago and then I realised that the rules say that the box is square. $\endgroup$ – Peter Taylor Aug 11 '17 at 6:45
  • 1
    $\begingroup$ @DrewCamp I guess this type cut results in at least TWO layers of flat-tbread, which violates the condition stated in the last line of the first paragraph of the puzzle. $\endgroup$ – Mea Culpa Nay Aug 11 '17 at 14:00
  • $\begingroup$ @PeterTaylor Somehow I must have skimmed over that requirement... Back to the drawing board! $\endgroup$ – DqwertyC Aug 11 '17 at 16:14
  • 1
    $\begingroup$ Yep, the box must be square. But as for "two layers", I am not sure if you have misinterpreted me or if I have misunderstood you. This just means that you can't stack pieces on top of each other. $\endgroup$ – Penguino Aug 13 '17 at 21:23
4
$\begingroup$

After a couple of months Ernie finally gave up waiting for me to find a solution and sketched out the following so we could actually try the flat-bread at an acceptable price:

enter image description here

This just squeaked below Ernie's price limit.

Price was 10.00 dollars for the flat-bread, 1.03 dollars for the packaging (rounded down from 103.907 cm^2 wasted space), and 0.08 dollars for the cutting. So total price 11.11 dollars, of which packaging and cutting makes up 1.11 dollars or 9.991% of the total.

Looking at DqwertyC's solution, Ernie's is a little more expensive but when I quizzed him on it, he told me that he chose it because it met his requirements and he liked the symmetry (also it gave him a single unbroken piece making up almost 50% of the total area plus four more pieces of almost 10% each!). But he agreed that DqwertyC should win the tick.

Of course it all became irrelevant when he visited the shop again a few days later to discover that the price has gone up to $11.00, but now the flat-breads are sold in circular boxes exactly 1 m in diameter (imagine a very flat hat-box) for no extra charge. So Ernie is pleased that his favorite snack is cheaper, comes in one piece, and also claims that the used boxes are a perfect size and shape for archery targets (more on that later...).

$\endgroup$
-1
$\begingroup$

I don't know what to write that shouldn't be under a spoiler, so:

You totally can order your food.

Because

Just get them to cut the pizza into 1.84cm strips. They'll then fit end to end int a box that's 1.84cm x 85.4cm (It probably would fit in a smaller box, I got the length by just adding all the rectangles it takes to hold each strip). This will result in wasted cardboard of 47 sq cm and 53 cuts. Therefore, you spend $1, which is 10%, the max you are allowed to spend.

$\endgroup$
  • 4
    $\begingroup$ Unfortunately, the rules require that the box be square. $\endgroup$ – Michael Seifert Aug 11 '17 at 14:39

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.