Le Monde puzzle [#937]

November 10, 2015
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

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

Filed under: Books, R Tagged: arithmetics, intersect, Le Monde, mathematical puzzle, R

To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)