Maths Olympiad Prep

Library / /22 of 69

Combinatorics Difficulty 5.7 AIME, harder Prove it Mongolia

All numbers of the form 2k3s2^{k}3^{s} (k,sk, s are non-negative whole numbers) were written in increasing order 1,2,3,4,6,8,9,12,1, 2, 3, 4, 6, 8, 9, 12, \ldots and formed the sequence ana_n. Prove that there are infinitely many numbers nn satisfying the condition
an+1an<1+1102014 \frac{a_{n+1}}{a_n} < 1 + \frac{1}{10^{2014}}

Solution

From the Euler number's definition (1+1102014)102014>2(1 + \frac{1}{10^{2014}})^{10^{2014}} > 2.

For any nonnegative whole number nn, there exists nonnegative mm such that 2m3n2m+12^m \le 3^n \le 2^{m+1}. Different n1,n2n_1, n_2 correspond to different m1,m2m_1, m_2. Note that 2m3n2m+113n2m22^m \le 3^n \le 2^{m+1} \Leftrightarrow 1 \le \frac{3^n}{2^m} \le 2. There exist infinitely many different numbers 3n2m\frac{3^n}{2^m} that lie in the segment [1;2][1; 2].

Divide the segment [1;2][1; 2] into small segments [(1+1102014)k;(1+1102014)k+1][(1 + \frac{1}{10^{2014}})^k; (1 + \frac{1}{10^{2014}})^{k+1}], k=0,1,,102014k = 0, 1, \ldots, 10^{2014}. Since there are infinitely many numbers of the form 3n2m\frac{3^n}{2^m}, by the pigeonhole principle there is a segment inside in which lie two different numbers 3n12m1,3n22m2\frac{3^{n_1}}{2^{m_1}}, \frac{3^{n_2}}{2^{m_2}}. Let us denote this segment by ss. In other words,
(1+1102014)s3n12m1<3n22m2(1+1102014)s+1. \left(1 + \frac{1}{10^{2014}}\right)^s \le \frac{3^{n_1}}{2^{m_1}} < \frac{3^{n_2}}{2^{m_2}} \le \left(1 + \frac{1}{10^{2014}}\right)^{s+1}.
From this it follows that 1<3n22m2:3n12m11+11020141 < \frac{3^{n_2}}{2^{m_2}} : \frac{3^{n_1}}{2^{m_1}} \le 1 + \frac{1}{10^{2014}} and 1<3n22m12m23n1<1+11020141 < \frac{3^{n_2} 2^{m_1}}{2^{m_2} 3^{n_1}} < 1 + \frac{1}{10^{2014}}.

Setting an+q=3n22m1a_{n+q} = 3^{n_2} 2^{m_1}, an=3n12m2a_n = 3^{n_1} 2^{m_2} we get 1+1102014>an+qanan+1an1 + \frac{1}{10^{2014}} > \frac{a_{n+q}}{a_n} \ge \frac{a_{n+1}}{a_n}.

Continuing in this manner from the fraction an+1an\frac{a_{n+1}}{a_n} it is possible to construct a new fraction less than 1+110k1 + \frac{1}{10^k} for any natural kk.

Note. limnan+1an=1\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = 1.

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.