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.