Korok Seeds

From The Riddler on FiveThirtyEight:

While spending more time at home in recent weeks, I’ve had the chance to revisit one of my favorite video games from recent years — The Legend of Zelda: Breath of the Wild. Within the game, there are hundreds of hidden “Korok Seeds,” which I’m having an increasingly difficult time finding.

Fortunately, there’s a special mask you can acquire in the game that makes a sound any time you’re within a certain distance of a Korok Seed. While playing, I marked nine distinct locations on the game map, forming the 3-by-3 grid shown below:

Each leaf symbol is within range of a Korok Seed, while the point in the middle is not within range of a Korok Seed. Given this arrangement, what is the minimum possible number of Korok Seeds I could have detected?

Solution

Suppose this grid is such that the origin is in the middle and the leaves are at (-1,1), (0,1), (1,1), (-1,0), (1,0), (-1,-1), (0,-1), and (1, -1). For detector radii greater than zero but less than 0.5, the map suggests we are detecting 8 Korok Seeds.

Here is a picture of the situation in which the radii are 0.5.

As the radii of the detectors grows larger than 0.5 and stays less than 1, the minimum number of Korok seeds that can be detected turns into 4. Here is the picture if the radii are exactly 1 and a possible placement of the 4 Korok Seeds.

When the radii get larger than 1 but stay smaller than a magical number of around 1.6, the minimum number of Korok sees that can be detected reduces to 3!

Here is a picture where the radii are 1.3 along with the 3 possible locations.

Finally, once we get a circle with radius larger than the 1.6, the minimum number of Korok Seeds reduces to 2! Here is a picture with radii all equal to 2 along with 2 possible locations.

Very Large Zoom Call

From the Riddler on FiveThirty Eight:

One Friday morning, suppose everyone in the U.S. (about 330 million people) joins a single Zoom meeting between 8 a.m. and 9 a.m. — to discuss the latest Riddler column, of course. This being a virtual meeting, many people will join late and leave early.

In fact, the attendees all follow the same steps in determining when to join and leave the meeting. Each person independently picks two random times between 8 a.m. and 9 a.m. — not rounded to the nearest minute, mind you, but any time within that range. They then join the meeting at the earlier time and leave the meeting at the later time.

What is the probability that at least one attendee is on the call with everyone else (i.e., the attendee’s time on the call overlaps with every other person’s time on the call)?

Extra credit: What is the probability that at least two attendees are on the call with everyone else?

Solution

Let’s first explore the solution for 2 people. I decided to approach the problem from a combinatorics perspective. At first, I got bogged down with looking at order statistics for the minimum and maximum of a uniform distribution. It was easier once I saw that we only care about the order.

Let’s say we have person a and person b. From start to finish, they could end up in any of the following orders with equal chances.

  • a, a, b, b
  • a, b, a, b
  • a, b, b, a
  • b, b, a, a
  • b, a, b, a
  • b, a, a, b

The last three we can ignore since they are equivalent to the first three. We find that a, a, b, b results in 0 people on the call with everyone else, and that the other two result in 2 people on the call with everyone else.

Thus, the probability of 0 people on the call is 1/3 for the case of just 2 people.

Let’s bring in a third person now. Although there are 90 possible outcomes, if we use the rule that the very first start time is labeled a, the second start time is labeled b, and the third start time is labeled c, with the finishing times labeled the same as the start, then there are only 15 outcomes we need to consider.

  • a,a,b,b,c,c - 0
  • a,a,b,c,b,c - 0
  • a,a,b,c,c,b - 0
  • a,b,a,b,c,c - 0
  • a,b,a,c,b,c - 1
  • a,b,a,c,c,b - 1
  • a,b,b,a,c,c - 0
  • a,b,b,c,a,c - 1
  • a,b,b,c,c,a - 1
  • a,b,c,a,b,c - 3
  • a,b,c,a,c,b - 3
  • a,b,c,b,a,c - 3
  • a,b,c,b,c,a - 3
  • a,b,c,c,a,b - 3
  • a,b,c,b,b,a - 3

