Using a 7 x 7 grid, what are the most number of dots that can be selected from the grid so that no 4 dots?

Question

can be connected to form a rectangle with sides parallel to the sides of the grid?

My answer is 18 yet the correct answer is higher.

Any assistance would be greatly appreciated.

Answer 1

You can also think of this as selecting dots from the grid so that no two rows share a pair of columns selected. I've found this the most useful way to think about it when I'm playing with it.

Anyway, if x represents a selected dot and - one that is not selected, I have found 21 with this pattern:
x x x - - - -
- - x x x - -
- - x - - x x
- x - x - x -
- x - - x - x
x - - x - - x
x - - - x x -

Obviously you can permute the rows and columns as you like, so feel free to play around with this if you want to make it symmetrical. ;-)

[edit] ... and looking at Scythian's solution again, I note that you can actually add 2: 6 to this, which makes it symmetrical and brings it up to 21. How did you miss that one, Scythian?

Note that each possible pair of columns is selected in some line or other. I suspect that this is the best possible, though I don't have a formal proof at this stage. I can do a decent hand-waving argument along these lines: There are 7C2 = 21 possible combinations of columns, and we want to use the maximum number of dots to get them. If we have n dots on a line, that uses up nC2 combinations; this number increases faster than linearly, so having (n+1) dots on one line and (n-1) on another uses up more combinations than having n dots on each line, which is bad because it means there are fewer combinations left for other lines (and so we must use fewer dots on those lines). So the ideal configuration will use 21/7 = 3 combinations on each line, giving nC2 = 3 => n(n-1) = 6 => n = 3 dots on each line, for a maximum of 21 dots.

What I also found interesting is that you can get a pretty high number (18) with a very simple pattern:
x x x x x x -
x - - - - - x
- x - - - - x
- - x - - - x
- - - x - - x
- - - - x - x
- - - - - x x

Answer 2

The best I can do by this time is 20. Maybe more is possible, but I can't prove anythng yet. The pattern is almost symmetric, but not quite. The location of the dots can be as follows, row by column:

1: 2,3,7
2: 1,2
3: 1,3,4
4: 3,5,6
5: 4,6,7
6: 2,4,5
7: 1,5,7

The odd man out is 6:2