A sequence of natural numbers $c_1, c_2,\dots$ is called perfect if every natural number $m$ with $1\le m \le c_1 +\dots+ c_n$ can be represented as $m =\frac{c_1}{a_1}+\frac{c_2}{a_2}+\dots+\frac{c_n}{a_n}$ Given $n$, find the maximum possible value of $c_n$ in a perfect sequence $(c_i)$.
Problem
Source: 17-th Iranian Mathematical Olympiad 1999/2000
Tags: induction, number theory proposed, number theory
06.01.2009 21:32
let $ C_1 = 2$ and $ C_i = 4\times 3^{i - 2}$ for $ i\geq 2$.we claim that for each $ i$,$ C_i$ is the maximum possible value of $ c_i$. we first prove by induction on $ i\geq 1$ that $ c_i\leq C_i$.for $ i = 1$,if $ c_i > 1$,then setting $ (m,n) = (c_1 - 1,1)$ shows that $ a_1 = \frac {c_1}{c_1 - 1}$ is an integer.this happens exactly when $ c_1 = 2$.thus $ c_1\leq C_1$. now suppose that $ c_i\leq C_i$ for $ i = 1,2,\ldots ,k - 1$,where $ k\geq 2$.we find the $ a_i$ corresponding to $ (m,n) = (c_k,k)$.clearly $ a_n\geq 2$.then: $ c_n = \sum_{i = 1}^n\frac {c_i}{a_i}\leq\frac {c_n}2 + \sum_{i = 1}^{n - 1}C_i$ or $ c_n\leq 2\sum_{i = 1}^{n - 1}C_i = C_n$.this completes the inductive step and the proof of the claim. it remains to be proven that for each $ i$,it is possible to have $ c_i = C_i$.indeed,we prove by induction on $ n$ that we can have $ c_i = C_i$ for all $ i$ simultaneously.for $ n = 1$,if $ m = 1$ we can set $ a_1 = 2$;if $ m = 2$ we can set $ a_1 = 1$. assuming that the claim is true for $ n = 1,2,\ldots ,k - 1$,where $ k\geq 2$,we prove it for $ n = k$.if $ m = 1$,we may set $ a_i = nC_i$ for $ i = 1,2,\ldots ,n$.if $ 2\leq m\leq \frac {C_n}2 + 1$,set $ a_n = C_n$;if $ \frac {C_n}2 + 1\leq m\leq C_n$,set $ a_n = 2$;if $ C_n + 1\leq m\leq\frac {3C_n}2 = \sum_{i = 1}^n C_i$ set $ a_n = 1$.in each case,$ 1\leq m - \frac {C_n}{a_n}\leq\frac {C_n}2$.thus by the induction hypothesis,we may choose positive integers $ a_1,a_2,\ldots ,a_{n - 1}$ such that $ m - \frac {C_n}{a_n} = \sum_{i = 1}^{n - 1}\frac {C_n}{a_n}$ as desired.this completes the proof.
29.08.2021 20:26
there is latex error in this post can you fix it please