DonaldRauscher.com

A Blog About D4T4 & M47H

538 Riddler: A Variation of the Drunkard's Walk ... In a Bar

14 July ’16

This week’s Riddler is a variation on the well-known OR problem, the drunkard’s walk. We can model this problem as an absorbing Markov Chain with X+Y+1 states. The transition probability matrix is the following:

Once we compute the fundamental matrix (N), calculating the expected number of steps until absorption is fairly easy. Plugging in a few different values of X and Y, a trend emerges: the expected number of coin flips is simply XY. Beautiful.

X <- 4
Y <- 13

# build Q
n_transient_state <- X + Y - 1
Q <- matrix(0.5, n_transient_state, n_transient_state)
tri <- cbind(rbind(FALSE, lower.tri(matrix(nrow=n_transient_state-1,ncol=n_transient_state-1))), FALSE)
Q[tri] <- 0; Q[t(tri)] <- 0; diag(Q) <- 0

# build R
R <- matrix(data = 0, nrow = n_transient_state, ncol = 2)
R[1,1] <- 0.5
R[n_transient_state,2] <- 0.5

# put together into P
P <- rbind(cbind(Q, R), cbind(matrix(0, 2, n_transient_state), diag(2)))

# fundamental matrix
N <- solve(diag(n_transient_state) - Q)

# expected number of steps to absorbtion
t <- N %*% matrix(1, n_transient_state, 1)

ggplot() +
  geom_line(aes(x=-(X-1):(Y-1), y=t)) +
  geom_point(aes(x=0, y=t[X]), colour="red", size=1) +
  geom_text(aes(x=0, y=t[X], label=t[X]), colour="red", nudge_y=2) +
  xlab("Starting Point") + ylab("Expected Game Length")

538 Riddler: Defending Riddler Headquarters

14 July ’16

The challenging part of this problem was creating an exhaustive state-space of bisectors. Odd-numbered polygons are a real pain. I started with a known bisector: a line that goes through one point and intersects the mid-point of the opposite side. If we shift the line slightly on one side, how much will we need to shift it on the opposing side (a rotation) to keep the area on either side equal? A little trig helps us figure this out. Interestingly, these bisectors don't always intersect the centroid. Because of this, an interesting, star-shaped hot spot forms in the middle of the shape. We can minimize our chances of getting hit if we stand at the mid point of one of the outer walls of the building, which makes intuitive sense.

library(ggplot2)

# make the pentagon
x <- c(0, cumsum(rep(c(1, cos(2*pi/5), -cos(pi/5), -cos(pi/5), cos(2*pi/5))/2, each = 2)))
y <- c(0, cumsum(rep(c(0, sin(2*pi/5), sin(pi/5), -sin(pi/5), -sin(2*pi/5))/2, each = 2)))
pentagon <- data.frame(x = x, y = y)

# make some bisectors
n <- 15
delta.edge <- seq(0, 0.5, 0.5/n)
A <- 0.5/tan(pi/10)
delta.point <- A*delta.edge / (delta.edge*cos(3*pi/10) + A*sin(3*pi/10))

bisectors <- do.call(rbind, lapply(1:5, function(i){

  if ((i %% 2) == 1){
    delta.1 <- delta.point
    delta.2 <- delta.edge
  } else {
    delta.1 <- delta.edge
    delta.2 <- delta.point
  }

  bisectors.begin.x <- x[i] + (x[i+1] - x[i])*delta.1/0.5
  bisectors.begin.y <- y[i] + (y[i+1] - y[i])*delta.1/0.5

  bisectors.end.x <- x[i+5] + (x[i+6] - x[i+5])*delta.2/0.5
  bisectors.end.y <- y[i+5] + (y[i+6] - y[i+5])*delta.2/0.5

  bisectors.x <- do.call(c, lapply(1:n, function(j) c(bisectors.begin.x[j], bisectors.end.x[j])))
  bisectors.y <- do.call(c, lapply(1:n, function(j) c(bisectors.begin.y[j], bisectors.end.y[j])))

  return(data.frame(x = bisectors.x, y = bisectors.y, piece = rep((n*(i-1) + 1):(n*i), each = 2)))

}))

# plot it
ggplot() +
  geom_path(aes(x = pentagon$x, y = pentagon$y)) +
  geom_path(aes(x = bisectors$x, y = bisectors$y, group = bisectors$piece), colour = "red")

538 Riddler: Defeating Roger Federer

07 July ’16

I began this challenge at the obvious starting point: I win my first 71 points against Roger. This puts me up 2 sets to 0, up 5-Nill in the 3rd, and winning 40-Love in what is possibly the final game of the match. Things look pretty good; I've got a triple match point. However, Roger's greatness cannot be underestimated, even in his twilight years. The probability that we win this specific game is:

This technically represents the lower bound of our win probability. However, the probability that I prevail if I lose this game is infinitesimally small, so this reprsents a good approximation.

However, if we focus exclusively on that final game, there is a scenario which gives us a few more opportunities to win. We can begin the match up 2 sets to 0 and up 6-0 in the tie break in the 3rd (tie breaks are allowed in all sets except the 5th at Wimbledon). This gives us 6 match points! The probability that we win this tie break is:

When the probability of winning each point hits 11%, we are more likely to prevail in the tie break than Roger! Cheers.