Some unit squares on an infinite sheet of squared paper are colored green such that:
Every 2x3 rectangle contains precisely two green squares, and:
Every 3x2 rectangle contains exactly two green squares.
How many green squares are there in a 9x11 rectangle?
*** Based on a Russian Math Olympiad problem.
OK. Let's fill in infinite grid with X's (instead of green) and O's, where 2 cells of every 2x3 and every 3x2 is an X.
I actually don't have time for an infinite grid, so let's start with a 4x4, whose columns are ABCD and whose rows are 1234. Place an X in B2.
Can there be an X in C2? It turns out that the answer is no.
If C2 has an X, then this forces O's in B3, C3, B4 and C4.
Also, it forces have O's in D2 and D3. But this leaves the rectangle with corners at B3 and D4 with 5 O's, which doesn't work. Therefore, our infinite grid cannot have two X's horizontally or vertically adjacent.
So, If there is an X in B2, this forces an O at B1, B3, A2 and C2.
There must be at least one X diagonally adjacent, because otherwise A3 and C3 are both O's, and this leaves the rectangle with corners at A2 and C3 with 5 O's, which doesn't work.
So, without loss of generality, place an X at C3, diagonally adjacent to the X at B2.
This forces O's at A2, A3, B2, C2, B4, C4, D2 and D3.
This in turn forces an X at A1 and D4, from which it follows that any X must be part of an infinite diagonal of X's.
Also, it forces an X at A4 and D4, and each of these must be part of their own infinite diagonal, parallel to the diagonal that contains B2, but three to the left and three to the right.
And, as Jer said, any 9x11 grid on the infinite extended space has 3 X's in each of the 11 rows (or columns), for a total of 33 X's.
Edited on September 23, 2014, 1:27 pm
A proof
