Question 141
Let $S$ be a set of intervals defined recursively as follows:
- Initially, $[1,1000]$ is the only interval in $S$.
- If $l \neq r$ and $[l, r] \in S$, then both $\left[l,\left\lfloor\frac{l+r}{2}\right\rfloor\right],\left[\left\lfloor\frac{l+r}{2}\right\rfloor+1, r\right] \in S$.
(Note that $S$ can contain intervals such as $[1, 1]$, which contain a single integer.) An integer $i$ is chosen uniformly at random from the range $[1,1000]$. What is the expected number of intervals in $S$ which contain $i$ ?
- Initially, $[1,1000]$ is the only interval in $S$.
- If $l \neq r$ and $[l, r] \in S$, then both $\left[l,\left\lfloor\frac{l+r}{2}\right\rfloor\right],\left[\left\lfloor\frac{l+r}{2}\right\rfloor+1, r\right] \in S$.
(Note that $S$ can contain intervals such as $[1, 1]$, which contain a single integer.) An integer $i$ is chosen uniformly at random from the range $[1,1000]$. What is the expected number of intervals in $S$ which contain $i$ ?