## [not] Le Monde puzzle (solution)

**F**ollowing the question on dinner table permutations on StackExchange (mathematics) and the reply that the right number was *six*, provided by hardmath, I was looking for a constructive solution how to build the resolvable 2-(20,5,1) covering. A few hours later. hardmath again came up with an answer, found in the paper *Equitable Resolvable Coverings* by van Dam, Haemers and Peek (2002). In the meanwhile (and even during the Big’MC seminar of yesterday!), I had been thinking of a simulated annealing implementation, which actually was used by van Dam, Haemers and Peek. Here is my (plain) R code

#initialisation of tables #rows for individuals, columns for courses T=sample(rep(1:4,5)) for (i in 2:6) T=cbind(T,sample(rep(1:4,5))) #encounters table meet=function(T){ M=outer(T[,1],T[,1],"==") for (i in 2:6) M=M+outer(T[,i],T[,i],"==") M } #number of missed encounters penalty=function(M){ sum(M==0) } penat=penalty(meet(T)) N=10^5 gamma=100 for (t in 1:N){ #random pick of switched individuals prop=sample(1:20,2,prob=apply(meet(T)==0,1,sum)) cour=sample(1:6,1) Tp=T Tp[prop[1],cour]=T[prop[2],cour] Tp[prop[2],cour]=T[prop[1],cour] penatp=penalty(meet(Tp)) print(c(penat,penatp)) if (penatp==0){ T=Tp break() } if (log(runif(1))<(penat-penatp)/gamma){ T=Tp penat=penatp} if (t%%10==0) gamma=gamma*.999 }

which happened to provide a solution on the second round (got stuck at a penalty of 4 in the first round):

> T T [1,] 1 4 3 2 2 3 [2,] 1 2 4 3 4 4 [3,] 3 2 1 4 1 3 [4,] 1 2 3 1 1 1 [5,] 4 2 4 2 3 3 [6,] 2 4 1 2 4 1 [7,] 4 3 1 1 2 4 [8,] 1 3 2 4 3 1 [9,] 3 3 3 3 4 3 [10,] 4 4 2 3 1 1 [11,] 1 1 1 3 3 2 [12,] 3 4 4 1 3 2 [13,] 4 1 3 4 4 2 [14,] 2 4 3 4 3 4 [15,] 2 3 4 2 1 2 [16,] 2 2 2 3 2 2 [17,] 2 1 2 1 4 3 [18,] 4 3 1 1 2 4 [19,] 3 1 4 4 2 1 [20,] 3 1 2 2 1 4

(This makes a great example for my general public talk in Australia this summer/winter!)

April 14, 2012 at 7:35 pm

Actually, the original attendance at my family meeting was made of 34 persons, sitting on three tables with 8 chairs and one table with ten chairs. Modifying the R code is easy, but I could not find a solution with 7 courses in that case…