Archive for combinatorics

Le Monde puzzle [#853]

Posted in Books, Kids, Statistics with tags , , , on February 13, 2014 by xi'an

Yet another one of those Le Monde mathematical puzzles which wording is confusing (or at least annoying) to me:

A political party has 11 commissions, to which belong some of the 13 members of the central committee. A token is given to each member for each commission whom he or she belongs. Two different members cannot share more than one common commission. How many tokens at most? Same question if the president belongs to five commissions.

I just dislike the “story” around the combinatoric problem. Given 13 sets and 11 letters, how many letters can one allocate to each set so that each pair of sets share at most one letter? While waiting for my prosthesis this afternoon, I thought of a purely random search, using the following R code:

n=11
m=13
best=0
for (t in 1:10^3){
  token=matrix(-1,ncol=n,nrow=m);diag(token)=1
  #fill at random: -1 unchecked, 1 allocated, 0 prohibited
  while (sum(token<0)>0){
    res=TRUE
    while (res){
      if (sum(token<0)==1){
          dex=(1:(n*m))[token[(1:(n*m))]<0]}else{
          dex=sample((1:(n*m))[token[(1:(n*m))]<0],1)}
      i=dex%%m+m*(dex%%m==0)
      j=trunc(dex/(1.01*m))+1
      res=FALSE
      for (k in (1:m)[token[,j]==1])
         res=res||(max(token[i,-j]+token[k,-j])==2)
      token[dex]=0
      if (sum(token<0)==0) res=FALSE
      }
    token[dex]=1*(sum(token<0)>0)
    for (k in (1:m)[-i])
      if (max(token[i,-j]+token[k,-j])==2) token[k,j]=0
    image(1:13,1:11,token)
    }
  if (sum(token[token==1])>best) bestoken=token
  best=max(best,sum(token))
}

which led to the value of 43 after that many iterations. Longer runs on faster machines at Paris-Dauphine did not change the output but, as usual with brute force simulation, the true solution may be such an extreme that it is extremely unlikely to happen… I then tried a standard simulated annealing exploration, but could not find an higher value. Except once, leading to the value 44. Here is the corresponding allocation of letters (committees) to sets (individuals) for that solution.lemonde853In this Feb. 5, 2014, issue of Le Monde Science&Médecine leaflet, a review of (my Warwick colleague) Ian Stewart’s 17 equations that changed the World, which must have been recently translated in French (with no criticism of the less compelling chapter on Black-Scholes, and a confusion of the “bell curve” with statistics). Yet another tribune of Marco Zito about the generalisation of Richard Feynman’s diagrams to a solid called the Amplituhedron. (Not making much sense as exposed!)

Le Monde puzzle [#822]

Posted in Books, Kids, R with tags , , , , , , on June 10, 2013 by xi'an

For once Le Monde math puzzle is much more easily solved on a piece of paper than in R, even in a plane from Roma:

Given a partition of the set {1,…,N} in k groups, one considers the collection of all subsets of  the set {1,…,N} containing at least one element from each group. Show that the size of the collection cannot be 50.

Obviously, one could consider a range of possible N’s and k’s and run a program evaluating the sizes of the corresponding collections. However, if the k groups are of size n1,…,nk, the number of subsets satisfying the condition is

(2^{n_1}-1)\times \ldots \times (2^{n_k}-1)

and it is easily shown by induction that this number is necessarily odd, hence the impossible 50.

Le Monde puzzle [#783]

Posted in R, Travel, University life with tags , , , on July 21, 2012 by xi'an

In a political party, there are as many cells as there are members and each member belongs to at least one cell. Each cell has five members and an arbitrary pair of cells only shares one member. How many members are there in this political party?

Back to the mathematical puzzles of Le Monde (science leaflet of the weekend edition)! In addition to a tribune by Cédric Villani celebrating the 100th anniversary of the death of Henri Poincaré, this issue [now of last week] offers this interesting challenge. So much interesting that I could only solve it for three (instead of five) members and could not see the mathematical notion behind the puzzle…

Let us denote by n the number of both the cells and the number of members. Then, when picking an arbitrary order on the sets, if ij denotes the number of members in set j already seen in sets with lower indices, we have the following equality on the total number of members

n = 5n -i_2-\cdots-i_n

and the constraints are that i2<2, i3<3, i4<4, i5<5, and ij<6, for j>5. Hence, i2+i3+i4+i5+…+in≤5n-15, which implies n≥15.

Now, in terms of analytics, I could not go much further and thus turned to an R code to see if I could find a solution by brute force. Here is my code (where the argument a is the number of elements in each set): Continue reading

[not] Le Monde puzzle (solution)

Posted in R, Statistics, University life with tags , , , , , on April 14, 2012 by xi'an

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)

Posted in University life with tags , , , , , , , on April 12, 2012 by xi'an

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.

Follow

Get every new post delivered to your Inbox.

Join 619 other followers