Archive for combinatorics

« Older Entries

xkcd’atorics

Posted in Books, Kids, pictures, R, Statistics, University life with tags , , , , , , on December 13, 2024 by xi'an

1 Comment »

alone in Napoli

Posted in Books, Kids, R, Statistics with tags , , , , , , , , on March 13, 2023 by xi'an


A combinatorics puzzle from The Riddler about a Napoli solitaire where 4 x 10 cards numbered from 1 to 10 are shuffled and the game is lost when a number (1,2, or 3) is equal to its position modulo 3 (1,2 or 3). A simple R code shows that the probability of winning is around 0.00831:

N=40
for(t in 1:1e6)F=F+!sum(!(sample((1:N)%%10)-(1:N)%%3))

ChatGPT bends over backward to achieve this figure! Now, the exact probability can be found by combinatorics. While there are 40! ways of permuting the 40 cards, those missing the coincidences are

\sum\limits_{k=0}^4\sum\limits_{j=0}^4\sum\limits_{i=0}^4{13\choose i}{13\choose 4-i}{14\choose j}{13-i\choose 4-j}{14-j\choose k}{9+i\choose 4-k}

multiplied by 4!4!4!28! (which I initially forgot), resulting in 0.00831:

for(i in 0:4)for(j in 0:4)for(k in 0:4)
      F=F+exp(lchoose(13,i)+lchoose(13,4-i)+3*lfactorial(4)+
          lchoose(14,j)+lchoose(13-i,4-j)+lfactorial(28)+
          lchoose(14-j,k)+lchoose(9+i,4-k)-lfactorial(40))

1 Comment »

another drawer of socks

Posted in Books, Kids, R, Statistics with tags , , , , , , on November 6, 2022 by xi'an

A socks riddle from the Riddler but with no clear ABC connection! Twenty-eight socks from fourteen pairs of socks are taken from a drawer, one by one, and laid on a surface that only fit nine socks at a time, with complete pairs removed. What is the probability that all pairs are stored without running out of space? No orphan socks then!!

Writing an R code for this experiment is straightforward

for(v in 1:1e6){
 S=sample(rep(1:14,2))
 x=S[1]
 for(t in 2:18){
  if(S[t]%in%x){x=x[S[t]!=x]}else{x=c(x,S[t])}
  if(sum(!!x)>9){
    F=F+1;break()}}}

and it returns a value quite close to 0.7 for the probability of success. I was expecting a less brute-force resolution but the the Riddler only provided the answer of 70.049 based on the above tree of probabilities (which I was too lazy to code).

1 Comment »

shelled and riddled

Posted in Books, Kids, pictures, R, Statistics with tags , , , , , , , on August 10, 2022 by xi'an

Consider a shell game with three shells and a ball with The Riddler constraint that the location of the shell with the ball is always exchanged with the location of an empty shell, randomly chosen. If one starts with the ball as rightmost, what is the distribution of the location of the ball after N steps?

Running an exploratory R code like

o=rep(0,3)
for(n in 1:1e6){
  b=c(0,0,1)
  for(t in 1:N){
    i=sample((1:3)[!b],1);b=0*b;b[i]=1}
  o=o+b}

shows that the difference in probability is between the rightmost position and both others, starting at zero, and evolving as p⁺=(1-p⁻)/2, with the successive values 0,1/2,1/4,3/8,5/15,11/32,… Very quickly converging to 1/3.

1 Comment »

self-avoiding random angles

Posted in Books, Kids, pictures, Statistics, Travel with tags , , , , , on June 17, 2022 by xi'an

An apparently easy riddle from The Riddler this week: given N random half-lines starting from a N-S segment, what is the probability that none ever intersect? If m ½-lines are on the same side of the segment, they will not intersect when their angle with the segment is decreasing with the longitude of the endpoint of this ½-line on the segment. Assuming that drawing a ½-line at random is akin to uniformely drawing an angle on (0,π), this no X’ing event happens when the m angles are properly ordered, a 1/m! event. Independently, the probability for the segments on the other side is 1/(N-m)! The joint probability is thus

\displaystyle\sum_{m=0}^N {N\choose m}\frac{1}{2^N} \frac{1}{m!(N-m)!}=\frac{(2N)!}{2^N(N!)^3}

Leave a comment »

« Older Entries