# Cutting rectangles while keeping the remainder connected

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?

-
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
"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
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
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
@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

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.