Le Monde puzzle [#1029]

[This article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

A convoluted counting Le Monde mathematical puzzle:

A film theatre has a waiting room and several projection rooms. With four films on display. A first set of 600 spectators enters the waiting room and vote for their favourite film. The most popular film is projected to the spectators who voted for it and the remaining spectators stay in the waiting room. They are joined by a new set of 600 spectators, who then also vote for their favourite film. The selected film (which may be the same as the first one) is then shown to those who vote for it and the remaining spectators stay in the waiting room. This pattern is repeated for a total number of 10 votes, after which the remaining spectators leave. What are the maximal possible numbers of waiting spectators and of spectators in a projection room?

A first attempt by random sampling does not produce extreme enough events to reach those maxima:

wm=rm=600 #waiting and watching
for (v in 1:V){
 film=rep(0,4) #votes on each fiLm
 for (t in 1:9){
  film=film+rmultinom(1,600,rep(1,4))
  rm=max(rm,max(film))
  film[order(film)[4]]=0
  wm=max(wm,sum(film)+600)}
 rm=max(rm,max(film)+600)}

where the last line adds the last batch of arriving spectators to the largest group of waiting ones. This code only returns 1605 for the maximal number of waiting spectators. And 1155 for the maximal number in a projection room.  Compared with the even separation of the first 600 into four groups of 150… I thus looked for an alternative deterministic allocation:

wm=rm=0
film=rep(0,4)
for (t in 1:9){
 size=sum(film)+600
 film=c(rep(ceiling(size/4),3),size-3*ceiling(size/4))
 film[order(film)[4]]=0
 rm=max(rm,max(film)+600)
 wm=max(wm,sum(film)+600)}

which tries to preserve as many waiting spectators as possible for the last round (and always considers the scenario of all newcomers backing the largest waiting group for the next film). The outcome of this sequence moves up to 1155 for the largest projection audience and 2264 for the largest waiting group. I however wonder if splitting into two groups in the final round(s) could even increase the size of the last projection. And indeed halving the last batch into two groups leads to 1709 spectators in the final projection. With uncertainties about the validity of the split towards ancient spectators keeping their vote fixed! (I did not think long enough about this puzzle to turn it into a more mathematical problem…)

While in Warwick, I reconsidered the problem from a dynamic programming perspective, always keeping the notion that it was optimal to allocate the votes evenly between some of the films (from 1 to 4). Using the recursive R code

optiz=function(votz,t){
  if (t==9){ return(sort(votz)[3]+600)
  }else{
    goal=optiz(sort(votz)+c(0,0,600,-max(votz)),t+1)
    goal=rep(goal,4)
    for (i in 2:4){
      film=sort(votz);film[4]=0;film=sort(film)
      size=sum(film[(4-i+1):4])+600
      film[(4-i+1):4]=ceiling(size/i)
      while (sum(film[(4-i+1):4])>size) film[4]=film[4]-1
      goal[i]=optiz(sort(film),t+1)}
    return(max(goal))}}    

led to a maximal audience size of 1619. [Which is also the answer provided by Le Monde]


Filed under: Books, Kids, R Tagged: combinatorics, Le Monde, R

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

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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)