Le Monde puzzle [#1029]

lemondapariA 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]

2 Responses to “Le Monde puzzle [#1029]”

  1. At first glance, it would seem (allowing vote changes!) that the maximum audience has to be the maximum waiting group in round 9 + 600 . If so, then the maximum waiting group is either that round 9 group, or, if that number exceeds 1800, the waiting group after (25% +1) is the winning vote in the tenth round. Did I get that right?

    • Voting does not change, in that people who wait for the next round cannot switch film or opinion. But you are right that the maximal size audience is 600 plus the maximal waiting group at round 9!

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.