XLVI OM - III - Problem 5

Let $ n $ and $ k $ be natural numbers. From an urn containing 11 slips numbered from 1 to $ n $, we draw slips one by one, without replacement. When a slip with a number divisible by $ k $ appears, we stop drawing. For a fixed $ n $, determine those numbers $ k \leq n $ for which the expected value of the number of slips drawn is exactly $ k $.
Let's establish a natural number $ k \in \{1,2,\ldots,n\} $. Consider the following events:






Let's denote the probabilities of these events: $ p_j = P(\mathcal{A}_j) $, $ q_j = P(\mathcal{B}_j) $. Of course, $ \mathcal{B}_0 $ is a certain event. Therefore, $ q_0 = 1 $.
The occurrence of event $ \mathcal{A}_j $ is equivalent to drawing $ j $ tickets, after which the drawing is stopped - that is, the random variable $ X $ (the number of tickets drawn) takes the value $ j $. Thus,






The occurrence of event $ \mathcal{A}_j $ is also equivalent to the fact that a number divisible by $ k $ did not appear in the first $ j-1 $ draws, but did appear in the first $ j $ draws - that is, event $ \mathcal{B}_{j-1} $ occurred, but event $ \mathcal{B}_j $ did not. In other words, event $ \mathcal{A}_j $ is equal to the difference between events $ \mathcal{B}_{j-1} $ and $ \mathcal{B}_j $ (considered as subsets of the appropriate probability space). Therefore,






(we use the fact that $ \mathcal{B}_j \subset \mathcal{B}_{j-1} $).
The expected value of the random variable $ X $ is equal to






In the set $ \{1,2,\ldots,n\} $, there are $ m $ numbers divisible by $ k $ and $ l $ numbers not divisible by $ k $, where



(symbol $ [t] $ denotes, as usual, the greatest integer not exceeding $ t $). If $ j > l $, then in one of the first $ j $ draws, a number divisible by $ k $ must have appeared, which means that $ \mathcal{B}_j $ is an impossible event. Therefore, $ q_j = 0 $ for $ j > l $, and thus,






From the conditions of the problem, it follows that for $ j \leq l $, the probabilities $ q_j $ are given by the formula



Indeed: in the first draw, we draw a number not divisible by $ k $ with probability $ l/n $; there remain $ n-1 $ tickets in the urn, of which $ l-1 $ are tickets with numbers not divisible by $ k $; in the second draw, we draw a number not divisible by $ k $ with probability $ (l-1)/(n-1) $; and so on. Drawing numbers not divisible by $ k $ in $ j $ consecutive draws occurs with the probability equal to the product written on the right side of formula (2).
We transform this product as follows:






(because $ l + m = n $). After substituting these expressions, equality (1) takes the form



(we applied a change of the summation index: $ s = n-j $). The last sum can be simplified in a known way:




(see the solution to problem 11 from the first round of this olympiad: formula (2) and the Remark on page 51). Hence,



In the problem, we need to determine the conditions under which the value $ E(X) $ is exactly equal to $ k $ - that is, under which the equality



holds.
If relation (3) holds, then obviously $ k $ is a divisor of the number $ n + 1 $. Conversely, if $ n+1 $ is divisible by $ k $, then from the inequality



(whose extreme members are integers) we infer that



which means that equality (3) holds.
Therefore, the answer is: the sought values of $ k $ are all divisors of the number $ n + 1 $ belonging to the set $ \{1,2,\ldots,n\} $.