# Le Monde puzzle [48]

**Xi'an's Og » R**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

**T**his 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 , does there exist a triplet (i,j,k) such that

**S**olving 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

has a non-zero diagonal entry. Indeed, since satisfies

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

chec=1 for (mc in 1:10^3){ #random filled matrix A=matrix(sample(1:5,(357)^2,rep=TRUE),357) A=A*upper.tri(A)+t(A*upper.tri(A)) #checking for links agr=0 for (t in 1:5){ B=(A==t) agr=max(agr,max(diag(B%*%B%*%B)>0)) if (agr==1){ break()} } chec=min(chec,agr) 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.

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

A=matrix(sample(1:5,(357)^2,rep=TRUE,357) A=A*upper.tri(A)+t(A*upper.tri(A))

Using the alternative saving on the lower triangular part

A=matrix(sample(1:5,(357)^2,rep=TRUE,357) A[upper.tri(A)]=sample(1:5,357*178,rep=TRUE) A=A*upper.tri(A)+t(A*upper.tri(A))

certainly takes longer…

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

**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 about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.