13
$\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$
  • 12
    $\begingroup$ Man this boy sure knows how to have a good time. $\endgroup$ – Going hamateur Jul 21 '15 at 18:26
  • 1
    $\begingroup$ My apologies, I misinterpreted the words $\endgroup$ – CodeNewbie Jul 21 '15 at 18:47
  • $\begingroup$ "Just do it!" proof time! :D $\endgroup$ – COTO Jul 21 '15 at 22:10
8
$\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$
  • $\begingroup$ Beautiful solution, even prettier than mine. Good job! $\endgroup$ – Puzzle Prime Jul 21 '15 at 23:01
  • $\begingroup$ @ArturKirkoryan How did you solve it? $\endgroup$ – xnor Jul 21 '15 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$ – Puzzle Prime Jul 21 '15 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 '15 at 23:49
  • $\begingroup$ @Lawrence All of that is right. If you had three squares though, the xor of the stack would be black everywhere, so there must be at least 1 black area. $\endgroup$ – xnor Jul 22 '15 at 0:18
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$
  • $\begingroup$ What if we have several squares at once overlapping with each other? The black areas can look very intricate. $\endgroup$ – Puzzle Prime Jul 21 '15 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$ – GentlePurpleRain Jul 21 '15 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$ – Puzzle Prime Jul 21 '15 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$ – dzastergamer Jul 21 '15 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$ – Puzzle Prime Jul 21 '15 at 20:33
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$
  • $\begingroup$ Nice picture:) The total black area becomes more than 1, this is what we have to prove. $\endgroup$ – Puzzle Prime Jul 22 '15 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 '15 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.