Token on a grid

Throughout this solution, $p_{i,j}$ will represent the probability that the token was originally placed in the square in the $i^{th}$ column and $j^{th}$ row of the chessboard. Because we are looking at a $2\times100$ chessboard, $i\in\{1,2,3,...,100\},j\in\{1,2\}$ .

We begin by finding the probability that the token was originally placed in each square. To do this, we must use the fact that the probability that the token is in a given square before the move is the same as the probability that it's in that square after the move. Because Brilli picks a square to move the token to uniformly at random from the squares surrounding the original square, the token has probability $\frac{1}{5}$ to move to any of its surrounding squares, unless the original square is in column $1$ or column $100$ , in which case that probability is $\frac{1}{3}$ . Thus, it must be the case that $p_{i,j}$ is the sum of $\frac{1}{5}$ (or $\frac{1}{3}$ , in a few cases concerning the edge columns) times the probabilities that the token was originally placed in each of the surrounding squares.

For ease of writing, let $p_{1,1}=a$ and $p_{1,2}=b$ . From the observation above, we have $a = \frac{1}{3}b + \frac{1}{5}p_{2,1} + \frac{1}{5}p_{2,2}$ and $b = \frac{1}{3}a + \frac{1}{5}p_{2,1} + \frac{1}{5}p_{2,2}$ . Subtracting the second equation from the first yields $a - b = \frac{1}{3}(b-a) \to a - b = 0 \to a = b$ . This fact may have been obvious from the symmetry present in the problem, but it is good to ensure that it is, indeed, true.

We see that $p_{2,1} = \frac{1}{3}a + \frac{1}{3}b + \frac{1}{5}(p_{2,2} + p_{3,1} + p_{3,2})$ and $p_{2,2} = \frac{1}{3}a + \frac{1}{3}b + \frac{1}{5}(p_{2,1} + p_{3,1} + p_{3,2})$ . From these two equations we can show that $p_{2,1} = p_{2,2}$ . Using similar equations and manipulations, it can be easily shown that this applies to all columns. That is, $\forall{i}\in\{1,2,3,...,100\}, p_{i,1} = p_{i,2}$ .

We now take another look at $a = \frac{1}{3}b + \frac{1}{5}p_{2,1} + \frac{1}{5}p_{2,2}$ . Using the facts from above, we turn this into $a = \frac{1}{3}a + \frac{2}{5}p_{2,1} \to p_{2,1} = \frac{5}{3}a$ . Plugging this into $p_{2,1} = \frac{1}{3}a + \frac{1}{3}b + \frac{1}{5}(p_{2,2} + p_{3,1} + p_{3,2})$ gives $\frac{5}{3}a = \frac{2}{3}a + \frac{1}{5}\cdot\frac{5}{3}a + \frac{2}{5}p_{3,1} \to p_{3,1} = \frac{5}{3}a = p_{2,1}$ . Continuing this process of using $p_{i,1}$ to find $p_{i+1,1}$ (which, we remind ourselves, is the same as $p_{i+1,2}$ ) gives us that $p_{1,1} = p_{1,2} = p_{100,1} = p_{100,2} = a$ and $p_{2,1} = p_{2,2} = p_{3,1} = p_{3,2} =...= p_{99,1} = p_{99,2} = \frac{5}{3}a$ .

The probability that the token gets placed on any square on the board is the sum of the probabilities that the token gets placed on a certain square on the board and must, of course, be $1$ , as Brilli certainly placed the token on the board. From above, we know that there are $196$ squares which have probability $\frac{5}{3}a$ attached to them and $4$ which have probability $a$ attached to them. Thus, $196\cdot\frac{5}{3}a + 4\cdot{a} = 1 \to a = \frac{3}{992} \to \frac{5}{3}a = \frac{5}{992}$ .

We can now calculate the probability $q$ that the problem asks for. The probability that the token is placed in a square in the "good" columns (i.e., columns $5,6,...,44$ ) is $\frac{5}{992}$ for each square in those columns. If the token is originally placed in any of the columns numbered $6,7,...,43$ , it must be in one of the "good" columns after the move, as it can't move more than one column away from its original position. However, if the token is originally placed in a square in columns $5$ or $44$ , it can only move to $3$ of the $5$ surrounding squares if it wants to stay in the "good" columns. There are, of course, $76$ squares in columns $6,7,...,43$ and $4$ in column $5$ and column $44$ . Thus, $q = \frac{5}{992}(76\cdot1 + 4\cdot\frac{3}{5}) = \frac{392}{992} = \frac{49}{124}$ . Our answer is $49 + 124 = \fbox{173}$ .

