# DonaldRauscher.com

## A Blog About D4T4 & M47H

In this week's Riddler, the largest circular table that we can carve out of our 4x8 piece of wood with two congruent semi-circles has a radius of ~2.70 feet. We can fit the largest semi-circles in the wood by orienting them diagonally: From the above graph, we can use a few equations to solve for X:

We've managed to use of the available wood for our circular table.

I modelled this week's Riddler as an absorbing Markov chain. This MC has 5 transient states (representing the dollar bill sitting in front of someone) and 5 absorbing states (which represent someone winning). The transition probability matrix is the following:

From this transition matrix we can calculate the absorbing probabilities using the following formula:

Q here represents the transient-to-transient transition matrix (top left 5x5 in above matrix), and R represents the transient-to-absorbing transition matrix (top right 5x5 in the above matrix). Calculating this out, the probability of winning if the game starts at you, next to you, or two spots away from you is , , and respectively.

# number of players
n <- 5

# build Q
Q <- matrix(0, n, n)
tri <- lower.tri(matrix(nrow=n,ncol=n))
tri.inner <- cbind(rbind(FALSE, lower.tri(matrix(nrow=n-1,ncol=n-1))), FALSE)
Q[tri] <- 1/3; Q[tri.inner] <- 0; Q[n,1] <- 1/3
Q[upper.tri(Q)] <- t(Q)[upper.tri(Q)]

# build R
R <- matrix(0, n, n)
diag(R) <- 1/3

# calculate fundamental matrix
N <- solve(diag(n) - Q)

# calculate absorbing probabilities
B <- N %*% R
print(B)

           [,1]       [,2]       [,3]       [,4]       [,5]
[1,] 0.45454545 0.18181818 0.09090909 0.09090909 0.18181818
[2,] 0.18181818 0.45454545 0.18181818 0.09090909 0.09090909
[3,] 0.09090909 0.18181818 0.45454545 0.18181818 0.09090909
[4,] 0.09090909 0.09090909 0.18181818 0.45454545 0.18181818
[5,] 0.18181818 0.09090909 0.09090909 0.18181818 0.45454545

The only issue with this approach is that it is tough to derive from it an expression for the general N case, unless you're unusually gifted at finding matrix inverses, which I am not. A perhaps more intuitive approach is to set up a system of equations. Because the problem is symmetrical, we need to solve for just 3 variables, the probabilities of winning with the bill 0, 1, and 2 people away. And we can relate these probabilities to one another easily since each turn is independent. Equations for the N=5, N=6, and N=7 cases:

Here are the tediously-derived solutions to the N=2 through N=10 cases:

N
2
3
4
5
6
7
8
9
10

We can use the Fibonnaci numbers to come up with general expressions for the odd and even cases:

Using the simpler odd case and some knowledge about the Fibonnaci numbers, we can see what happens as N goes to infinity:

Link to this week's Riddler. I began by forming expressions for two known facts of the problem. equalities. Firstly, we know that the derivative of the ram's path will be the slope of the line passing through the ram's current position (x,y) and the location of the fleeing person (1,z). Secondly, by construction, we know that the distance travelled by the ram (which we express with a line integral) is some multiple of the distance travelled by the human (z). These can be expressed as follows:

Substituting and taking the derivative gives us the following second order differential equation:

Since there is no Y term, we can solve this in two steps. We treat it as a first order differential equation and solve for Y', then integrate the resulting expression to get Y:

A first iteration yields the following expression for :

Having solved for our two constants, we can use our last condition (that the ram's path passes through the origin) to come up with an expression for :

here represents the % of the ram's distance that the person travels over some period of time. We want the inverse, how much faster the ram's velocity must be, which is and conveniently also equal to . So the ram must travel about 62% faster than the human to reach the human just as he/she reaches the northeast corner of the pen. This fits into our intuitive bounds for the problem. At the very least, the ram must travel faster to reach the human, if crossing the pen along the diagonal. Our stupid ram needs to compensate for this stupidity by being 14% faster than the smart ram. 