In a 2025 by 2025 grid, every cell initially contains a `1'. Every minute, we simultaneously replace the number in each cell with the sum of numbers in the cells that share an edge with it. (For example, after the first minute, the number 2 is written in each of the four corner cells.) After 2025 minutes, we colour the board in checkerboard fashion, such that the top left corner is black. Find the difference between the sum of numbers in black cells and the sum of numbers in white cells. Proposed by chorn
Problem
Source: 2024 IRN-SGP-TWN Friendly Math Competition P1
Tags: grid
02.08.2024 16:50
Answer: $0$ The trick is to track where each of the original ones end up. After the first minute it gives the one to all of its neighbors, after the second minute to all of its neighbors neighbors, and so on. So after $2025$ minutes for every path of length $2025$ we can draw starting at our original one and connecting adjacent squares will 'contribute' one to the cell at the end of its path. As paths of length $2025$ connect black and white squares each path will contribute one to a black square and one to a white square when traversed both ways.
04.08.2024 07:18
The answer is $0$. The main claim is that after $n$ minutes, the number in each cell is the total count of paths of length $n+1$ ending in that square. (A path of length $x$ is defined as a sequence of not necessarily distinct cells $c_1,c_2,\dots,c_x$ such that $c_i$ is orthogonally adjacent to $c_{i+1}$ for all $1\leq i<x$.) This is proven by induction on $n$: The base case is $n=0$, where there is a unique path of length $1$ ending on each cell. For the induction step, observe that for a cell $c_{n+2}$, there is a bijection between paths of length $n+2$ ending in $c_{n+2}$ and paths of length $n$ ending in a cell adjacent to $c_{n+2}$ by removing $c_{n+2}$ from the path. Thus the number of paths of length $n+1$ ending in $c_{n+2}$ is exactly the sum of values of cells adjacent to $c_{n+2}$ at time $n$, which is the value of cell $c_{n+2}$ at time $n+1$, completing the induction. Finally, we have (after $2025$ minutes): \begin{align*} \sum(\text{values of black cells})&=\sum(\text{\# paths of length 2026 ending in black cell})\\ &=\sum(\text{\# paths of length 2026 beginning in black cell})\\ &=\sum(\text{\# paths of length 2026 ending in white cell})\\ &=\sum(\text{values of white cells}) \end{align*}where the equalities come from the main claim, reversing the paths, path length being odd, and the main claim respectively. So the difference is $0$.