17
$\begingroup$

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.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Are you disallowing horizontal/vertical aligned rectangles, or any rectangles including e.g. (in chess notation) $\{a2,b1,b3,c2\}$? (See comments under my answer.) $\endgroup$ – Rand al'Thor Feb 16 at 12:59
  • 2
    $\begingroup$ Ah, we just disallow the horizontal/vertical aligned rectangles. If any rectangles, the left example is false because a5, b6, d2, e3. $\endgroup$ – athin Feb 16 at 13:28
  • 2
    $\begingroup$ 21 is the maximum, as reported in OEIS A072567. $\endgroup$ – RobPratt Feb 16 at 18:10
  • 1
    $\begingroup$ This is a good old problem. I first met it when I was a schoolboy, learning a problem from All-Soviet-Union mathematical competition from the year when I was born. :-) In this answer at Mathematics.SE I briefly surveyed the generalization of this problem to rectangular boards and its mathematical side. $\endgroup$ – Alex Ravsky Feb 17 at 21:11
20
$\begingroup$

Here's the solution:

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ But there are lots of rectangles here: e.g., in terms of your labels, C/ABC - D/ADE - B/BDF - A/AFG. Perhaps the puzzle was meant to say "no axis-aligned rectangles" or something, but if not then I think it's asking for something more difficult. $\endgroup$ – Gareth McCaughan Feb 16 at 12:54
  • 1
    $\begingroup$ @Gareth Heuristically it seems like 21 painted squares is the maximum under the restriction of no axis-aligned rectangles. I'd guess that ruling out oblique rectangles would make 21 impossible, and that the OP's intent was just to disallow axis-aligned rectangles. Also, checking page 10 of the linked source, the original problem says "subboard" which suggests axis-aligned. But I've left a comment on the question to clarify. $\endgroup$ – Rand al'Thor Feb 16 at 12:59
  • 1
    $\begingroup$ I agree it's likely that your answer matches the actual intent. $\endgroup$ – Gareth McCaughan Feb 16 at 13:25
  • 2
    $\begingroup$ Yeah, it has to be axis-aligned. I rewrite the problem in hope for an easier description, but that's actually crucial.. Anyway this answer is correct, well done! $\endgroup$ – athin Feb 16 at 13:33
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This! Is the intended solution in the contest and generalizing the answer (Block Design concept specifically), tho it may be too mathy for regular people but highly recommended to those who're interested. (I also just learnt about it from my friend along with telling me about this puzzle.) $\endgroup$ – athin Feb 16 at 23:04
  • 1
    $\begingroup$ This provides the mapping between a set of lines+vertices and the painted squares on a board with the same size. But then wouldn't the actual work be how to find such combination of 7 lines and 7 vertices such that every line incident with 3 vertices? $\endgroup$ – justhalf Feb 17 at 1:42
  • $\begingroup$ I guess, but luckily Fano did that already, and I linked it. $\endgroup$ – Magma Feb 17 at 9:18
3
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Sorry, edited it. $\endgroup$ – Nautilus Feb 16 at 15:27
3
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.