[not] Le Monde puzzle (solution)

Following 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!)

[not] Le Monde puzzle (6)

After posting the question on dinner table permutations on StackExchange (mathematics), I got almost instantaneously a reply that the right number was six, linking to the Covering chapter by Gordan and Stinson, taken from the second edition of Handbook of Combinatorial Designs. If I understand correctly this terse coverage that reminds me of Gradshteyn and Ryzhik’s monumental Table of Integrals, Series and Products, my question is connected to the covering number C(20,5,2), which is equal to 21 according to Table 1.33 of the above chapter. This is the minimum number of blocks such that every pair of points occurs in at least one block (element) of the collection of subsets of size 5 (the tables across courses). Now, in my problem, the interesting coverage is a resolvable coverage, i.e., a collection of tables that “can be partitioned into parallel classes, each of which consists of v/k[=4] disjoint blocks” (Definition 1.43). Then the number of parallel classes is r(4,5)=6, as provided by hardmath. Now the remaining question is how to build the resolvable 2-(20,5,1) covering, i.e. the table plans across the six courses… This may be related to a direct proof as to why a five course dinner does not work.

[super]power to X-edit

Having reached 2000 reputation credits on Cross Validated, I now have the privilege to edit others’ posts:

We believe in the power of community editing. That means once you’ve generated enough reputation, we trust you to edit anything in the system without it going through the peer review system. Not just your posts—anyone’s posts!

Which I already did in the past with superusers’ supervision. Hopefully, this promotion will not induce spending even more time on the forum… And increase my stress at reading often too often questions written by people obviously too lazy to open a stat manual. (I know, I know, no one forces me to read them!)

[stack] overloaded, crossed and invalidated

For the few past days, I have been monitoring Cross Validated, a forum on statistics that is part of StackExchange (“a fast-growing network of 71 question and answer sites on diverse topics from software programming to cooking to photography and gaming“…) for questions of interest, but I think (hope?) I will stop there my involvement. First, I fear this type of forum is too addictive (at least for me, and I already have my share of web-related addictions, witness this very blog!). Of course, Cross Validated is an interesting site for questions related with statistics and machine learning, with a great L_AT_EX interface that allows to type math formulas in a natural way; however I also find the exercise rather frustrating and to some extend futile, which is another reason why I do not wish pursuing the experience any further. For one thing, some of the questions found there are of the “please do my homework for me” type and I am plagued with enough emails of this sort (connected with my own exercises) to look for further hassle. They are however easy to spot and thus eliminate. For another, I suspect a majority of questions, while honest and deep enough, are often asked at the spur of the moment, i.e. without a preliminary search on a paper or online source, like Wikipedia or a textbook. E.g., a question about Bayes theorem that brought decent answers but not further than the Wikipedia entry on the topic. At one level, I would like to give in to temptation and to answer questions I feel I have a valid and informative answer. However, it does not seem like an efficient use of my time (read my books instead!) And also I am not completely convinced this fundamentally helps the persons who ask the questions in the first place. What may lie at the bottom of my unease with being involved in such forums is the sad fact that most questioners want answers without getting through the necessary steps of learning the bases and the background theory surrounding the question. While not being a teacher at heart, this approach gets against my views on learning (“Give a man a fish, &tc.”). Observations towards this view are that (a) many questioners are “one-shot” occurrences, i.e. are never seen again on the forum and (b) such questioners often fail to acknowledge answers that are not posted immediately, i.e. are not really interested in the debate surrounding the question they asked in the first place, only in someone solving their problem for them…

Anyway, this post is my very personal opinion on why I should not get involved with Q&A sites: it does not aim at criticising people asking or answering questions on Cross Validated, quite clearly, as some questions may lead to interesting research developments and as some answers are well-though, helpful, and informative. Just not my ballpark!