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 square cake. It contains N toppings - N disjoint axis-aligned squares. The toppings may have different sizes, and they do not necessarily cover the entire cake.

I want to divide the cake into 2 rectangular pieces, by either a horizontal or a vertical cut, such that the number of toppings I destroy (i.e. cross in the interior) is minimized.

What is the number of toppings I will have to destroy, in the worst case?

NOTE: I asked a related question where the toppings may be arbitrary rectangles, and MvG found an example where $\frac{N}{4}$ toppings are destroyed. This example obviously does not work when the toppings must be square.

share|improve this question
    
$\frac{N}{4}$ is also not an upper bound yet. Consider the cake with only one topping, that covers the whole cake. –  Arthur Oct 24 '13 at 13:43
    
I give an upper bound below, but it's not tight. My conjecture is that you can construct cases where $c \sqrt{N}$ toppings need to be destroyed for arbitrarily large $N$ for $c=1/2$, but not for any larger $c$. –  mjqxxxx Oct 24 '13 at 14:47

1 Answer 1

up vote 5 down vote accepted

Let the cake be a unit square; let $l_1,l_2,\ldots,l_N$ be the lengths of the $N$ toppings; and let $f(x)$ be the number of toppings destroyed through by a vertical cut at $x\in(0,1)$. The $i$-th topping increases $f(x)$ by one over an interval of length $l_i$, so $$ \int_{0}^{1}f(x)dx=\sum_{i}l_i, $$ and $$ \min_{x\in(0,1)}f(x) \le \sum_i l_i. $$ So you cannot need to destroy more than $\sum_i l_i$ toppings; this is an upper bound for fixed $l_i$. Also, since the toppings are disjoint we have $\sum_i l_i^2 \le 1$. The maximum of $\sum_i l_i$, subject to $\sum_i l_i^2\le 1$, is achieved when each $l_i=1/\sqrt{N}$, giving an upper bound:

In the worst case, no more than $\sqrt{N}$ toppings need to be destroyed.

This upper bound is presumably not tight, because the regular arrangement of $m^2$ square toppings into an $m\times m$ grid presents "seams" along which the cake can be cut without destroying any toppings at all. In order to force a large number of toppings to be destroyed, some irregularity needs to be introduced, making the packing less snug.

For a concrete example, we can place $m^2$ equal-sized toppings onto an $m\times m$ grid such that each topping has a "margin" of size $\varepsilon$ in each direction within its grid square, except that no margins are left along the edges of the cake. We then slide each topping by $2\varepsilon$ in one of four directions: north, south, east, or west. (Toppings pushed toward an adjacent edge of the cake do not move.) The toppings will remain disjoint provided that no two adjacent toppings are pushed toward each other. Cuts through the middle of grid squares will destroy $m$ toppings; but cuts through the "margins" will only destroy those toppings that have been pushed into the margin; and cuts within $2\varepsilon$ of a margin (or a cake edge) will only destroy those toppings that have not been pushed away from that margin. Use the following arrangement of displacements (repeating as necessary): $$ \begin{matrix} \vee & \lt & \wedge & \gt \\ \gt & \vee & \lt & \wedge \\ \wedge & \gt & \vee & \lt \\ \lt & \wedge & \gt & \vee \end{matrix} $$ Then no two adjacent toppings are pushed toward each other, and the best cuts (through the margins) destroy $m/2$ toppings. Hence:

When $N$ is an even square, the toppings can be arranged so that any cut destroys at least $\frac{1}{2}\sqrt{N}$ toppings.

share|improve this answer
    
This is a very interesting construction, and I think all 16 elements of it are essential, therefore it works only when $N=16k^2$. –  Erel Segal Halevi Oct 24 '13 at 17:15
    
@ErelSegalHalevi: I think it works if you use the upper-left ($2\times 2$) quadrant only, or the extension to the east and south out to any even grid size. (While the lower-left quadrant, for instance, doesn't work.) –  mjqxxxx Oct 24 '13 at 17:59
1  
When m=2, if you use the upper-left quadrant, you can make a horizontal cut in the middle, that cuts no toppings. However, it is easy to change it to a working example. I think that, in order to create a working example, You must slide at least 1 topping in each of the 4 directions. –  Erel Segal Halevi Oct 25 '13 at 5:19

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.