Paint 21 Squares of a 7×7 Board Without Forming a Rectangle

Question

_{Got a nice puzzle from my friend, when he was competing in IWYMIC/IMC 2011.}

---

Paint $21$ of the $49$ squares of a $7 \times 7$ board so that no four painted squares form the four corners of a rectangle.

As an example, the left board here is a valid solution for $10$ painted squares, whereas the right one is invalid because of the $4$ X-marked painted squares form the corners of a rectangle.

Answer 1

Here's the solution:

There's a very neat method for finding this, inspired by the no-computers way of solving another related puzzle. Namely,

put labels $A, B, C, D, E, F, G$ along the top for each column, and then label the rows by certain subsets of the set $\{A, B, C, D, E, F, G\}$.

More specifically, given the constraints of this problem:

• 7 rows, so 7 different subsets;

• 21 painted cells, so each subset should be of size 3;

• no rectangles, so no pair of subsets has two elements in common.

How can we achieve this?

Without loss of generality, say the first subset is $\{A,B,C\}$. The six remaining subsets are found by associating each one of $A,B,C$ together with one of the three ways of dividing $\{D,E,F,G\}$ into pairs.

The way I used (unique up to swapping of rows and columns) is

ABC, ADE, AFG, BDF, BEG, CDG, CEF.

That gives the following grid:

A B C D E F G
ABC - - -
ADE - - -
AFG - - -
BDF - - -
BEG - - -
CDG - - -
CEF - - -

which is what I put at the top in nicer formatting.

Answer 2

Short solution with generalization potential:

Consider the finite projective plane with 7 vertices and 7 lines. Number the points of that plane, number the lines of that plane, then paint the square at coordinates $(i,j)$ if and only if the $i$-th line goes through the $j$-th point. Since each line is incident to three points, there are exactly $21$ squares painted, and there is no axis-aligned rectangle $(a,c),(a,d),(b,c),(b,d)$ formed by four painted squares, because that rectangle would correspond to two different lines $a,b$ in the projective plane that have two different points $c,d$ in common.

Answer 3

Swapping rows and columns works.

First, we have to determine if a row can have 4 or more painted squares ($n$). If so, the $nx7$ rectangle on the left will have $n+6$ painted squares at most, allowing the "unaffected" side (whose width is $7-n$ ie. 3 at most and height is 6) to have at least $15-n$. If one row of this rectangle had 3 painted squares, at most 8 squares would be painted in total. If no rows had that, at most 9 squares would. $9>=15-n$, so $n>=6$, and it just doesn't work.

That means all rows must have 3 painted cells each, like so:

xxxoooo
oooxxoo
ooooxxo
oooooxx
oooxoxo
ooooxox
oooxoox

Go back to the left:

xxxoooo
oxoxxoo
xoooxxo
oxoooxx
ooxxoxo
ooxoxox
xooxoox

Answer 4

Here's a solution. I don't have much to say about it other than the fact it looks elegant and is different from the others posted.

 1 1 0 0 0 1 0 
 0 1 1 0 0 0 1 
 1 0 1 1 0 0 0 
 0 1 0 1 1 0 0 
 0 0 1 0 1 1 0 
 0 0 0 1 0 1 1 
 1 0 0 0 1 0 1