Le Monde puzzle [48]

December 1, 2010

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

This week(end), the Le Monde puzzle can be (re)written as follows (even though it is presented as a graph problem):

Given a square 327×327 symmetric matrix A, where each non-diagonal entry is in {1,2,3,4,5} and text{diag}(A)=0, does there exist a triplet (i,j,k) such that

a_{ij} = a_{jk} = a_{ki}

Solving this problem in R is very easy. We can create a random matrix A and check whether or not any of the five triple indicator matrices

(A==c)^3,,qquad c=1,ldots,5,

has a non-zero diagonal entry. Indeed, since B=A^3 satisfies

b_{uu} = sum_{v,w} a_{uv}a_{vw}a_{wu}

there is a non-zero entry iff there exists a triplet (u,v,w) such that the product a_{uv}a_{vw}a_{wu} is different from zero. Here is the R code:

for (mc in 1:10^3){

#random filled matrix

#checking for links
for (t in 1:5){
if (agr==1){ break()}

if (chec==0){ break()}

I did run the above and did not find any case where no triplet was sharing the same number. Neither did I for 326. But Robin Ryder told me that this is a well-known problem in graph theory that goes under the name of Ramsey’s problem and that 327 is an upper bound on the number of nodes for the existence of the triplet with 5 colours. So this is another illustration of a case when crude simulation cannot exhibit limiting cases in order to void a general property, because of the number of possible cases.

Incidentally, I wonder if there is a faster way to produce a random symmetric matrix than the cumbersome


Using the alternative saving on the lower triangular part


certainly takes longer…

Filed under: R, Statistics Tagged: graph, graphs, Le Monde, mathematical puzzle, R

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

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, 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.


Mango solutions

RStudio homepage

Zero Inflated Models and Generalized Linear Mixed Models with R

Quantide: statistical consulting and training



CRC R books series

Contact us if you wish to help support R-bloggers, and place your banner here.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)