Maths Olympiad Prep

Library / /822 of 860

Algebra Difficulty 5.6 AIME, harder Find the answer

Let f:NNf: \mathbb{N} \rightarrow \mathbb{N} be a function satisfying the following conditions: (a) f(1)=1f(1)=1 (b) f(a)f(b)f(a) \leq f(b) whenever aa and bb are positive integers with aba \leq b. (c) f(2a)=f(a)+1f(2a)=f(a)+1 for all positive integers aa. How many possible values can the 2014-tuple (f(1),f(2),,f(2014))(f(1), f(2), \ldots, f(2014)) take?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Note that f(2014)=f(1007)+1f(2014)=f(1007)+1, so there must be exactly one index 1008i20141008 \leq i \leq 2014 such that f(i)=f(i1)+1f(i)=f(i-1)+1, and for all 1008j2014,ji1008 \leq j \leq 2014, j \neq i we must have f(j)=f(j1)f(j)=f(j-1). We first claim that each value of ii corresponds to exactly one 2014-tuple (f(1),,f(2014))(f(1), \ldots, f(2014)). To prove this, note that f(1024)=11f(1024)=11, so each ii uniquely determines the values of f(1007),,f(2014)f(1007), \ldots, f(2014). Then all of f(1),,f(1006)f(1), \ldots, f(1006) can be uniquely determined from these values because for any 1k10061 \leq k \leq 1006, there exists a unique nn such that 1007k2n20141007 \leq k \cdot 2^{n} \leq 2014. It's also clear that these values satisfy the condition that ff is nondecreasing, so we have a correspondence from each 1008i20141008 \leq i \leq 2014 to a unique 2014-tuple. Also, given any valid 2014-tuple (f(1),,f(2014)(f(1), \ldots, f(2014), we know that f(1),,f(1006)f(1), \ldots, f(1006) can be uniquely determined by f(1007),,f(2014)f(1007), \ldots, f(2014), which yields some 1008i20141008 \leq i \leq 2014 where f(i)=f(i1)+1f(i)=f(i-1)+1, so we actually have a bijection between possible values of ii and 2014-tuples. Therefore, the total number of possible 2014-tuples is 1007.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.