cutting a cake without destroying the square toppings 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.
 A: 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. 

