[un]solved riddles

July 3, 2017
By

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

On the Riddler of last week, first a birthday puzzle:

Given a group of 23 persons, what is the probability of observing three pairs of identical birthdays?

which can be found by a quick simulation as

ave=0
for (t in 1:1e6){
 dupz=dates[duplicated(sample(1:365,23,rep=TRUE))]
 ave=ave+as.integer((length(dupz)==3)&
     (length(unique(dupz))==3))}}
ave/M

returning a value of 0.0183, but which combinatoric resolution I could not fully fathom without a little help from a friend (-ly blog). I had the multinomial coefficient

{23\choose 2\ 2\ 2}

for the allocation of the 23 persons to one of the three pairs or none, as well as the probability

\dfrac{365\times\cdots\times(365-(23-4)+1)}{365^{23}}

but I had forgotten the 3! in the denominator for the permutations of the three pairs, which leads again to

{23 \choose 2\ 2\ 2}\dfrac{365\times\cdots\times(365-(23-4)+1)}{3!\times365^{23}} = 0.0183

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?

The second riddle was just as easy to code in R:

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?

The outcome of

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)}

leads to an average value of

2^{N-1}-1

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 each time 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…

Filed under: Books, Kids, R Tagged: birthday problem, extended birthday problem, The Riddler

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.

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)