Solution:
We can assume that the initial numbers are all distinct, since this occurs with probability 1. For clarity, we denote the value of ai after t seconds as ai,t. The index i is taken mod 2025.
In general, after k<1012 seconds, we claim the expected number of distinct values remaining is k+12025. To show this, we first prove that for any remaining value, its appearances are consecutive. Indeed, note that for all i and k,
ai,k=max(ai−1,k−1,ai,k−1,ai+1,k−1)=max(ai−2,k−2,…,ai+2,k−2)=⋯=max(ai−k,0,…,ai+k,0).
Given an initial number ac,0, let j1 and j2 be the smallest positive integers such that ac−j1,0>ac,0 and ac+j2,0>ac,0. As the initial numbers are distinct, we conclude ai,k=ac,0 if and only if {i−k,i−k+1,…,i+k} contains c but neither c−j1 nor c+j2 (mod 2025). The indices i that satisfy this are clearly consecutive.
Now consider the indicator variables
1i={10if ai,k=ai+1,kotherwise
for 1≤i≤2025. Note that the number of distinct values on the board after k seconds is simply ∑i=120251i. By linearity of expectation, it suffices to compute E[1i] for each i. Recall
ai,k=max(ai−k,0,…,ai+k,0)
for each 1≤i≤2025. Hence, the condition ai,k=ai+1,k can be written as
max(ai−k,0,…,ai+k,0)=max(ai+1−k,0,…,ai+1+k,0).
This is the case if and only if max(ai−k,0,…,ai+k+1,0) is either ai−k,0 or ai+k+1,0 (as ai−k,0=ai+k+1,0 and 2k+2<2025). Since the 2k+2 values ai−k,0, ..., ai+k+1,0 were sampled independently from the same distribution, each of ai−k,0 and ai+k+1,0 has a 2k+21 probability of being their maximum. Hence,
E[1i]=Pr[ai,k=ai+1,k]=2k+22=k+11.
Thus, the expected number of distinct values is
i=1∑2025E[1i]=k+12025.
Substituting k=100 yields the answer [1012025]