Colouring a Grid without Rectangles

Given a 5x5 grid, what is the maximum number of squares that can be coloured in, such that no 4 coloured squares form the corners of a rectangle? Find a layout for this number, and prove that this is the maximum.

For example, this is a valid configuration (although it is not the maximum number of coloured squares):

And this is not valid, since the corners form a rectangle:

An observation

If we have an invalid configuration (one where a rectangle is formed), then we are free to swap pairs of rows or columns, and we will still have a rectangle. This is because changing the width/height of a rectangle or even flipping its orientation does not change the fact that it is a rectangle. By repeatedly swapping pairs, we can achieve any ordering we want.

Needless to say, the converse is also true, since swapping two rows or columns is a self-inverse operation.

From this, we can derive (through the contrapositive) that a valid configuration remains valid under reordering of rows or columns.

A claim

It's pretty straightforward to come up with a valid colouring of 12 squares. Here is one such example:

I claim that this is the best we can do. I.e. 13 squares is impossible.

The proof

A useful number to look at is the maximum number of squares per row. Let's call this .

If , then the maximum number of coloured squares is , which is worse than 12.

Something to note, is that a "rectangle" is just two squares in one row intersecting with two squares in another (intersecting meaning that their columns match).

For , say we start with the row of 5. Then every other row can have a maximum of only 1 square! If there were 2 squares in a row, then they would form a rectangle with the first row. So the maximum for is , and we can discard this too.

For , start with a row of 4 like before. If our goal is 13, there are 9 squares remaining, which need to fit into 4 rows. By the pigeonhole principle, at least one row must have 3 squares in it. But any row with 3 squares must have 2 squares overlapping with the row of 4, so this is impossible.

We conclude that we must have . Again, if the goal is 13, we have 10 squares remaining to fit into 4 rows. By the pigeonhole principle, at least 2 of the remaining rows must have 3 squares in.

Let's draw the first row. We can always make the first row look like this, without loss of generality, by our reordering argument.

There's only one way to place the second row (up to reordering of columns):

Now we must place the final row of 3 squares, but it's easy to see that that is impossible. It either has to overlap 2 squares with row 1 or row 2. So we have shown that 13 squares is impossible, and that 12 is the solution.