<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/le-monde-puzzle-1029/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2017/11/22/le-monde-puzzle-1029/"> R – Xi'an's Og</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><strong><img src="https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcRsQd3v7efgSlmsNPKddzl-oQS9fZOF8a68V6KPmf5dnmI_EJ66rw" alt="" width="273" height="185">A</strong> convoluted counting <a rel="nofollow" href="https://xianblog.wordpress.com/2011/09/03/le-monde-puzzle-website/" title="Le Monde puzzle [website]" target="_blank">Le Monde mathematical puzzle</a>:</p>
<blockquote>
<p><em>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?<br>
</em></p>
</blockquote>
<p><strong>A</strong> first attempt by random sampling does not produce extreme enough events to reach those maxima:</p>
<pre>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)}</pre>
<p>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:</p>
<pre>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)}
</pre>
<p>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…)</p>
<p>While in <a rel="nofollow" href="https://xianblog.wordpress.com/2016/11/10/snapshot-from-warwick-jatp/" target="_blank">Warwick</a>, 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</p>
<pre>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))}}    
</pre>
<p>led to a maximal audience size of 1619. [Which is also the answer provided by <a rel="nofollow" href="https://xianblog.wordpress.com/2011/09/03/le-monde-puzzle-website/" title="Le Monde puzzle [website]" target="_blank">Le Monde</a>]</p>
<p>Filed under: <a rel="nofollow" href="https://xianblog.wordpress.com/category/books/" target="_blank">Books</a>, <a rel="nofollow" href="https://xianblog.wordpress.com/category/kids/" target="_blank">Kids</a>, <a rel="nofollow" href="https://xianblog.wordpress.com/category/statistics/r-statistics/" target="_blank">R</a> Tagged: <a rel="nofollow" href="https://xianblog.wordpress.com/tag/combinatorics/" target="_blank">combinatorics</a>, <a rel="nofollow" href="https://xianblog.wordpress.com/tag/le-monde/" target="_blank">Le Monde</a>, <a rel="nofollow" href="https://xianblog.wordpress.com/tag/r/" target="_blank">R</a> <a rel="nofollow" href="https://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/34756/" target="_blank"><img border="0" alt="" src="https://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/34756/"></a> <img border="0" alt="" src="https://i1.wp.com/pixel.wp.com/b.gif?resize=1%2C1&ssl=1" data-recalc-dims="1"></p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://xianblog.wordpress.com/2017/11/22/le-monde-puzzle-1029/"> R – Xi'an's Og</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/5631AjcVxiY" height="1"></a></div>