Black and White

Question

OK guys, I think this is my best puzzle yet. Hope you enjoy it, the solution is neat and simple.

A boy draws 2015 unit squares on a piece of paper, all oriented the same way. The squares can overlap. Then he colors the resulting picture in black and white chess-wise, such that any area belonging to an even number of squares is painted white and any area belonging to an odd number of squares is painted black.

Prove that there is at least one square unit of black on the paper when he is finished.

Answer 1

Let's think of the problem as taking XOR's (symmetric differences) of the square areas, with black as 1 and white as 0. The black area is the XOR of all the squares.

Imagine doing this all on graph paper whose cells are sized and oriented like the squares. Take the resulting figure, cut up the occupied cells, and stack them on top of each other without rotating. Now, take the XOR of that stack.

Note that any square on the graph paper gets cut up and rearranged to make exactly the full unit cell. So, the XOR of the stack is the XOR of 2015 fully black squares, which is all black, since 2015 is odd. Then, since each black point in the XOR requires at least one black point the contribute, the total area of black in the stack must be at least 1.

---

Needlessly formally:

We are interested in the group $G$ of (well-behaved) finite-area subsets of the plane under symmetric difference (XOR). We quotient out the plane by integer translations to get $(\mathbb R \times \mathbb R) / (\mathbb Z \times \mathbb Z)$, which induces a homomorphism $\phi$ from $G$ to the corresponding group $G'$ on the unit square.

We have $2015$ single-square elements $x_1, ..., x_{2015}$ of $G$ and are interested in their sum $x$. As single-square elements, they all map to the same full-square element $\phi(x_i) = s$ in $G'$, so $\phi(x) = s + \cdots + s$ summed $2015$ times. Since $G'$ has order $2$, this is simply $s$. But the homomorphism $\phi$ cannot increase the size of the subset, so

$$\mathrm{Area}(x) \geq \mathrm{Area}(\phi(x)) = \mathrm{Area}(s) =1 $$

Answer 2

In order to minimize the area shaded black, we want as many squares possible to perfectly overlap in even numbers. For example, take two squares. Separated, they are both single layers, and therefore provide $2$ $units^2$ of black paint. So we overlap these two. If we let the overlapping area be $A$, we then have $(1-A) + (1-A) = 2(1-A) units^2$ of black area. It is quite easy to see that to minimize the amount of area colored black we want $A=1$; the squares perfectly overlap.

So then we "pair" each square up with one another in order to minimize the amount of area being colored black. In this case we have 2015 squares, forming 1007 pairs with one square left over. The 1007 pairs, no matter how they are distributed, will add 0 black area to the total. So then we are left with the problem of where to place the remaining square in order to minimize the area colored black. Notice that since we formed pairs, our remaining square will be placed in an area that is shared by 0, 2, 4, etc, squares already. Thus no matter where we place our last square, all of its area will be shared by an odd number of squares. So our minimal area being colored black is the area of our one square: $1$ $unit^2$.

Alternative proof:

For $N$ squares, we can clearly see that if there is no overlap, then we will need to fill in a maximal area of $N$ units. So in this setup, we pick one square to "slide" around. If while sliding it around we encounter another square(s), then two things can happen: the total black area remains the same, the total black area decreases. In order for it to remain the same, the square would need to enter a region that is already shared by an even number of squares. If an odd number of squares share the region, then it's like the situation in the solution above where $A$ (the shared area) is now increasing from 0. As $A$ increases, the amount being colored black will decrease.

Thus we can continuously pick and slide squares around on the sheet. If we place the square into a region already shared by other squares, then we know that the total black area is either the same or less. Notice that by sliding squares, we can achieve any possible configuration of $N$ squares on the sheet of paper. Now notice the case where we slide all the squares perfectly onto each other. As $N$ is odd in this case, we know that the area of this configuration is $1$. More importantly, we know from our previous observations, that if we were to alter this configuration by sliding a square away from other squares then the black area will either stay the same, or increase. Thus any configuration of squares will have a minimal area of $1$.

Answer 3

Since a fellow puzzler asked me in the comments to post a proof by induction (not as elegant as the top answer), here it is...

We denote by $X(A_1, A_2, \cdots , A_n)$ the exclusive disjunction of the sets $A_1, A_2, \cdots , A_n$ and start by proving the following Lemma:

---

LEMMA: If there is an odd number of unit segments on a line, then the set consisting of points covered by an odd number of segments has measure of at least 1.

Solution: We denote the segments by $S_1, S_2, \cdots S_n$ and prove that $\mu(X(S_1, S_2, \cdots , S_n))\geq 1$ for each odd $n$ by induction. The statement is trivial for $n=1$ segment. We assume it is true for some $n=2k-1$ and prove that it is true for $n=2k+1$ as well. Consider the two rightmost segments $S_{2k}, S_{2k+1}$ and their exclusive disjunction $X(S_{2k},S_{2k+1})$ which consists of two segments of equal length. The right one of these two segments is disjoint from the exclusive disjunction of the $2k-1$ leftmost segments $X(S_1, \cdots , S_{2k-1})$, so for the total exclusive disjunction we have:

\begin{align}\mu(X(S_1, \cdots , S_{2k-1}, S_{2k}, S_{2k+1})) &= \mu(X(X(S_1, \cdots , S_{2k-1}) + X(S_{2k}, S_{2k+1}))), \\ &\geq \mu(X(S_1, \cdots , S_{2k-1}))\geq 1\end{align}

---

We denote the squares by $A_1, \cdots A_{2015}$ and draw $x$- and $y$-axises that are parallel to their sides. Then, we project them onto the $x$-axis, forming $2015$ unit segments $S_1, \cdots S_{2015}$ on it. By the Lemma we proved above, we have that $\mu(X(S_1,\cdots , S_{2015}))\geq 1$. Note that for each point $x\in X(S_1, \cdots , S_{2015})$, the set $A \subset X(A_1, \cdots A_{2015})$ that projects onto $x$ is the exclusive disjunction of an odd number of unit segments and therefore, again by the Lemma, it has measure of at least $1$. Since every point $y \in X(A_1, \cdots , A_{2015})$ projects onto the set $X(S_1, \cdots , S_{2015})$, the statement follows.

Answer 4

I'm sure I'm misunderstanding something. But here we go:

https://i.stack.imgur.com/XPbk4.png

Overlap 2013 of them on top of each other and have the other two slightly offset.