It turns out that 5 of these 15 outcomes result in 0 people overlapping with everyone else, which is 1/3 again. The probability that exactly one person overlaps is 4/15.

To explore this further, I resorted to coding. First I built something that would build the above set for any input. However, a,a,b,b,c,c would instead be read (1,2)|(3,4)|(5,6). The first “group” is where a’s start and finish time line up. The second “group” is where b’s start and finish time line up. And so on. So, (1,4)|(2,6)|(3,5) would mean it resulted in this line-up: a,b,c,a,c,b.

## This will be built to use recursion
groupsOfTwo <- function(k){
   if(k==1){return(1:2)}
   else if(k==2){
      return(matrix(c(1,1,1,2,3,4,3,2,2,4,4,3), nrow = 3))
   }
   else{
      outerMatrix <- c()
      ## The recursion step 
      workingMatrix <- groupsOfTwo(k-1)
      for(i in 1:(2*k-1)){
         innerMatrix <- workingMatrix
         innerMatrix[innerMatrix>=i] <-
            innerMatrix[innerMatrix>=i] + 2
         innerMatrix[innerMatrix<i] <- 
            innerMatrix[innerMatrix<i] + 1
         K <- nrow(innerMatrix)
         addOnMatrix <- matrix(c(rep(1,K),rep(i+1,K)),
                               nrow = K)
         outerMatrix <- rbind(outerMatrix,
                              cbind(addOnMatrix,innerMatrix))
      }
   }
   return(outerMatrix)
}

groupsOfTwo(2)
##      [,1] [,2] [,3] [,4]
## [1,]    1    2    3    4
## [2,]    1    3    2    4
## [3,]    1    4    2    3
groupsOfTwo(3)
##       [,1] [,2] [,3] [,4] [,5] [,6]
##  [1,]    1    2    3    4    5    6
##  [2,]    1    2    3    5    4    6
##  [3,]    1    2    3    6    4    5
##  [4,]    1    3    2    4    5    6
##  [5,]    1    3    2    5    4    6
##  [6,]    1    3    2    6    4    5
##  [7,]    1    4    2    3    5    6
##  [8,]    1    4    2    5    3    6
##  [9,]    1    4    2    6    3    5
## [10,]    1    5    2    3    4    6
## [11,]    1    5    2    4    3    6
## [12,]    1    5    2    6    3    4
## [13,]    1    6    2    3    4    5
## [14,]    1    6    2    4    3    5
## [15,]    1    6    2    5    3    4

Now that I have this, I want a function that will take each row of my matrix, and produce the number of “callers” who overlap with everone else.

## The input P will be one of the "groups of two" 
## permutations. 
allCalls <- function(P){
   N <- length(P)/2
   indexSet <- 1:N
   ## The start times are all the odd locations
   Mins <- P[2*indexSet-1]
   ## The end times are all the even locations
   Maxs <- P[2*indexSet]
   ## there are 0 overlaps to begin with. 
   count <- 0
   for(j in indexSet){
      ## For each individual, check to see if their start
      ## time is less than all the other' end time AND
      ## if their end time is greater than all the other's
      ## start time. If this is so, they overlap with everyone
      ## and we increase the count by 1. 
      if(all(Mins[j]<Maxs[-j]) & all(Maxs[j]>Mins[-j])){
         count <- count+1
      }
   }
   return(count)
}

## Test on a permutation that should result in 0:
allCalls(c(1,2,3,4,5,6))
## [1] 0
## Test on one that should return 1:
allCalls(c(1,5,2,3,4,6))
## [1] 1
## Test on one that should return 3:
allCalls(c(1,4,2,5,3,6))
## [1] 3

Now, let’s build a function that will then take a number as an input, and read through the matrix of values and return a table of values for 0, 1, 2, etc.

