5
$\begingroup$

Attribution: I remember seeing this type of question some time ago but don't remember from where. So I have redesigned the question. Hope that is OK.

You have 5 burger patties to grill. Each side takes 1 minute total to cook. Both sides need full grilling. Your grill can only handle 3 patties at a time. You are in a rush. What is the least amount of time you can fully cook those patties?

$\endgroup$
3
  • $\begingroup$ Does this answer your question? Frying Three Steaks $\endgroup$ Apr 16, 2023 at 13:10
  • 1
    $\begingroup$ @Randal'Thor that problem seems more complicated as you also need to butter and other constraints. $\endgroup$ Apr 16, 2023 at 13:22
  • $\begingroup$ Related: puzzling.stackexchange.com/questions/64558/…, and the classic puzzle of having 6 tires on a four-wheeled vehicle (4 installed, 2 spares), each with 1000km lifetime, trying to reach 1500km distance. $\endgroup$
    – justhalf
    Apr 16, 2023 at 15:09

2 Answers 2

14
$\begingroup$

If we make the (rather dubious) assumption that

all that matters is that each side of each patty should end up having been on the grill for at least 1 minute (so that cooking for 1 minute is equivalent to cooking for 30 seconds, waiting 1 minute, then cooking for another 30 seconds)

then

we can do the job in the theoretical minimum of 10/3 minutes = 3 minutes 20 seconds, as follows. The table has 10 burger-sides along the top, and 10 20-second periods along the left. "##" indicates cooking. "//" indicates the last 20-second period a given burger-side needs.

  1a 1b 2a 2b 3a 3b 4a 4b 5a 5b
0 ##    ##    ##
1 ##    ##    ##
2 //    //    //
3    ##    ##    ##
4    ##             ##    ##
5    //             ##    ##
6          ##       //    //
7          //          ##    ##
8                ##    ##    ##
9                //    //    //

$\endgroup$
-1
$\begingroup$

Assuming the minimum time for a pattie to cook on one side is 1 minute, the answer is

4 minutes

Observe that

With 5 patties there are 10 sides that need to be cooked. Since our grill can only cook 3 patties per minute, we will need at least $\lceil{10/3}\rceil=4$ minutes.

Here is how this lower bound can be reached

Denote patties as A, B, C, D and E. Use numbers to denote which side we are cooking. We can now cook like so:
1. A1 B1 C1
2. D1 E1 A2
3. B2 C2 D2
4. E2

There are many other solutions too.

$\endgroup$
4
  • 1
    $\begingroup$ This puzzle brought back many great memories as this was the first problem I wrote for TopCoder back in 2003. See the general solution to this problem under FryingHamburgers here: topcoder.com/thrive/articles/SRM%20159 $\endgroup$ Apr 16, 2023 at 13:25
  • 3
    $\begingroup$ Why the need for ceiling function here? $\endgroup$
    – justhalf
    Apr 16, 2023 at 15:06
  • 1
    $\begingroup$ Well I was assuming that the minimum time you can have the patties on one side is 1 minute. $\endgroup$ Apr 18, 2023 at 3:19
  • $\begingroup$ Ah, ok. I hadn't considered that case since this is a classic problem for me, where a few things needs to be allocated to a few slots, but one thing can only be used at one slot at a time (one side of steak grilled at a time in this case), and I assume we can do partially. The classic problem is trying to get a car (4 wheels) with 1 spare, where each tire has a lifetime of 1000km, and asking how to reach 1250km. $\endgroup$
    – justhalf
    Apr 18, 2023 at 5:05

Your Answer

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

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