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.

[not] Le Monde puzzle

Posted in Kids, Statistics with tags , , on April 12, 2012 by xi'an

In the spirit of the mathematical puzzles of Le Monde, here is a puzzle that came to me during a family reunion last weekend.

During a dinner of 20 couples sitting at four tables with ten seats, everyone wants to share a table with everyone. The assembly decides to switch seats after each serving towards this goal. What is the minimal number of servings needed to ensure that every couple shared a table with every other couple at some point? And what is the optimal switching strategy?

Of course, extension of the solution to k couples, n tables and p seats (with k<np) would be great!

Magical Mathematics [and the converse]

Posted in Books, Kids, Mountains, Travel, University life with tags , , , , , , , , , on December 29, 2011 by xi'an

The two of us have been mixing entertainment with mathematics for most of our lives.” (page xi)

When I learned that Persi Diaconis and Ron Graham had co-authored a book on the mathematics of magic, the Book Editor of CHANCE immediately asked Princeton University Press for a copy! Even though I am not at all interested in card tricks. Nor in juggling. (The title is a wee confusing to [a non-native speaker like] me as it sounds as focussing on the magics of mathematics rather than the converse.)

Once the book had arrived, I showed the book to my wife and she started reading it right away, going over the first chapter prior to giving it back. Later, on a plane trip between Phoenix and Minneapolis, I happened to sit next to a professional magician, The Amazing Hondo!, who started chatting with me and telling me about his work and some of his tricks. He knew about Persi as a magician but was surprised he was equally famous among mathematicians. Hondo showed me a few (impressive) sleights of hand and explained a nice mathematical trick (based on creating apparent randomness while always extracting the same number of cards from the pile). As I happened to have the book with me, he took a look at it, commenting on one trick, and wrote down the reference. I have had a few other occurrences of how the book attracted the attention of non-magicians and/or non-mathematicians: this illustrates the appeal of the concept of this book for a very wide audience and, of course, once one starts reading the book, the attaction is increased manyfold. It is indeed a very entertaining book, with a fairly easy mathematical level, and it is also a beautiful product, with wide margins, fancy (but readable) fonts, photographs, and graphs or tables in the margins.

Both of our worlds have a dense social structure: thousands of players turning ideas over and over.” (page xi)

The entertaining and cosy style of Mathematical Magics (oops, Magical Mathematics!) does not mean it is an easy read. First, conceptualising the card manipulations requires a good analytic mind if one does not have a deck of cards available. Second, the connections with mathematics involve several subfields and not only combinatorics. Like de Bruijn sequences and graphs, the Mandelbrot set, Penrose tiling. And even Bayesian analysis for reversible Markov chains (p.42) and the I Ching… The last chapters are however less directly related to maths (even though Chapter 10 about great mathematical magicians includes connections with topology).

Interestingly (for us academics), the book mentions a (Banff) BIRS 2004 workshop relating to magics via de Bruijn sequences and Gray codes. With the traditional picture in front of the (old) BIRS building. (Another item of information, IBM stands for International Brotherhood of Magicians!)

We hope that our book will shine a friendly light on the corners of the world that are our homes.” (page xii)

One of the complaints I share with my wife about Magical Mathematics is that some of the tricks are not explained in full enough detail. At least for some non-native speakers like us. For instance, during my skiing break in the Alps, Paul my nephew and I tried the Gilbreath principle and could not make it work without forcing the perfect riffle-shuffle one card at a time. The sentence “the shuffle doesn’t have to be carefully done” (p.63) set us on the wrong track. On pages 106 and 107, two 1500’s books in French are quoted with one typo (sont versus font, but at the time s and f were typed quite similarly), a missing s in Inventions, and without the accents:  I wonder whether or not accents existed at the time. (It seems they did not, as seen on the originals here and there.) The comment on Heeffer’s 1624 (French) book is confusing [to me] in that Heeffer is a current math historian working on a 1624 book by Jean Leurechon. (The accents are not there in the 1624 edition.)

Overall, this is a wonderful book, potentialy enjoyable by a large range of individuals. (Precision: I read half of it flying over the beauty of sunsetted Greenland and the other half in a chalet next to the ski slopes. So I was in a mellow spirit!) The order behind the apparent randomness of card tricks becomes clearer and clearer to the naïve reader like me.And the warmth and communal spirit of the magician community transpires through the last chapters. (Note there is a $1000 reward posted within the book!)

Follow

Get every new post delivered to your Inbox.

Join 634 other followers