Grid probability problem

Question

Let's say that you have a $5 \times 5$ grid. There is one correct square in each row. Your job is to make it across the grid. There is one correct answer in each row of the grid. You start by picking any of the five squares in the first row of the grid. You can proceed forward, forward and up, or forward and down. What is the probability that you get through the grid in one try without selecting any wrong answers? The correct path is guaranteed to be contiguous

At first, I thought it would be $(1/5)\times (1/3)^4$ but if you are on one of the edges you only have two options and therefore you have a $50\%$ chance of getting right. I am having trouble figuring out the probability that you end up on the edge to begin with, if we assume that you got the right answer and are in a row $n$.

Answer 1

We can just make an array showing the number of ways to finish from each square. The right column is all $1$s as you have finished. Each column to the left has the sum of the cells you can reach. The figure below has the result. It shows there are $60$ paths that start with the second cell. The $259$ is the total number of paths. If you assume the creator has chosen a path at random, you also choose one at random and you have $\frac 1{259}$ chance of being right.

Answer 2

It seems that there will be no better statement of the problem, so i will give an answer in the same shape. We answer the special case in the framework of the more general case describe below.

We start with a $K\times N$ empty matrix, so there are

• $K$ rows, numbered from $1$ to $K$,
• $N$ columns, numbered from $1$ to $N$,
• $KN$ "cells",
• and build an ordered graph on the cells, from the cell $(k,n)$ we can pass to one of the following cells $(k+1, n-1)$, $(k+1, n+)$, $(k+1, n+1)$, with the condition that the resulted cell lives in the given empty matrix.

The question wants the number $c(K,N)$ of all maximal paths starting from the first column (i.e. from some cell $(k,1)$) to the last column.

We define here the more specialized numbers $c_i(K,N)$ of all path as above, that start from $(i,1)$, where $i$ can be taken "up to the middle", so that we can use the obvious symmetry of the margins. (So $c_1=c_K$, $c_2=c_{K-1}$ and so on.)

The problem wants in these notations $$ c(5,5)= c_1(5,5)+c_2(5,5)+c_3(5,5)+c_2(5,5)+c_1(5,5)\ . $$ We have obviously $$ \begin{bmatrix} c_1(5,N+1)\\ c_2(5,N+1)\\ c_3(5,N+1)\\ c_2(5,N+1)\\ c_1(5,N+1) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}^N \begin{bmatrix} c_1(5,1)\\ c_2(5,1)\\ c_3(5,1)\\ c_2(5,1)\\ c_1(5,1) \end{bmatrix} $$ or simpler, but with less symmetry $$ \begin{bmatrix} c_1(5,N+1)\\ c_2(5,N+1)\\ c_3(5,N+1)\\ \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 2 & 1 \end{bmatrix}^N \begin{bmatrix} c_1(5,1)\\ c_2(5,1)\\ c_3(5,1) \end{bmatrix}\ . $$ The answer is thus using the simpler version $$ \begin{bmatrix} 2&2&1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 2 & 1 \end{bmatrix}^4 \begin{bmatrix} 1\\1\\1 \end{bmatrix} = 259 \ . $$

So there are $259$ paths in the graph, assuming they are equally probable, the asked probability is $1/259$.

---

[sage][1] code computing the above number:

sage: q = matrix( 1, 3, [2,2,1] )
sage: A = matrix( 3, 3, [1,1,0, 1,1,1, 0,2,1] )
sage: v = matrix( 3, 1, [1,1,1] )
sage: q*A^4*v
[259]

(Sage computes also the minimal polynomial, we do not have a "simple diagonalization" of the one or the other matrix written above, so for computational reasons the result should be enough.)