
Archive for resolvable covering
America in line [& the world in the balance]
Posted in Books, pictures with tags Agent Orange, democracy, Donald Trump, resolvable covering, The New Yorker, US elections 2020, US politics, vote, voters suppression on November 3, 2020 by xi'an
[not] Le Monde puzzle (solution)
Posted in R, Statistics, University life with tags combinatorics, covering, R, resolvable covering, simulated annealing, StackExchange on April 14, 2012 by xi'anFollowing 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)
Posted in University life with tags combinatorics, covering, Handbook of Combinatorial Designs, permutations, resolvable covering, Series and Products, StackExchange, Table of Integrals Series and Products on April 12, 2012 by xi'anAfter 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.