Consider a connected undirected graph with probabilities for vertices. Write the probabilities for the vertices as a vector $p=(p_1,p_2...p_n)^t$ . We can find the probabilities for reaching the vertices in the next step by $p^\prime=A_d p$ where $A_d$ is the adjacency matrix $A$ modified by dividing every column by the degree $d_i$ of the corresponding vertex.

We require $p^\prime=p$ , which gives $(A_d-I)p=0$ . Let $L_d=I-A_d$ . We have $L_dp=0$ . Now, this equality will still be satisfied if we divide row $i$ of the vector $p$ by some quantity $c_i$ and multiply column $i$ of the matrix by the same constant. Choose $c_i=d_i$ . Then the equation becomes $Lq=0$ with $q=(\frac{p_1}{d_1},\frac{p_2}{d_2}...\frac{p_3}{d_3})^t$ and $L$ is the matrix formed by adding vertex degrees as diagonal entries to the negative of the adjacency matrix. But this is just the definition of the laplacian matrix of the graph.

Thus we want $q$ to be an eigenvector of the laplacian matrix with eigenvalue 0. But it is well-known that the only 0-eigenvalue eigenvector of the laplacian of a connected graph is $(1,1...1)^t$ (The fact that a connected graph laplacian can have only one 0-eigenvector is a direct consequence of Kirchhoff's theorem ). Thus we find that all $q_i$ s are equal, and thus $p_i$ s are proportional to $d_i$ . Normalising with the sum of degrees of all vertices, we obtain $p_i=\frac{d_i}{\sum_i d_i}$ .

Thus, the probability of being at a corner cell is $\frac{3}{992}$ while that of being at any other cell is $\frac{5}{992}$ . Hence the probability of being in columns $\{5..44\}$ is $\frac{400}{992}$ . The only way of going out of these columns in the next step is if you were initially at column 5 or column 44, and moved to any of the 2 (out of 5) neighbours that took you outside. The probability of this happening is $\frac{2}{40}\times\frac{2}{5}=\frac{1}{50}$ . Hence the required probability is $\frac{400}{992}\times\frac{49}{50}=\frac{49}{124}$

By symmetry, the probability of the token's position being in the first row must equal the probability of it being in the second, since if this were not the case, the token's position after the move could not follow the same probability distribution as before the move. Let $T, T' \in \{1, 2, \ldots, 100 \} \sim P$ be random variables indicating the column position of the token before and after the move, respectively, and denote $\begin{aligned} p_{j,k} &= p_k = \textstyle\frac{1}{2}\Pr[T = k], \\ p'_{j,k} &= p'_k = \textstyle\frac{1}{2}\Pr[T' = k] \end{aligned}$ be the respective probabilities that the token is located in row $j$ and column $k$ . Then $\begin{aligned} p_1 &= p_{1,1} = p'_{1,1} \\ &= \frac{1}{3}p_{2,1} + \frac{1}{5}p_{2,2} + \frac{1}{5}p_{1,2} \\ &= \frac{1}{3}p_1 + \frac{2}{5}p_2. \end{aligned}$ Similarly, $\begin{aligned} p_2 &= p_{1,2} = p'_{1,2} \\ &= \frac{1}{3}p_{1,1}+\frac{1}{3}p_{2,1}+\frac{1}{5}p_{2,2}+\frac{1}{5}p_{2,3}+\frac{1}{5}p_{1,3} \\ &= \frac{2}{3}p_1 + \frac{1}{5}p_2 + \frac{2}{5}p_3. \end{aligned}$ For columns $3 \le T \le 98$ , there are no adjacent cells that belong to column $1$ or $100$ , so we have $p_k = \frac{2}{5}p_{k-1} + \frac{1}{5}p_{k} + \frac{2}{5}p_{k+1}, \quad 3 \le k \le 98.$ Finally, we have the condition $\sum_{k=1}^{100} p_k = \frac{1}{2}$ . Simplifying the first two conditions yields $p_1 = \frac{3}{5} p_2$ , $p_2 = p_3$ , and since the third condition is equivalent to $p_k = (p_{k-1} + p_{k+1})/2$ , it is easy to see that $p_3 = p_4 = \ldots = p_{98} = p_{99}$ . Again by symmetry, we have $p_{100} = p_1$ , so all together it follows that $\frac{1}{2} \sum_{k=1}^{100} p_k = \left( 2 \cdot \frac{3}{5} + 98 \right) p_2 = \frac{496}{5} p_2,$ hence the distribution $P$ is $p_{j,1} = p_{j,100} = 3/992, \quad p_{j,2} = p_{j,3} = \ldots = p_{j,98} = 5/992.$

