Consider a grid with $n{}$ lines and $m{}$ columns $(n,m\in\mathbb{N},m,n\ge2)$ made of $n\cdot m \; 1\times1$ squares called ${cells}$. A ${snake}$ is a sequence of cells with the following properties: the first cell is on the first line of the grid and the last cell is on the last line of the grid, starting with the second cell each has a common side with the previous cell and is not above the previous cell. Define the ${length}$ of a snake as the number of cells it's made of. Find the arithmetic mean of the lengths of all the snakes from the grid.
Problem
Source: Romania JBMO TST 2023 Day 4
Tags: combinatorics
rms
10.10.2023 09:51
See here. All solutions from this site are in romanian, but I think you can handle .
IbrahimNadeem
10.10.2023 12:26
Perhaps the mean implies that expected value is very useful here...
If we 'drop down' to a line/row, then we can continue in one of two directions until we reach an edge. When we 'drop down', let's break it down by case.
If we drop at the leftmost square of that line/row, then our expected number of squares in that row is $\frac{1 + 2 + ... + m}{m} = \frac{m+1}{2}$. If we drop to the second square from the left, then the expected value is $\frac{(m-1)(m) + 4}{m}$. In general, if it is $x$ squares from the leftmost square, the expected value is $\frac{\frac{x+1)(x+2)}{2} - 1 + \frac{(m-x)(m-x+1)}{2}}{m}$.