Solving the rectangle puzzle

Given the wrong solution provided in Le Monde and comments from readers, I went to look a bit further on the Web for generic solutions to the rectangle problem. The most satisfactory version I have found so far is Mendelsohn’s in Mathematics Magazine, which gives as the maximal number

for a grid. His theorem is based on the theory of projective planes and must be such that a projective plane of order exists, which seems equivalent to impose that is a prime number. The following graph plots the pairs when along with the known solutions, the fit being perfect for the values of of Mendelsohn’s form (i.e., 3, 7, 13).

Unfortunately, the formula does not extend to other values of , despite Menselsohn’s comment that using for the positive root of the equation and then replacing by nearby integers (in the maximal number) should work. (The first occurrence I found of a solution for a square-free set did not provide a generic solution, but only algorithmic directions. While it is restricted to squares. the link with fractal theory is nonetheless interesting.)