Le Monde puzzle [#1029]

November 21, 2017
By

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

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 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.

Search R-bloggers

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)