Wrong puzzle of the week [w10]?!
In the weekend supplement to Le Monde, the solution of the rectangle puzzle is given as 32 black squares. I am thus… puzzled!, since my R program there provides a 34 square solution.
Am I missing a hidden rectangle in the above?! Given that the solution in Le Monde is not based on a precise mathematical argument (something to do with graph theory???), it may be that the authors of this puzzle got their reasoning wrong… (The case of the parallelogram is clearer, the argument being that an horizontal distance between two black squares can only occur once.) An open problem (?) is then to figure out a formula for the number of black squares on an nxn grid without any rectangle. (I wonder how this is linked with the friendly queen puzzle set by Gauß…)
Xi'an's Og 
March 16, 2010 at 12:14 am
[…] 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 […]
March 13, 2010 at 11:22 pm
According to http://www.research.att.com/~njas/sequences/A072567, your 34 solution is optimal. I think a general solution is still probably an open problem.
March 14, 2010 at 8:24 pm
I found the beginning of a reference : a paper published in 1992 by Stephen Davis, I should be able to get hold of it tomorrow, The 1987 paper by Mendelsohn also seems to address the problem….
March 13, 2010 at 6:46 am
My bad, that is an upper bound. <=, not =. So 51 is an upper bound. Could you please post Le Monde's reasoning?
March 13, 2010 at 7:13 am
The solution goes like this: “The optimal solution must correspond to settings where rows include 3 or 4 entries, because using 5 entries eliminates too many cases from the following rows. Here is a grid with 32 entries (2 rows of 4 and 8 rows of 3). A simple reasoning shows that having more than 2 rows with 4 entries imposes corresponding rows with 2 entries.” Hardly convincing… The last part is wrong: in my 34 entries example, I get 4 rows with 4 entries and 6 with 3 entries. None with 2.
March 13, 2010 at 6:03 am
I doubt this is an open problem. Rectangles on the nxn grid can be represented as cycles of length 4 on a bipartite graph of 2n nodes. Is the solution/method that Le Monde posted? (I take it that solution is not online otherwise you would’ve linked to it.) The equation giving the general solution of the maximum number of edges in an mxn bipartite graph is given in this paper http://www.cims.nyu.edu/~naor/homepage%20files/bipartite2k.ps
(It is the first equation listed, where k would equal 2.) k of 2 gives a solution of 10*sqrt(10) + 10 + 10 = 51 (or 52, depending if the floor or ceiling function is used, but I’m pretty sure it’s the floor function.)
So, Le Monde is almost certainly wrong.