Now that we know the distribution for the token, consider the partition $C' = \{6, 7, \ldots, 43 \}, C'' = \{5,44\}$ of $C$ . Then the token is guaranteed to be in $C$ after the move if it is in $C'$ before the move. If the token is in $C''$ before the move, then with probability $\frac{2}{5}$ , it will move out of $C$ on the next move. So we have $\begin{aligned} q &= \Pr[T, T' \in C] \\ &= \Pr[T' \in C \mid T \in C']\Pr[T \in C'] \\ &\quad + \Pr[T' \in C \mid T \in C'']\Pr[T \in C''] \\ &= \Pr[T \in C'] + \frac{3}{5} \Pr[T \in C''] \\ &= 2 \left( \sum_{k=6}^{43} p_k + \frac{3}{5}(p_5 + p_{44}) \right) \\ &= 2 \cdot \frac{5}{992} \left( 38 + \frac{3}{5} \cdot 2 \right) \\ &= \frac{49}{124}. \end{aligned}$ Therefore, the answer is $49 + 124 = \boxed{173}$ .

Let $p_i$ be the in the column $i$ . We have:

$\sum_{i=1}^{100}p_i = 1$

If the token starts at column $c=1$ or $c=100$ it has 3 neighbours to go, 1 of them is at the same column, 2 are in the neighbouring columns (2 or 99 respectively), i.e. it remains at the same column with $\frac{1}{3}$ probability and goes to the neighbouring column with $\frac{2}{3}$ probability. Similarly, for all other columns, it goes to the column to the left or right with $\frac{2}{5}$ probability each, and remains at the same column with probability $\frac{1}{5}$ . Since the probability distribution after the move must be the same as before the move according to the problem statement, this can be written as:

$p_1 = \frac{1}{3}p_1 + \frac{2}{5}p_2$

$p_2 = \frac{2}{3}p_1 + \frac{1}{5}p_2 + \frac{2}{5}p_3$

$p_3 = \frac{2}{5}p_2 + \frac{1}{5}p_3 + \frac{2}{5}p_4$

$\ldots$

$p_{99} = \frac{2}{5}p_{98} + \frac{1}{5}p_{99} + \frac{2}{3}p_{100}$

$p_{100} = \frac{2}{5}p_{99} + \frac{1}{3}p_{100}$

Rewriting these we get:

$p_2 = \frac{5}{3}p_1$

$p_3 = p_2$

$p_4 = p_3$

$\ldots$

$p_{99} = p_{98}$

$p_{100} = \frac{3}{5}p_{99}$

or:

$p_2 = p_3 = \ldots = p_{99} = \frac{5}{3}p_1 = \frac{5}{3}p_{100}$

and since they must sum up to 1:

$98p_2 + 2\frac{3}{5}p_2 = 1 \Rightarrow p_2 = \frac{5}{496}$

or:

$p_1 = p_{100} = \frac{3}{496}$ , $p_2=p_3=\ldots =p_{99}=\frac{5}{496}$

Now for the token to start in one of the columns of $C = \{5,6,\ldots 44\}$ , it either starts in one of the columns of $\{6,7,\ldots 43\}$ , or it starts in column 5 or 44 and remains on that column or goes to column 6 or 43 respectively ( $\frac{3}{5}$ probability). That leads to:

$q = (43-6+1)\frac{5}{496} + 2\frac{5}{496}\frac{3}{5} = \frac{196}{496} = \frac{49}{124}$

