Archive for The Riddler

Riddle of the lanes

Posted in Books, Kids, R with tags , , , , , on July 13, 2020 by xi'an

An express riddle from the Riddler about reopening pools, where lanes are allowed provided there is no swimmer in the lane or in any of the adjacent lanes. If swimmers pick their lane at random (while they can), what is the average number of occupied lanes?

If there are n lanes and E(n) is the expected number of swimmers, E(n) satisfies a recurrence relation determined by the location of the first swimmer:

E(n)=1+\frac{1}{n}[2E(n-2)+\sum_{i=2}^{n-1}\{E(i-2)+E(n-i-1)\}]

with E(0)=0, E(1)=E(2)=1. The above can be checked with a quick R experiment:

en=0
for(t in 1:T){
   la=rep(u<-0,N)
   while(sum(la)<N){
     i=sample(rep((1:N)[!la],2),1)
     la[max(1,i-1):min(N,i+1)]=1
     u=u+1}
   en=en+u}

overlap, overstreched

Posted in Books, Kids, R, Statistics with tags , , , , , , on June 15, 2020 by xi'an

An interesting challenge on The Riddler on the probability to see a random interval X’ing with all other random intervals when generating n intervals from Dirichlet D(1,1,1). As it happens the probability is always 2/3, whatever n>1, as shown by the R code below (where replicate cannot be replaced by rep!):

qro=function(n,T=1e3){
  quo=function(n){
     xyz=t(apply(matrix(runif(2*n),n),1,sort))
  sum(xyz[,1]<min(xyz[,2])&xyz[,2]>max(xyz[,1]))<0}
  mean(replicate(quo(n),T))}

and discussed more in details on X validated. As only a property on permutations and partitions. (The above picture is taken from this 2015 X validated post.)

minimax, maximin or plain

Posted in Kids, R with tags , , , on June 1, 2020 by xi'an

A simple riddle from The Riddler on choosing between the maximum between two minima of two throws of an N-face dice, the minimum between two maxima of two throws of an N-face dice, and a single throw. Since maximin is always less than minimax, second choice is always worse than first and a stochastic domination version of the argument shows the single throw should stand in the middle.

a new Monty Hall riddle

Posted in Books, Kids, Mountains, pictures, R, Statistics, Travel with tags , , , , , , , , , on May 22, 2020 by xi'an

The Riddler was sort of feeling the rising boredom of being under lockdown when proposing the following variant to the Monty Hall puzzle:

There are zero to three goats, with a probability ¼ each, and they are allocated to different doors uniformly among the three doors of the show. After the player chooses a door, Monty opens another door hidding a goat or signals this is impossible. Given that he did open a door, what is the probability that the player’s door does not hide a goat?

Indeed, a straightforward conditional probability computation considering all eight possible cases with the four cases corresponding to Monty opening a door leads to a probability of 3/8 for the player’s door. As confirmed by the following R code:

s=sample
m=c(0,0)
for(t in 1:1e6)m=m+(range(s(1:3,s(1:3,1)))>1)

not a Bernoulli factory

Posted in Books, Kids, pictures, R with tags , , , , , , , on May 20, 2020 by xi'an

A Riddler riddle I possibly misunderstood:

Four isolated persons are given four fair coins, which can be either flipped once or returned without being flipped. If all flipped coins come up heads, the team wins! Else, if any comes up tails, or if no flip at all is done, it looses. Each person is further given an independent U(0,1) realisation. What is the best strategy?

Since the players are separated, I would presume the same procedure is used by all. Meaning that a coin is tossed with probability p, ie if the uniform is less than p, and untouched otherwise. The probability of winning is then

4(1-p)³p½+6(1-p)³p½²+4(1-p)p³½³+p⁴½⁴

which is maximum for p=0.3420391, with a winning probability of 0.2848424.

And an extra puzzle for free:

solve xxxx=2020

Where the integral part is the integer immediately below x. Puzzle that I first fail solving by brute force, because I did not look at negative x’s… Since the fourth root of 2020 is between 6 and 7, the solution is either x=6+ε or x=-7+ε, with ε in (0,1). The puzzle then becomes either

(6+ε)⌊(6+ε)⌊(6+ε)⌊6+ε⌋⌋ = (6+ε)⌊(6+ε)⌊36+6ε⌋⌋ = (6+ε)⌊(6+ε)(36+⌊6ε⌋)⌋ = 2020

where there are 6 possible integer values for ⌊6ε⌋, with only ⌊6ε⌋=5 being possible, turning the equation into

(6+ε)⌊41(6+ε) = (6+ε)(246+⌊41ε) = 2020

where again only ⌊42ε=40 being possible, ending up with

1716+286ε = 2020

which has no solution in (0,1). In the second case

(-7+ε)(-7+ε)(-7+ε)-7+ε⌋⌋ = (-7+ε)(-7+ε)(49+-7ε⌋)= 2020

shows that only -7ε=-3 is possible, leading to

(-7+ε)⌊46(-7+ε)) = (-7+ε) (-322+46ε⌋)=2020

with only 46ε=17 possible, hence

2135-305ε=2020

and

ε=115/305.

A brute force simulated annealing resolution returns x=-6.622706 after 10⁸ iterations. A more interesting question is to figure out the discontinuity points of the function

ℵ(x) = xxxx

as they seem to be numerous:

For instance, only 854 of the first 2020 integers enjoy a solution to ℵ(x)=n.