Le Monde puzzle [#937]

A combinatoric Le Monde mathematical puzzle that resembles many earlier ones:

Given a pool of 30 interns allocated to three person night-shifts, is it possible to see 31 consecutive nights such that (a) all the shifts differ and (b) there are no pair of shifts with a single common intern?

In fact, the constraint there is very strong: two pairs of shift can only share zero or two interns. For one given shift, there are 26 other shifts with which it can share two interns, but then any two of those 26 others must share zero or two, which makes the two common to all and exclude any additional shift. But this is not the only approach to allocate the interns over the shifts since, as pointed out by Jean-Louis and checking with the following R code, 28 and not 27 is the maximum possible number of shifts under those conditions.

poss=combn(30,3)
shft=matrix(NA,31,3)
shft[1,]=sample(1:30,3)

poss=poss[,sample(4060)]
prop=poss[,1];k=2
acpt=intersect(prop,shft[1,])
while (((length(acpt)==1)+(length(acpt==3)))>0){
    prop=poss[,k];k=k+1
    acpt=intersect(prop,shft[1,])}
shft[2,]=prop
for(i in 3:31){
  poss=poss[,sample(4060)]
   prop=poss[,1];k=2
  acpt=(length(intersect(prop,shft[1,]))==1)+(length(intersect(prop,shft[1,]))==3)
  for (j in 2:(i-1))
    acpt=acpt+(length(intersect(prop,shft[j,]))==1)+(length(intersect(prop,shft[j,]))==3)
  while ((acpt>0)&(k<4061)){
    prop=poss[,k];k=k+1
    acpt=(length(intersect(prop,shft[1,]))==1)+(length(intersect(prop,shft[1,]))==3)
    for (j in 2:(i-1))
    acpt=acpt+(length(intersect(prop,shft[j,]))==1)+(length(intersect(prop,shft[j,]))==3)}
  if (k==4061) break()
  shft[i,]=prop}

For instance, here is a 28 day solution:

> shft
[,1] [,2] [,3]
[1,]   14   30   29
[2,]    5   17   19
[3,]    2   18   24
[4,]   15   16   20
[5,]    4   22   28
[6,]    3   21   25
[7,]   13   21   25
[8,]    4    7   28
[9,]    1   17   19
[10,]    2   18   27
[11,]   10   15   20
[12,]    2   24   27
[13,]    8    9   23
[14,]    4   12   28
[15,]    1    5   17
[16,]    4   11   28
[17,]    6   14   29
[18,]    6   14   30
[19,]    3   13   25
[20,]    9   23   26
[21,]    1    5   19
[22,]   10   15   16
[23,]    8    9   26
[24,]    8   23   26
[25,]    3   13   21
[26,]   10   16   20
[27,]   18   24   27
[28,]    6   29   30

4 Responses to “Le Monde puzzle [#937]”

  1. Merci, Jean-Louis! I eventually “got” your solution: out of the four groups of three, there are always two in common. Since Le Monde was not printed yesterday, I did not check the proposed resolution.

  2. J-L FOULLEY Says:

    Sorry, the scheme was not reproduced the way I wrote it. The groups were made of the elements of the square table without the diagonal i.e.

    1) 2,3,4
    2) 1,3,4
    3) 1,2,4
    4) 1,2,3

  3. J-L FOULLEY Says:

    Thanks Christian for reporting on this logical game.
    At first glance, I would have said 28 on account of the following scheme:
    There are 4 possible such groups of 3 persons (2 persons in common) among 4 different persons. Starting with 30 persons, you can repeat this scheme 7 times with completely different blocks of four.

    1 2 3 4
    – X X X
    X – X X
    X X – X
    X X X –

    But may be I missed sth?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s