From above condition, named the square as $(x , y)$ , where $x$ as the column and $y$ as the row. And, defined $P_{(x, y)}$ as probability that token placed into square $(x, y)$ . From the problem, we know that, "The token is then moved uniformly at random to one of the horizontally, vertically, or diagonally adjacent squares. The probability that the token is in a particular position after it has been moved also satisfies the distribution P.".

Now, assume that, $P'_{(x, y)}$ is the probability after move. Look that, if the move came from $x = 1$ or $100$ , then the probability is $\frac{1}{3}$ from the previous square , but if the move came from the other one, then the probability is $\frac{1}{5}$ from the previous square. This is due the square from column $1$ and $100$ only have $3$ , so the probability each move is $\frac{1}{3}$ , analogue with the other column

Then, it's easy to see that : $P_{(1, 1)} = P'_{(1, 1)} = \frac{P_{(1,2)}}{3} + \frac{P_{(2,2)}}{5} + \frac{P_{(2,1)}}{5} \ldots \ldots (1)$ $P_{(1, 2)} = P'_{(1, 2)} = \frac{P_{(1,1)}}{3} + \frac{P_{(2,2)}}{5} + \frac{P_{(2,1)}}{5} \ldots \ldots(2)$

Subtract (1) from (2), we obtain that : $P_{(1,2)} - P_{(1,1)} = \frac{P_{(1,1)}}{3} - \frac{P_{(1,2)}}{3} \implies P_{(1,2)} = P_{(1,1)}$

But, we also see that : $P_{(2,2)} = \frac{P_{(3,1)} + P_{(3,2)}}{5} + \frac{P_(1,2) + P(1, 1)}{3} + \frac{P_{(2,1)}}{5} \ldots \ldots(3)$ $P_{(2,1)} = \frac{P_{(3,1)} + P_{(3,2)}}{5} + \frac{P_(1,2) + P(1, 1)}{3} + \frac{P_{(2,2)}}{5} \ldots \ldots(4)$

Analog with the previous one, we obtain $P_{(2, 2)} = P_{(2, 1)}$ . Then, subtitute it, into (1), we obtain that :

$P_(2, 1) = P(2, 2) = a$ $P_{(1, 1)} = P_{(1, 2)} = \frac{3a}{5}$

From (3) and (4), we also obtain that $P(3, 1) + P(3, 2) = 2a$ . And, we skip it into the lemma, since it's satisfy the condition $P_{(n+1, 1)} + P_{(n+1, 2)} = 2a$ .

Lemma : If $P_{(n, 1)} = P_{(n, 2)} = a$ then $P_{(n+1, 1)} = P_{(n+1, 2)} = a$ forall $2 \le n \le 98$ . $$ Proof : Analogue from equation (3) and (4), we obtain that : $a = P_{(n, 1)} = \frac{P_{(n+1,1)} + P_{(n+1,2)} + P_{(n,2)} + P_{(n-1,1)} + P_{(n-1,2)}}{5} = \frac{P_{(n+1,1)} + P_{(n+1,2)} + 3a}{5} \ldots \ldots (5)$ $a= P_{(n, 2)} = \frac{P_{(n+1,1)} + P_{(n+1,2)} + P_{(n,1)} + P_{(n-1,1)} + P_{(n-1,2)}}{5} = \frac{P_{(n+1,1)} + P_{(n+1,2)} + 3a}{5} \ldots \ldots (6)$

From (5) and (6) we obtain that $P_{(n+1, 1)} + P_{(n+1, 2)} = 2a$

also : $P_{(n+1, 1)} = \frac{P_{(n+2,1)} + P_{(n+2,2)} + P_{(n+1,2)} + P_{(n,1)} + P_{(n,2)}}{5} \ldots \ldots (7)$ $P_{(n+1, 2)} = \frac{P_{(n+2,1)} + P_{(n+2,2)} + P_{(n+1,1)} + P_{(n,1)} + P_{(n,2)}}{5} \ldots \ldots (8)$

Subtract from (8) to (7), then it will implies $P_{(n+1, 1)} = P_{(n+1, 2)}$ . Then, from $P_{(n+1, 1)} + P_{(n+1, 2)} = 2a$ . It will implies that : $P_{(n+1, 1)} = P_{(n+1, 2)} = a$ . Q.E.D

