[un]solved riddles

[This article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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 about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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)