Piece of Cake

Question: How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut.

Answer: Simple question right? There are two possible solutions to this problem. People often overlook the easier solution to this problem. Let’s start with the easiest solution. If you make one straight horizontal cut along the height of the cake, the resulting slices are of equal sizes. But this solution may not work so well on a cake with icing. So let’s rethink.

In general, when a straight cut is made at any angle through the center of a  rectangle, the resulting pieces are always of equal area. So let’s consider our situation. What if we make a straight cut such that it passes through the center of both the rectangles? Since the cut halves both the rectangles, the resulting two pieces are guaranteed to have equal area. Each piece has an area equal to half the original cake minus half the area of the missing rectangular piece. This results in two pieces of equal size, assuming the cake’s height is same at all points 🙂

Liked this post? Please Digg or Stumble it.

If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:

Book Cover

19 Responses

  1. Ojal says:

    I think the cake cut diagonally from the removed part through the mid point till the other end will give the two equal halves.

  2. We have to cut the cake diagonally from the side which takes the removed portion, So that we can go through the mid points of both the rectangles by single straight cut .

  3. We have to cut the cake diagonally from the side which takes the removed portion, So that we can go through the mid points of both the rectangles by single straight cut.

  4. ash says:

    cut the cake vertically at same breadth

  5. laxatives says:

    Nevermind, I’m an idiot. I think Convinced gives a legible answer to the problem.

  6. laxatives says:

    Both of these solutions assume the first rectangle is evenly divided along some axis. If the rectangular slice isnt perpendicular along x,y, or, z, there isn’t a simple answer to this problem

  7. Let’s make believe that the cake is of uniform rectangular shape and density (a block). Here is one simple solution… Balance the cake on a fulcrum (i.e. a piece of suspended wire or something similar) and then cut it at the fulcrum! No fancy stuff needed.

  8. Jeffro says:

    What I meant to say was: What if the 1st point was the center of the missing rectangle and the 2nd point was the center of the cake (when it was whole). Use those two points to define the cut line.

    This effectively cuts the cake in half, and the missing piece in half, leaving 2 equal pieces regardless of where the first piece was cut.

  9. Jeffro says:

    What if the 1st point was the center of the missing rectangle and the 2nd point was the center of the cake (when it was whole). Slice between the two lines.

  10. Not convinced, please post a pic of a rectangle with another rectangle anywhere inside it that you think cannot be bisected by method 2.
    I will then show you how to bisect it. No matter where the centers of the two rectangles lie, you can always find a line that fits both points. Even if those centers lie in empty “non cake” space. 🙂

  11. @Not convinced

    So you mean to say that, you can’t connect two points with a line??
    Point —> Center of Rectangle
    Line —> Straight cut

  12. bilashi says:

    Cake is 3 dimensional rectangular shape having length(x), width(y) and height(h)
    If Cake is cut through the middle of h(height), then we have two half of cakes, it does not matter from where rectangular piece was cut

  13. Brian B. says:

    I am unhappy with this solution. As “Very Unconvinced” said, what if the slice is from within the cake?
    I like his idea of using mass.

    The following assumes that the cut region is inclusive to the cake, and does not initially leave the cake in two pieces.
    Let the piece be of dimensions a,b with any rotation and have a centroid at vector P.
    Let the original cake be of dimensions m,n and have a centroid at vector C.
    After the cut, the cake’s new centroid is vector N = (mnC-abP)/(mn-ab).

    Any cut through this new centroid N will have equal mass on either side of the cut.
    But to make sure the remaining cake is cut into two pieces you need to follow a simple rule.

    If any of the cut is to go through the void of the original piece,
    it must also go though any shared border between the piece and the cake.
    A shared border can be either a side or a point (if the piece was rotated).
    You don’t have to worry about the case of two points of intersection since
    we assumed the cake would still be in one piece before we make our cut.

    If no such border exists, cut anyway you like through N. It wont matter as the piece is convex.

  14. Dont Know says:

    i feel a diagonal cut would make it into equal halves.

  15. not robust says:

    It’s not hard to have the initial missing rectangle intersect that straight cut, thus making it actually two straight cuts that result in 3 pieces. (For example, have the initial missing rectangle be most of the cake, leaving a thin L for the two remaining rectangles.)

  16. Stumble. says:

    Second solution might not always cut into two pieces, there is a possibility that it will ended into 3 pieces.

  17. There is no diagram provided with this picture, and so we have to assume that “any size and orientation” means the cut out rectangle could be anywhere. The current solution seems to indicate that the remaining could can be mentally divided into two disjoint rectangles, but this is only possible if the missing piece contains one of the original corners of the cake.

    Consider what happens if a piece is removed from the center of the cake. Then the minimum number of disjoint rectangles into which the cake can be divided is four! In this case, it is impossible for a straight cut to contain the centers of all the rectangles, so the given solution cannot work.

    We can make this even more tricky! Let’s assume the piece cut out of the center is a rectangle rotated by 36 degrees with respect to the orientation of the outer boundary of the cake. Now there is no way to mentally divide it into disjoint rectangles.

    As you can see, a solution to this problem must be extremely general, and the simplest one is this: Pick up the cake and balance the tray on one finger. Mark the balance point by poking your finger in the icing directly above it. Set the cake down and make any straight vertical cut through the middle of this indentation.

    This technique assures that both parties will get the same amount of cake (by mass or by volume) under the assumption that the cake has uniform density and is the same height everywhere.

    But we can be more general and remove these assumptions! In fact, there is a theorem that asserts that there exists a plane cut through the center of mass which evenly divides the mass no matter how it is distributed!

    Lastly, I want to mention in passing that if one can compute the mass distribution of the cake (any cake, period) any project it directly onto any line, then one can find a straight cut perpendicular to that line that evenly divides the cake by solving a single equation in one variable. (Said cut may not go through the center of mass however.) This would be the preferable method of dividing our uniform rectangular cake with removed parallaxial rectangle, since the mass distribution can be determined just by looking at it. No need to even pick the cake up!

  18. Convinced says:

    For the second solution, there is a 100% chance of a straight cut on the line connecting the centers of the two rectangles to halve them both.

  19. For the second solution, you’d be pretty lucky to have a single straight cut available which halves both rectangles….

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>