Then, since it's symmetric, we obtain that : $P(x, y) = a \text{for} 2 \le x \le 99$ $P(x, y) = \frac{3a}{5} \text{for} x = 1 \text{or} x = 100$

Since, the sum all of probability is $1$ , then : $1 = \sum_{x = 1}^{100} (P(x, 1) + P(x, 2)) = 4 \times \frac{3a}{5} + 196 \times a = \frac{992}{5} \implies a = \frac{5}{992}$

The, probability that the token on column ${5, 6, ... , 44}$ is $\frac{5}{992} \times 2(44-5+1) = \frac{25}{62}$ .

Look that, the probability token on column ${6, 7, ...., 43}$ still in one of these column is $1$ for each square. And, for square the probability $P(5, 1) = P(5, 2) = P(44, 1) = P(44, 2) = \frac{3}{5}$ that still one these column.

Proof : Took square (5, 1). Since there are $5$ possibilities move, that is $(4, 1), (4, 2), (5, 2), (6, 1), (6, 2)$ . And, see that, $3$ of $5$ square still in those column. Then, the probability is $\frac{3}{5}$

So, the probability, that the token still on these column is :

$\frac{2(38) + 4(\frac{3}{5})}{80} = \frac{49}{50}$

Then, the probability that the token is placed into one of these columns of and after being moved is still in one of those columns is $\frac{25}{62} \times \frac{49}{50} = \frac{49}{124}$

So, $a + b = 49 + 124 = \boxed{173}$

Let $P_i$ be the probability that the token is in column $i$ . The condition in the problem implies that $P_1 = \frac13 P_1 + \frac25 P_2$ , $P_2 = \frac23 P_1 + \frac15 P_2 + \frac25 P_3$ , $P_n = \frac25 P_{n-1} + \frac15 P_n + \frac25 P_{n+1}$ for $3 \le n \le 98,$ $P_{99} = \frac25 P_{98} + \frac15 P_{99} + \frac23 P_{100}$ , and $P_{100} = \frac25 P_{99} + \frac13 P_{100}.$ And of course $\sum P_i = 1.$

Subtracting $P_n$ from both sides of the given equations, we get $P_2 = \frac53 P_1,$ $P_3 = 2 P_2 - \frac53 P_1$ , $P_{n+1} = 2 P_n - P_{n-1}$ for $3 \le n \le 98$ , $P_{100} = \frac65 P_{99} - \frac35 P_{98},$ and $P_{100} = \frac35 P_{99}$ .

Solving for $P_n$ one by one in terms of $P_1$ , we quickly see that $P_2 = P_3 = \cdots = P_{99} = \frac53 P_1$ and $P_{100} = P_1$ . So $1 = \sum P_i = \left( 2 + 98 \frac53 \right) P_1 = \frac{496}3 P_1.$

So $P_1 = P_{100} = \frac3{496}$ and $P_n = \frac5{496}$ for $2 \le n \le 99$ . Now $q = \frac35 P_5 + (P_6 + \cdots + P_{43}) + \frac35 P_{44}$ , so $q = \frac5{496} \left( \frac35 + 38 + \frac35 \right) = \frac{49}{124}$ , so the answer is $173$ .

Suppose $P_n$ is the probability that the token is placed into column n.

Because after a move to a adjacent square, $P_n$ is not changed, we have: $P_1=\frac{1}{3}P_1+\frac{2}{5}P_2$

and $P_2=\frac{2}{3}P_1+\frac{1}{5}P_2+\frac{2}{5}P_3$ .

Therefore, $P_1=\frac{3}{5}P_2$ and $P_2=P_3$ .

Similarly, we have $P_2=P_n \forall 3 \leq n \leq 99$ and $P_{100}=P_1=\frac{3}{5}P_2$ .

Because the sum of all $P_n$ is equal to 1, we have: $2.\frac{3}{5}P_2+98P_2=1$ or $P_2=\frac{5}{496}$ .

So, $q=38P_2+\frac{3}{5}.2P_2=\frac{49}{124}$ .

So the answer is: 49 + 124 = 173.

We first consider the following system of equations:

$\begin{array}{l} x = py + m\\ y = px + m\\ \end{array}$

Solving these equations yields $x = y = \frac{m}{p-1}$ or $x = y, p=1, m = 0.$ In both instances, we have $x = y.$

