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.

3 Responses to “Puzzle of the week [w10]”

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

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

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

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: