Le Monde puzzle [48]

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. Or appears to be. We can indeed 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:

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 code and did not find any case where no triplet was sharing the same number. Neither did I for 326, 325,… 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/numbers. 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. To improve the chances of uncovering the boudary value, we would need a simulation that dis-favours triplets with the same number. I am also curious to see Le Monde solution tomorrow, since finding Ramsey’s numbers seems to be a hard problem, no solution being provided for 6 colours/numbers.

Incidentally, 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…

One Response to “Le Monde puzzle [48]”

  1. […] Monde puzzle [48: resolution] The solution to puzzle 38 given in Le Monde this weekend is rather direct (which makes me wonder why the solution for 6 […]

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 )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 705 other followers