Maths Olympiad Prep

Library / /1316 of 1394

Combinatorics Difficulty 6.1 National Olympiad Prove it United States

Problem:

Albert writes 2025 numbers a1a_{1}, ..., a2025a_{2025} in a circle on a blackboard. Initially, each of the numbers is uniformly and independently sampled at random from the interval [0,1][0,1]. Then, each second, he simultaneously replaces aia_{i} with max(ai1,ai,ai+1)\max (a_{i - 1}, a_{i}, a_{i + 1}) for all i=1,2,,2025i = 1, 2, \ldots, 2025 (where a0=a2025a_{0} = a_{2025} and a2026=a1a_{2026} = a_{1}). Compute the expected value of the number of distinct values remaining after 100 seconds.

Solution

Solution:

We can assume that the initial numbers are all distinct, since this occurs with probability 1. For clarity, we denote the value of aia_{i} after tt seconds as ai,ta_{i,t}. The index ii is taken mod 2025.

In general, after k<1012k < 1012 seconds, we claim the expected number of distinct values remaining is 2025k+1\frac{2025}{k + 1}. To show this, we first prove that for any remaining value, its appearances are consecutive. Indeed, note that for all ii and kk,

ai,k=max(ai1,k1,ai,k1,ai+1,k1)=max(ai2,k2,,ai+2,k2)==max(aik,0,,ai+k,0). a_{i,k} = \max (a_{i - 1,k - 1}, a_{i,k - 1}, a_{i + 1,k - 1}) = \max (a_{i - 2,k - 2}, \ldots, a_{i + 2,k - 2}) = \dots = \max (a_{i - k,0}, \ldots, a_{i + k,0}).

Given an initial number ac,0a_{c,0}, let j1j_{1} and j2j_{2} be the smallest positive integers such that acj1,0>ac,0a_{c - j_{1},0} > a_{c,0} and ac+j2,0>ac,0a_{c + j_{2},0} > a_{c,0}. As the initial numbers are distinct, we conclude ai,k=ac,0a_{i,k} = a_{c,0} if and only if {ik,ik+1,,i+k}\{i - k, i - k + 1, \ldots, i + k\} contains cc but neither cj1c - j_{1} nor c+j2c + j_{2} (mod 2025). The indices ii that satisfy this are clearly consecutive.

Now consider the indicator variables

1i={1if ai,kai+1,k0otherwise \mathbf{1}_{i} = \left\{ \begin{array}{ll}1 & \mathrm{if~}a_{i,k}\neq a_{i + 1,k}\\ 0 & \mathrm{otherwise} \end{array} \right.

for 1i20251\leq i\leq 2025. Note that the number of distinct values on the board after kk seconds is simply i=120251i\textstyle \sum_{i = 1}^{2025}\mathbf{1}_{i}. By linearity of expectation, it suffices to compute E[1i]\mathbb{E}[\mathbf{1}_{i}] for each ii. Recall

ai,k=max(aik,0,,ai+k,0) a_{i,k} = \max (a_{i - k,0},\ldots,a_{i + k,0})

for each 1i20251\leq i\leq 2025. Hence, the condition ai,kai+1,ka_{i,k}\neq a_{i + 1,k} can be written as

max(aik,0,,ai+k,0)max(ai+1k,0,,ai+1+k,0). \max (a_{i - k,0},\ldots ,a_{i + k,0})\neq \max (a_{i + 1 - k,0},\ldots ,a_{i + 1 + k,0}).

This is the case if and only if max(aik,0,,ai+k+1,0)\max (a_{i - k,0},\ldots ,a_{i + k + 1,0}) is either aik,0a_{i - k,0} or ai+k+1,0a_{i + k + 1,0} (as aik,0ai+k+1,0a_{i - k,0}\neq a_{i + k + 1,0} and 2k+2<20252k + 2< 2025). Since the 2k+22k + 2 values aik,0a_{i - k,0}, ..., ai+k+1,0a_{i + k + 1,0} were sampled independently from the same distribution, each of aik,0a_{i - k,0} and ai+k+1,0a_{i + k + 1,0} has a 12k+2\frac{1}{2k + 2} probability of being their maximum. Hence,

E[1i]=Pr[ai,kai+1,k]=22k+2=1k+1. \mathbb{E}[\mathbf{1}_{i}] = \operatorname*{Pr}[a_{i,k}\neq a_{i + 1,k}] = \frac{2}{2k + 2} = \frac{1}{k + 1}.

Thus, the expected number of distinct values is

i=12025E[1i]=2025k+1. \sum_{i = 1}^{2025}\mathbb{E}[\mathbf{1}_{i}] = \frac{2025}{k + 1}.

Substituting k=100k = 100 yields the answer [2025101]\left[\frac{2025}{101}\right]

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.