Maths Olympiad Prep

Library / /9 of 16

Algebra Difficulty 6.0 AIME, harder Prove it Bulgaria

Problem:
Let nn be a positive integer. Find the number of all finite strictly increasing sequences a0=1,a1,,ak=2.3na_{0}=1, a_{1}, \ldots, a_{k}=2.3^{n} of positive integers with the following property: i=1k[ai+ai11ai1]=2.3n\prod_{i=1}^{k}\left[\frac{a_{i}+a_{i-1}-1}{a_{i-1}}\right]=2.3^{n}, where [x][x] is the integral part of xx.

Solution

Solution:
Let mm and nn be positive integers and n=mq+r,0r<mn=m q+r, 0 \leq r<m. Then [n+m1m]=q+1+[r1m]\left[\frac{n+m-1}{m}\right]=q+1+\left[\frac{r-1}{m}\right] and nm=q+rm\frac{n}{m}=q+\frac{r}{m}. Hence [n+m1m]nm\left[\frac{n+m-1}{m}\right] \geq \frac{n}{m} with equality if and only if mm divides nn.

Applying the above inequality we obtain
2.3n=i=1k[ai+ai11ai1]i=1kaiai1=aka0=2.3n 2.3^{n}=\prod_{i=1}^{k}\left[\frac{a_{i}+a_{i-1}-1}{a_{i-1}}\right] \geq \prod_{i=1}^{k} \frac{a_{i}}{a_{i-1}}=\frac{a_{k}}{a_{0}}=2.3^{n}
Therefore ai1a_{i-1} divides aia_{i} for i=1,2,,ki=1,2, \ldots, k. We have to find the number of the sequences 1=a0<a1<<ak=2.3n1=a_{0}<a_{1}<\cdots<a_{k}=2.3^{n} such that ai1a_{i-1} divides aia_{i} for i=1,2,,ki=1,2, \ldots, k. Starting by an arbitrary sequence we construct a sequence of kk symbols \star, nn digits 3 and one digit 2 in the following way: if ai+1ai=2p3q\frac{a_{i+1}}{a_{i}}=2^{p} 3^{q}, i=1,2,,k1i=1,2, \ldots, k-1 then we put pp digits 2 and qq digits 3 between \star number ii and \star number i+1i+1. Since ai<ai+1a_{i}<a_{i+1} there are no two consecutive symbols \star.

It is clear that any sequence of kk symbols \star, nn digits 3 and one digit 2 with no two consecutive symbols \star corresponds to a sequence 1=a0<a1<<ak=2.3n1=a_{0}<a_{1}<\cdots<a_{k}=2.3^{n}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.