Puzzle of the week [w10]

March 10, 2010
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

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.


Filed under: R Tagged: Le Monde, mathematical puzzle

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.