Enigma 1452 — Crossed lines

by Susan Denham

                
                
                
                
       How many rectangles can been seen in this 4×4 grid of squares (shown on the left)? In fact there are exactly 100.

I made a much larger square grid with lines dividing it into little squares (a three-figure number of little squares, in fact) and I calculated the number of rectangles which could be seen in this new grid. I then cut the grid along one of the lines in order to make two rectangular pieces, and I calculated the number of rectangles visible in each of my two new pieces. The total of these two numbers was exactly two-thirds of the number visible in my original large square grid.

What was the size of my original grid before I cut it?

Initially think of a row of n−1 squares to which we add a further square (shown red) to make a row of n squares.
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ...                      
In this extended row of n squares there will be n rectangles that include the square shown in red.
They are formed by adding in the next square on the left until we have all n squares with the whole row as a single big rectangle.
None of these rectangles was in the original row of n−1 squares, and all of the other rectangles in the new row were in the original row because they do not contain the red square.

Thus when we add the nth square to a row we add in n new rectangles, and the number of rectangles in a row of n squares is:
            1 + 2 + 3 + ... + n = ½ n ( n + 1 )

We now look at m−1 such rows of n squares, and add in an mth row:
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ...
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ...                     
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ...                     
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ...                     
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ...                     
This will add in ½n(n+1) red rectangles and also more rectangles which have red squares at the bottom.
There are m of these extra rows rows when we include the row of all red squares.

So the total number of rectangles will be:
            ½ n ( n + 1 ) [ 1 + 2 + 3 + ... + m ] = ¼ n ( n + 1 ) m ( m + 1 )

For a 4×4 grid (i.e. n = m = 4 ) we have:
            ¼ × 4 × 5 × 4 × 5 = 100

Let the much larger square be n×n, and let the width of the two strips be m and n−m.
            3 [ ¼ n ( n + 1 ) m ( m + 1 ) + ¼ n ( n + 1 ) (n − m) ( n − m + 1 ) ] = 2 × ¼ n ( n + 1 ) n ( n + 1 )
Also we know that:
            100 ≤ n2 < 1000   \ 10 ≤ n ≤ 31      and    m < n    and    m and n are both positive integers.

Divide through by ¼ n ( n + 1 )
            3 [ m ( m + 1 ) + (n − m) ( n − m + 1 ) ] = 2 n ( n + 1 )
            3 [ m2 + m + (n − m)2 + n − m ] = 2 n ( n + 1 )
            3 [ n2 + 2 m2 − 2 n m + n ] = 2 n2 + 2 n
            n2 + n + 6 m2 − 6 n m = 0
This re-arranges to:
            n ( n + 1 ) = 6 m ( n − m )
If either n or n+1 is a prime number p then either m or (n−m) will need to be p or a multiple of p. but both m and (n−m) are less than n (note: n ≤ p).
So neither n nor n+1 can be prime, and n ( n + 1 ) must be a multiple of 6. Non-prime candidates for n for which n+1 is also non-prime are:
            n = 14   gives   m ( 14 − m ) = 7×5 = 35
            n = 15   gives   m ( 15 − m ) = 5×8 = 40
            n = 20   gives   m ( 20 − m ) = 10×7 = 70
            n = 21   gives   m ( 21 − m ) = 7×11 = 77
            n = 24   gives   m ( 24 − m ) = 4×25 = 100
            n = 25   gives   m ( 25 − m ) = non−integer
            n = 26   gives   m ( 26 − m ) = 13×9 = 117
            n = 27   gives   m ( 27 − m ) = 9×14 = 126

These are the only values of n for which there is any prospect of yielding and integer solution for m.

In general:
            m2 − n m + c = 0       where    c = n ( n + 1 ) / 6, is the number on the right of the above table.

In order for there to be an integer solution for m, we need the discriminant of the quadratic ( n2 − 4 c ) to be a perfect square. A quick bit of cheating with a spreadsheet, reveals that this only happens for n = 27, giving a value for m of 6.

Therefore the original grid was 27×27 little squares.