For positive integers $ n,$ the numbers $ f(n)$ are defined inductively as follows: $ f(1) = 1,$ and for every positive integer $ n,$ $ f(n+1)$ is the greatest integer $ m$ such that there is an arithmetic progression of positive integers $ a_1 < a_2 < \ldots < a_m = n$ for which \[ f(a_1) = f(a_2) = \ldots = f(a_m).\] Prove that there are positive integers $ a$ and $ b$ such that $ f(an+b) = n+2$ for every positive integer $ n.$
Problem
Source: IMO Shortlist 1995, S5
Tags: arithmetic sequence, algebra, recurrence relation, function, IMO Shortlist
BaBaK Ghalebi
10.09.2008 22:53
" wrote: we claim that: $ f(4k + 3) = 2$. $ f(4k) = k$ , $ (k\neq 2)$,and $ f(8) = 3$. $ f(4k + 1) = 1$ , $ (k\neq 1,3)$,and $ f(5) = f(13) = 2$. $ f(4k + 2) = k - 3$ , $ (k\neq 0,1,2,3,4,6)$,and $ f(2) = 1,f(6) = f(10) = 2,f(14) = f(18) = 3,f(26) = 4$. we will prove our claims using induction on $ n$.it's easy to compute the values of $ f$ for $ n\leq 31$,so let $ n>31$: if $ n = 4k$ ($ k\geq 8$) then $ f(3) = f(7) = \ldots = f(4k - 1) = 2$ hence $ f(4k)\geq k$,on the other hand we have $ f(n)\leq\max\{f(m): m < n\} + 1$,thus $ f(4k) = k$. now if $ n = 4k + 2$ ($ k > 7$),we have $ f(17) = f(21) = \ldots = f(4k + 1) = 1$ hence $ f(4k + 2)\geq k - 3$.on the other hand if we denote $ d$ as the common difference of the progression and $ d\neq 4$ then obviously $ d\geq 8$,hence the length of the progression would be less than or equal to $ \frac {4k + 1}8$ which with the assumption $ k > 7$ yields us $ k - 3 > \frac {4k + 1}8$ hence $ f(4k + 2) = k - 3$. also for $ n = 4k + 1$,because of $ k\geq 7$,for every $ m < 4k$ we have $ f(m) < k$,hence $ f(4k + 1) = 1$. last but not least,for $ n = 4k + 3$,note that because of $ k\geq 8$ and $ f(4k + 2) = k - 3$,also for every $ k\geq 8$,there exists one and only one $ m < 4k + 2$ for which $ f(m) = k - 3$,hence $ f(4k + 3) = 2$. now according to the proved claims we can see that $ f(4n + 8) = n + 2$,thus $ a = 4,b = 8$. QED