Maths Olympiad Prep

Library / /8 of 13

Combinatorics Difficulty 4.9 AIME Prove it China

Let Mn={0,a1a2anai=0 or 1,1in1,an=1}M_n = \{0, a_1a_2\cdots a_n \mid a_i = 0 \text{ or } 1, 1 \le i \le n-1, a_n = 1\} be a set of decimal fractions, TnT_n and SnS_n be the number and the sum of the elements in MnM_n respectively. Then
limnSnTn=. \lim_{n \to \infty} \frac{S_n}{T_n} = \underline{\hspace{2cm}}.

Solution

Since a1,a2,,an1a_1, a_2, \dots, a_{n-1} all have exactly two possible values, so Tn=2n1T_n = 2^{n-1}. Meanwhile, the frequency of ai=1a_i = 1 is the same as that of ai=0a_i = 0 for 1in11 \le i \le n-1, and an=1a_n = 1. Then
Sn=12×2n1×(110+1102++110n1)+2n1×110n=2n1×118×(1110n1)+2n1×110n. \begin{aligned} S_n &= \frac{1}{2} \times 2^{n-1} \times \left( \frac{1}{10} + \frac{1}{10^2} + \dots + \frac{1}{10^{n-1}} \right) + 2^{n-1} \times \frac{1}{10^n} \\ &= 2^{n-1} \times \frac{1}{18} \times \left( 1 - \frac{1}{10^{n-1}} \right) + 2^{n-1} \times \frac{1}{10^n}. \end{aligned}

So
limnSnTn=limn[118(1110n1)+110n]=118. \lim_{n \to \infty} \frac{S_n}{T_n} = \lim_{n \to \infty} \left[ \frac{1}{18} \left( 1 - \frac{1}{10^{n-1}} \right) + \frac{1}{10^n} \right] = \frac{1}{18}.

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 and solution reproduced as published; topic and difficulty added by this site.