Math Help -> Puzzles -> Increasing integer function -> Answer 

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).

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 --