atLeastN <- function(N){
   ## Build the matrix 
   MatrixofPermutations <- groupsOfTwo(N)
   k <- nrow(MatrixofPermutations)
   ## At Least counts all start at 0
   AtLeastCounts <- rep(0, N+1)
   names(AtLeastCounts) <- as.character(0:N)
   for(i in 1:k){
      ## read each row of the matrix
      j <- allCalls(MatrixofPermutations[i,])
      ## update the count 
      AtLeastCounts[j+1] <- AtLeastCounts[j+1]+factorial(N)
   }
   return(AtLeastCounts)
}

Two <- atLeastN(2)
Two 
## 0 1 2 
## 2 0 4
Two/sum(Two)
##         0         1         2 
## 0.3333333 0.0000000 0.6666667
Three <- atLeastN(3)
Three
##  0  1  2  3 
## 30 24  0 36
Three/sum(Three)
##         0         1         2         3 
## 0.3333333 0.2666667 0.0000000 0.4000000

It works for the two and three! Let’s explore some more.

Four <- atLeastN(4)
Four
##   0   1   2   3   4 
## 840 672 432   0 576
Four/sum(Four)
##         0         1         2         3         4 
## 0.3333333 0.2666667 0.1714286 0.0000000 0.2285714
Five <- atLeastN(5)
Five
##     0     1     2     3     4     5 
## 37800 30240 19440 11520     0 14400
Five/sum(Five)
##         0         1         2         3         4         5 
## 0.3333333 0.2666667 0.1714286 0.1015873 0.0000000 0.1269841
Six <- atLeastN(6)
Six 
##       0       1       2       3       4       5       6 
## 2494800 1995840 1283040  760320  432000       0  518400
Six/sum(Six)
##          0          1          2          3          4          5 
## 0.33333333 0.26666667 0.17142857 0.10158730 0.05772006 0.00000000 
##          6 
## 0.06926407
Seven <- atLeastN(7)
Seven
##         0         1         2         3         4         5         6 
## 227026800 181621440 116756640  69189120  39312000  21772800         0 
##         7 
##  25401600
Seven/sum(Seven)
##          0          1          2          3          4          5 
## 0.33333333 0.26666667 0.17142857 0.10158730 0.05772006 0.03196803 
##          6          7 
## 0.00000000 0.03729604

Not only does the probability of 0 stay the same, so does the probability of 1, and 2, and 3, and so on, as we increase the number of people. We can conjecture that this will remain the case up to 330 million so that the probability that at least one person overlaps with everyone else is 2/3 and at least two people overlap is 1 - 1/3 - 4/15 = 2/5.

This is worth exploring more. Referring to the result for 7 people above, we can determine that the probability distribution will continue in this pattern: 1/3, 4/15, 18/105, 96/945, 600/10395, 4320/135135. This is more than enough to pick up a pattern. For \(k=0,1,2,\ldots\), we get that \[ p(k) = \frac{(k)(k!)}{(2k+3)!!}, \] where \(n!! = n(n-2)(n-4)\ldots (3)(1)\) if n is odd and \(n!! = n(n-2)(n-4)\ldots (2)\) if n is even.

Knowing the probability distribution will help us get the expected value! Let’s build the probability distribution for 0 to 100.

k <- 0:100
pk <- rep(0,101)
for(i in k){
   pk[i+1] <- (i+1)*factorial(i+1)/prod(2*(0:i)+3)
}

## Should sum to 1 if it is a probability distribution
sum(pk)
## [1] 1
## Expected value is the sum-product of k and pk.
sum(k*pk)
## [1] 1.570796
## Is that number what I think it is?!?
pi/2
## [1] 1.570796

If we set that up, we get that \[ \frac{\pi}{2} = \sum_{k=0}^{\infty} \frac{k^2(k!)}{(2k+3)!!}. \] The closest I found something like this was equation 23 in https://mathworld.wolfram.com/PiFormulas.html which says that \[ \frac{\pi}{2} = \sum_{k=0}^{\infty} \frac{k!}{(2k+1)!!} \]