# Increasing Integer Function Puzzle

### Statement of the Puzzle

 Let f map positive integers to positive integers with the conditions: i) f(n+1) > f(n) ii) f(f(n)) = 3n Find f(955). Source: http://mathforum.org/wagon/spring02/p955.html, which cites EMISSARY, the MSRI Newsletter, Fall 2001.

### Solution

 If f(1)=1 then f(f(1))=1 but f(f(1))=3, so f(1) isn't equal to 1 If f(1)>2 then f(2)>3, so f(f(1))>3, but f(f(1))=3, so f(1) isn't greater than 2 Thus f(1)=2, and f(2)=3 f(3)=f(f(2))=6, and f(6)=f(f(3))=9, so 9 > f(5) > f(4) > 6, so f(5)=8 and f(4)=7. Now we have established the following: f(1)=2 f(2)=3 f(3)=6 f(4)=7 f(5)=8 f(6)=9 I'm going to stop now, and start over in base 3. f(1)=2 f(2)=10 f(10)=20 f(11)=21 f(12)=22 f(20)=100 There's a pattern here, which is: If the first base-3 digit of x is "1" then f(x) is x with the first "1" replaced with "2". If the first base-3 digit of x is "2" then f(x) is x with the first "2" replaced with a "1", and a "0" appended to the end of it. This function meets the conditions, because f(x+1)>f(x) and f(f(x)) replaces the first digit of x with a different digit, then replaces the result with the original digit, and a zero is appended to the end of it in one of those two transformations.  In short, f(f(x))=3x. But is this the only function that meets the conditions? It's the only function f(x) that meets the conditions when x is a 1-digit number; we've shown that. Let's assume it's the only function f(x) that meets the conditions when x is an n digit base three number, and use induction to show it's the only function that meets the conditions when x is an n+1 digit base three number. If x is an n-digit base three number of the form 1ddd then f(x)=2ddd, and f(2ddd)=1ddd0, so f(1ddd0)=2ddd0 So f(x) is the only function that meets the conditions when x is an n+1 digit multiple of 3 that begins with "1". If x is an n+1 digit multiple of 3 beginning with "1", then f(x+3)=f(x)+3. (That's true even if x+3 begins with "2" -- f(12220+3) = f(20000) = f(f(10000)) = 100000 = 22220+3 = f(12220)+3) So in order for f(x)+3 = f(x+3) > f(x+2) > f(x+1) > f(x) it must be the case that f(x+2)=f(x)+2, and f(x+1)=f(x)+1 So for all n+1 digit numbers beginning with 1, f(1dddd)=2dddd. Now, let's look at the n+1 digit numbers beginning with 2. If x is of the form 2dddd then f(1dddd)=2dddd, so f(2dddd)=1dddd0, proving that f(x) is the only function that meets the conditions when x is an n+1 digit base three number. Now, to answer the question at hand -- 955 base 10 = 1022101 base 3, and 1684 base 10 = 2022101 base 3, so f(955)=1684

### Related pages in this website

The webmaster and author of this Math Help site is Graeme McRae.