MathDB

5

Part of 1980 Poland - Second Round

Problems(1)

print the terms of the sequence

Source: Polish MO Recond Round 1980 p5

9/9/2024
We print the terms of the sequence (n1,n2,…,nk) (n_1, n_2, \ldots, n_k) , where n1=1000 n_1 = 1000 , and nj n_j for j>1 j > 1 is an integer selected randomly from the range [0,nj−1−1] [0, n_{j-1 } - 1] (each number in this range is equally likely to be selected). We stop printing when the selected number is zero, i.e. nk−1 n_{k-1} , nk=0 n_k = 0 , The length k k of the sequence (n1,n2,…,nk) (n_1, n_2, \ldots, n_k) is a random variable. Prove that the expected value of this random variable is greater than 7.
number theorycombinatorics