Let $n$ be the number of columns in the grid let $k$ be the number of columns in $C$ .

Let $P_{i,j}$ be the probability that the token is placed into row $i$ and column $j.$ Using the fact that the distribution is $P$ both before and after moving the token, we calculate $P_{1,j} = d (P_{1,j-1} + P_{2,j-1}) + e (P_{2,j}) + f(P_{1,j+1} + P_{2,j+1}),$ $P_{2,j} = d (P_{1,j-1} + P_{2,j-1}) + e (P_{1,j}) + f(P_{1,j+1} + P_{2,j+1}),$ where $d,e,f$ can be $0, \frac{1}{3}, \mbox{ or } \frac{1}{5},$ depending on the value of $j.$ These equations satisfy the $x = py + m, y = px + m$ format, which tells us that $P_{1,j} = P_{2,j}$ for each $j.$ Let $P_{j} = P_{1,j} = P_{2,j}.$

If we solve the equation for $P_{1,1},$ we get $5 P_{1} = 3 P_{2}.$ If we use this relation to solve the equation for $P_{1,2}$ we get $P_{2} = P_{3}.$ Repeating, we get that $\frac{5}{3} P_{1} = P_{2} = P_{3} = \cdots = P_{n-1} = \frac{5}{3} P_{n}.$ When we combine this with the equation $2 \sum\limits_{j=1}^{n} P_{j} = 1$ to get $\frac{5}{3} P_{1} = P_{2} = P_{3} = \cdots = P_{n-1} = \frac{5}{3} P_{n} = \frac{5}{10n - 8}.$

Neither the first nor the last columns of the chessboard are in $C$ . The probability that the token begins in one of the columns of $C$ that is neither the first nor the last is $2(k-2)\frac{5}{10n-8} = \frac{10k-20}{10n-8}.$ The probability that the token belongs in either the first or last column of $C$ and then does not leave $C$ is $4\frac{5}{10n-8} \frac{3}{5} = \frac{12}{10n-8}.$ Adding these together gives a total probability of $\frac{10k-8}{10n-8}.$

When $k = 40$ and $n = 100$ we get the probability is $\frac{10(40) - 8}{10(100)-8} = \frac{49}{124}.$ So $a + b = 49 + 124 = 173.$

the value of q comes to be a/b=49/124 so a+b=173

We first consider the number of ways to place and move any token placed on the board.

If a token is placed in columns $2$ through $99$ , it can be moved $5$ different ways ( $1$ way vertical, $2$ ways horizontal, $2$ ways diagonal) to an adjacent square so that the token stays on the board. There are $98*2=196$ squares in columns $2$ through $99$ , so there are a total of $196*5=980$ ways to place and move a token placed in in columns $2$ through $99$ .

If a token is placed in columns $1$ or $100$ , it can be moved $3$ different ways ( $1$ way vertical, $1$ way horizontal, $1$ way diagonal) so that the token stays on the board. There are $2*2=4$ squares in columns $1$ or $100$ , so there are a total of $4*3=12$ ways to place and move a token placed in in columns $1$ or $100$ .

We add $980$ and $12$ to get $992$ total possibilities for placing and moving any token placed on the board.

We now count the number of ways that we can place and move a token within $C=\left\{5, 6, 7, ... 43, 44\right\}$ .

If a token is placed in columns $6$ through $43$ , it can be moved $5$ different ways ( $1$ way vertical, $2$ ways horizontal, $2$ ways diagonal) to an adjacent square so that it still stays in $C$ . There are $38*2=76$ squares in columns $6$ through $43$ , so there are a total of $76*5=380$ ways to place and move a token placed in columns $6$ through $43$ .

If a token is placed in columns $5$ or $44$ , it can be moved $3$ different ways ( $1$ way vertical, $1$ way horizontal, $1$ way diagonal) so that it still stays in $C$ . There are $2*2=4$ squares in columns $5$ or $44$ , so there are a total of $4*3=12$ ways to place and move a token placed in in columns $5$ or $44$ .

We add $380$ and $12$ to get $392$ total possibilities for placing and moving a token so that it is placed in $C$ and stays in $C$ after being moved.

Therefore, $q=\frac{392}{992}=\frac{49}{124}$ . $a=49$ and $b=124$ , so $a+b=\fbox{173}$