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ß…)

6 Responses to “Wrong puzzle of the week [w10]?!”

  1. […] 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 […]

  2. 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.

    • 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….

  3. My bad, that is an upper bound. <=, not =. So 51 is an upper bound. Could you please post Le Monde's reasoning?

    • 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.

  4. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: