18
$\begingroup$

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.

$\endgroup$
5
  • 14
    $\begingroup$ Man this boy sure knows how to have a good time. $\endgroup$ Jul 21, 2015 at 18:26
  • 1
    $\begingroup$ My apologies, I misinterpreted the words $\endgroup$
    – CodeNewbie
    Jul 21, 2015 at 18:47
  • $\begingroup$ "Just do it!" proof time! :D $\endgroup$
    – COTO
    Jul 21, 2015 at 22:10
  • $\begingroup$ Do we have to prove that there is at least one square that is entirely colored black or, do we have to prove that when we sum the areas of the black portions, then they are at least equal to one square unit ? $\endgroup$ Jul 6 at 21:32
  • 1
    $\begingroup$ @HemantAgarwal the second one; the total area should be at least 1. $\endgroup$ Jul 10 at 14:02

4 Answers 4

12
$\begingroup$

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 $$

$\endgroup$
9
  • $\begingroup$ Beautiful solution, even prettier than mine. Good job! $\endgroup$ Jul 21, 2015 at 23:01
  • $\begingroup$ @ArturKirkoryan How did you solve it? $\endgroup$
    – xnor
    Jul 21, 2015 at 23:07
  • 1
    $\begingroup$ First proved it by induction for unit segments on a line. Then projected all squares on a line parallel to one of their sides and applied twice the 1-dimensional case. $\endgroup$ Jul 21, 2015 at 23:13
  • $\begingroup$ I don't follow how this reasoning preserves the colouring. Suppose we follow the top procedure with just two non-overlapping squares. The graph paper happens to have two full squares occupied, so they are cut and stacked. Taking the xor would give white everywhere, whereas the boy would have coloured both squares black. What am I missing from your explanation? $\endgroup$
    – Lawrence
    Jul 21, 2015 at 23:49
  • 1
    $\begingroup$ @HemantAgarwal I posted the solution below. It is nowhere as elegant as this one, but anyway, enjoy :) $\endgroup$ Jul 11 at 6:06
3
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ What if we have several squares at once overlapping with each other? The black areas can look very intricate. $\endgroup$ Jul 21, 2015 at 19:04
  • $\begingroup$ @ArturKirkoryan, it sounds like this solution takes that into consideration: "...to minimize the amount of area colored black we want $A=1$; the squares perfectly overlap." $\endgroup$ Jul 21, 2015 at 19:13
  • 1
    $\begingroup$ @GentlePurpleRain, yeah, but this A=1 applies only if we are trying to minimize the black area resulting from 2 squares alone. Then they should really completely overlap, so that both will vanish. However, I don't think this implies that all of the squares except for one should overlap in pairs. $\endgroup$ Jul 21, 2015 at 19:16
  • $\begingroup$ @ArturKirkoryan I was using the overlapping of two squares to show a way to achieve a minimal area of black. I added another proof that approaches it from another way. $\endgroup$ Jul 21, 2015 at 19:36
  • 1
    $\begingroup$ @dzastergames, after you have placed several squares, overlapping each other, the black areas resulting around can have various shapes. This way when you take some isolated square and start placing it around this construction, it will be hard to analyze what happens exactly. I think you have good intuition, but will need some mathematical approaches to make things rigorous. $\endgroup$ Jul 21, 2015 at 20:33
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

http://i.imgur.com/bVaysoT.png

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

$\endgroup$
2
  • $\begingroup$ Nice picture:) The total black area becomes more than 1, this is what we have to prove. $\endgroup$ Jul 22, 2015 at 2:10
  • 1
    $\begingroup$ Oh I see, I was misread one square unit. And now it's fun again, thanks. Edit: I only made an answer because I was under the impression I couldn't write comments. $\endgroup$
    – millsy
    Jul 22, 2015 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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