<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/unsolved-riddles/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2017/07/04/unsolved-riddles/"> 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>O</strong>n the <a rel="nofollow" href="https://fivethirtyeight.com/features/how-long-will-chaos-reign-in-this-game-of-tag/" target="_blank">Riddler of last week</a>, first a <a rel="nofollow" href="https://xianblog.wordpress.com/2012/02/01/the-birthday-problem/" target="_blank">birthday puzzle</a>:</p>
<blockquote><p><em>Given a group of 23 persons, what is the probability of observing three pairs of identical birthdays?</em></p>
</blockquote>
<p>which can be found by a quick simulation as</p>
<pre>ave=0
for (t in 1:1e6){
 dupz=dates[duplicated(sample(1:365,23,rep=TRUE))]
 ave=ave+as.integer((length(dupz)==3)&amp;
     (length(unique(dupz))==3))}}
ave/M
</pre>
<p>returning a value of 0.0183, but which combinatoric resolution I could not fully fathom without a little help from a friend (<a rel="nofollow" href="https://numbersandshapes.net/2011/04/the-birthday-problem-and-a-generalization/" target="_blank">-ly blog</a>). I had the multinomial coefficient</p>
<p><img alt="{23choose 2 2 2}" title="{23choose 2 2 2}" src="https://s0.wp.com/latex.php?latex=%7B23%5Cchoose+2%5C+2%5C+2%7D&bg=000000&%23038;fg=B0B0B0&%23038;s=0" class="latex"></p>
<p>for the allocation of the 23 persons to one of the three pairs or none, as well as the probability</p>
<p><img alt="dfrac{365timescdotstimes(365-(23-4)+1)}{365^{23}}" title="dfrac{365timescdotstimes(365-(23-4)+1)}{365^{23}}" src="https://s0.wp.com/latex.php?latex=%5Cdfrac%7B365%5Ctimes%5Ccdots%5Ctimes%28365-%2823-4%29%2B1%29%7D%7B365%5E%7B23%7D%7D&bg=000000&%23038;fg=B0B0B0&%23038;s=0" class="latex"></p>
<p>but I had forgotten the 3! in the denominator for the permutations of the three pairs, which leads again to</p>
<p><img alt="{23 choose 2 2 2}dfrac{365timescdotstimes(365-(23-4)+1)}{3!times365^{23}} = 0.0183" title="{23 choose 2 2 2}dfrac{365timescdotstimes(365-(23-4)+1)}{3!times365^{23}} = 0.0183" src="https://s0.wp.com/latex.php?latex=%7B23+%5Cchoose+2%5C+2%5C+2%7D%5Cdfrac%7B365%5Ctimes%5Ccdots%5Ctimes%28365-%2823-4%29%2B1%29%7D%7B3%21%5Ctimes365%5E%7B23%7D%7D+%3D+0.0183&bg=000000&%23038;fg=B0B0B0&%23038;s=0" class="latex"></p>
<p>A question that also led to an unsolved question: in the even this probability was much smaller, what is an easy way into constructing a more efficient importance sampler?</p>
<p>The <a rel="nofollow" href="https://fivethirtyeight.com/features/how-long-will-chaos-reign-in-this-game-of-tag/" target="_blank">second riddle</a> was just as easy to code in R:</p>
<blockquote>
<p><em>A game of tag goes by the following rules: (i) anyone untagged can tag anyone untagged; (ii) anyone tagged by a player tagged gets untagged; (iii) the winner is the last untagged player. What is the expected number of runs for N players?</em></p>
</blockquote>
<p>The outcome of</p>
<pre>game=function(N=12){
  a=rep(0,N);T=0
  while (sum(a==0)>1){
   ij=sample((1:N)[a==0],2)
   a[ij[2]]=ij[1];a[a==ij[2]]=0
   T=T+1}
  return(T)}
</pre>
<p>leads to an average value of</p>
<p><img alt="2^{N-1}-1" title="2^{N-1}-1" src="https://s0.wp.com/latex.php?latex=2%5E%7BN-1%7D-1&bg=000000&%23038;fg=B0B0B0&%23038;s=0" class="latex"></p>
<p>but I had no clear quick explanation for the doubling phenomenon. Until I picked a pen and a sheet of paper and drew the last steps of the game: to decrease down to 1, the size of the untagged survivors has to get through …,3,2 and <em>each time</em> the eliminated player needs to have tagged no other player since otherwise the population grows again. This has to apply all the way to the second round, where N-1 players remain and the one tagged needs to be anyone but the one who tagged the first one. And so on…</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/birthday-problem/" target="_blank">birthday problem</a>, <a rel="nofollow" href="https://xianblog.wordpress.com/tag/extended-birthday-problem/" target="_blank">extended birthday problem</a>, <a rel="nofollow" href="https://xianblog.wordpress.com/tag/the-riddler/" target="_blank">The Riddler</a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/33800/" target="_blank"><img border="0" alt="" src="http://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/33800/"></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/07/04/unsolved-riddles/"> 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/cV9wcWPE2Zg" height="1"></a></div>