Let be a function satisfying the following conditions: (a) (b) whenever and are positive integers with . (c) for all positive integers . How many possible values can the 2014-tuple take?
Solution
Note that , so there must be exactly one index such that , and for all we must have . We first claim that each value of corresponds to exactly one 2014-tuple . To prove this, note that , so each uniquely determines the values of . Then all of can be uniquely determined from these values because for any , there exists a unique such that . It's also clear that these values satisfy the condition that is nondecreasing, so we have a correspondence from each to a unique 2014-tuple. Also, given any valid 2014-tuple , we know that can be uniquely determined by , which yields some where , so we actually have a bijection between possible values of 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.