Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a cake with $n$ toppings. I want to cut a small piece out of each topping, such that the remaining cake is connected. Is this always possible?

SOME FORMAL DETAILS (possibly not all of them are relevant for a general solution):

  • The cake is a square.
  • All toppings are pairwise-interior-disjoint axis-parallel rectangles.
  • The pieces should be pairwise-interior-disjoint axis-parallel rectangles.
  • The size of each piece should be more than 0 and less than half of the size of the corresponding topping.

1-DIMENSIONAL CASE:

when the cake, toppings and pieces are all 1-dimensional segments, the answer is NO. Specifically, assume the cake is the segment $[0,n]$, and the toppings are the segments $[i,i+1]$ for $i \in \{0..n-1\}$. It is clear that any attempt to cut a small piece from more than 2 toppings will create a disconnected remainder. My question is: is this result also valid in 2 dimensions?

share|improve this question
    
It seems to me that if the toppings are axis-parallel rectangles, as you say, you could consider the projection of the cake onto a horizontal line. You then have that the toppings are (not necessarily distinct) intervals of the line. But you know one-dimensional cases where the cake cannot be properly divided, so any two-dimensional cake whose projection is one of these bad one-dimensional cases will also be bad. On the other hand, there is hope, because if each topping is a horizontal strip, you can cut vertical slices that cross each strip. –  MJD Dec 8 '13 at 10:30
1  
"there is hope, because if each topping is a horizontal strip, you can cut vertical slices that cross each strip." - exactly, this is what I think. The difference between 1 and 2 dimensions is that in 2 dimensions you don't have to cut the entire horizontal strip - you can cut just a vertical strip and leave some open space for connection. –  Erel Segal Halevi Dec 8 '13 at 12:18
1  
Probably I misunderstood the problem, but it seems to be trivial. Let $A_1,\dots, A_n\subset [0;1]^2$ be the toppings such that $\operatorname{int} A_i\not=\emptyset$ for every $i$. We can easily choose points $z_i\in\operatorname{int} A_i$ for every $i$ such that no two different points $z_i$ has equal abscissas. –  Alex Ravsky Dec 12 '13 at 21:17
1  
Therefore we can slightly inflate each point $z_i$ to a small rectangle $R_i\subset \operatorname{int}A_i$ having mutually non-intersecting orthogonal projections on the horizonal side of the square. Then the boundary of the square $[0;1]^2$ is contained in the set $L=[0;1]^2\setminus\bigcup_{i=1}^n R_i$ and each point from $L$ can be connected by a vertical line with the boundary. –  Alex Ravsky Dec 12 '13 at 21:17
1  
@AlexRavsky It seems you are right. The conclusion holds even if each piece must be, for example, exactly one quarter of the area of its topping: if the topping is $a \times b$, then you can cat a rectangle of sides $a/2 \times b/2$, symmetrically centered within the topping, so the remainder of the topping is connected to the neighbouring toppings. Now this really looks trivial... –  Erel Segal Halevi Dec 15 '13 at 11:06

1 Answer 1

up vote 3 down vote accepted
+50

The problem seems to trivial. Let $A_1,\dots, A_n\subset [0;1]^2$ be the toppings such that $\operatorname{int} A_i\not=\emptyset$ for every $i$. We can easily choose points $z_i\in\operatorname{int} A_i$ for every $i$ such that no two different points $z_i$ has equal abscissas. Therefore we can slightly inflate each point $z_i$ to a small rectangle $R_i\subset \operatorname{int}A_i$ having mutually non-intersecting orthogonal projection on the horizonal side of the square. Then the boundary of the square $[0;1]^2$ is contained in the set $L=[0;1]^2\setminus\bigcup_{i=1}^n R_i$ and each point from $L$ can be connected by a vertical line with the boundary.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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