Puzzle of the week [w10]
The puzzle in last Saturday edition of Le Monde is made of two parts: Given a 10×10 grid, what is the maximum number of nodes one can highlight before creating a parallelogram with one side parallel to one of the axes of the grid? What is the maximum number of nodes one can highlight before creating a rectangle?
Given that I was reasonably busy in this intermission week betwen two meetings, I opted for a computer-based solution. My R programs for solving the parallelogram and the rectangle problems are there and there, respectively. They are both based on random hits on the grid that are accepted or rejected depending on whether or not they satisfy the constraint. Obviously simulation only gives a lower bound on the solution, but the parallelogram program there provides 19 as an answer, which seems to be the correct one. The rectangle R program there produces 34 over iterations but there is no confidence that this is the right number.
Xi'an's Og 
March 12, 2010 at 12:47 am
Ok. I think the problem would be better stated then where it’s explicitly mentioned that the parallelogram or rectangle will be defined by only the four nodes corresponding to its vertices. This is clear in retrospect but initially I was thinking that the edges of the shapes would be “filled in” as it were.
March 11, 2010 at 7:13 pm
Am I missing something, why is 19 the lower bound for the parallelogram case? If we made the entire grid a checkerboard wouldn’t there be 0 parallelograms (with “one side parallel to an axis”). I must not be understanding this puzzle.
March 11, 2010 at 7:22 pm
Roger: my R program finds 19 as the upper number of black dots it can put at random on a grid without creating a parallelogram. Therefore, this is a lower bound on the maximum number under this constraint: there may be a configuration with a larger number of black dots but it is so unlikely that the R program does not exhibit it… Your
solution of using the checkerboard does not work in that if you take the first row and the third row there are 5 columns with black dots on those two rows. Any pair of those 5 columns thus leads to a rectangle, hence to a parallelogram with both sides parallel to the axes of the grid.