IMO Shortlist 1997 problem 24
Kvaliteta:
Avg: 0,0Težina:
Avg: 0,0 For each positive integer
, let
denote the number of ways of representing
as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance,
, because the number 4 can be represented in the following four ways: 4; 2+2; 2+1+1; 1+1+1+1.
Prove that, for any integer
we have
.
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![f(n)](/media/m/d/3/e/d3e47283bffbbf24c97f0c6474d5a82d.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![f(4) = 4](/media/m/1/d/d/1ddf2f667cf760000f093db09bd7b25b.png)
Prove that, for any integer
![n \geq 3](/media/m/5/4/8/54807b3bf99aa939833fe57bf8d891d3.png)
![2^{\frac {n^2}{4}} < f(2^n) < 2^{\frac {n^2}2}](/media/m/6/7/8/678a337d845e47e29bb37535ba17d2e4.png)
Izvor: Međunarodna matematička olimpijada, shortlist 1997