bonanova Posted February 24, 2015 Report Share Posted February 24, 2015 There is a function f (n) on the positive integers n = 1, 2, 3, ... It is defined solely by these properties: f (n) is itself a positive integer f is strictly increasing: f (n+1) > f (n) applying f twice returns the argument multiplied by 3: f ( f (n) ) = 3n Work out the values of f for the first 30 integers or so: f (1), f (2), f (3), … , f (30). Start, of course, with 1 and 2. When you see some patterns, find f (2015). Credit: Recent Math Olympiad. Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted February 24, 2015 Report Share Posted February 24, 2015 ƒ(2015) = 3858 Quote Link to comment Share on other sites More sharing options...

0 gavinksong Posted February 24, 2015 Report Share Posted February 24, 2015 ƒ(1) = 2 ƒ(2) = 3 ƒ(3) = 6 ƒ(4) = 7 ƒ(5) = 8 ƒ(6) = 9 ƒ(7) = 12 ƒ(8) = 15 ƒ(9) = 18 ƒ(10) = 19 ƒ(11) = 20 ƒ(12) = 21 ƒ(13) = 22 ƒ(14) = 23 ƒ(15) = 24 ƒ(16) = 25 ƒ(17) = 26 ƒ(18) = 27 ƒ(19) = 30 ƒ(20) = 33 ƒ(21) = 36 ƒ(22) = 39 ƒ(23) = 42 ƒ(24) = 45 ƒ(25) = 48 ƒ(26) = 51 ƒ(27) = 54 ƒ(28) = 55 ƒ(29) = 56 ƒ(30) = 57 Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted February 24, 2015 Author Report Share Posted February 24, 2015 Great job. 1 Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted February 24, 2015 Author Report Share Posted February 24, 2015 Solution: f (1) = 1? Can't be, since f (1) = f ( f (1) ) = 1, but it must be 3. f (1) = 2? Could be, since f (2) would then be f ( f (1) ) = 3. Must be. If f (1) were 3, then f (3) would also be 3. Non-increasing. Continue to use f ( f (n) ) = 3n: f (1) = 2 f (2) = 3 f (3) = 6 = f ( f (2) ) f (4) = f (5) = f (6) = 9 = f ( f (3) ) f (7) = f (8) = f (9) = 18 = f ( f (6) ) f (10) = We can fill in 4 and 5 because there are exactly two positive integers in the interval n = (3, 6), and exactly two other positive integers between f = (6, 9). Values for n = 7 and 8 are then found using f ( f (n) ) = 3n: f (1) = 2 f (2) = 3 f (3) = 6 = f ( f (2) ) f (4) = 7 f (5) = 8 f (6) = 9 = f ( f (3) ) f (7) = 12 = f ( f (4) ) f (8) = 15 = f ( f (5) ) f (9) = 18 = f ( f (6) ) f (10) = Looking ahead to n = 12 we will have f = 21. That constrains n = 10 and 11 to give f = 19 and 20. Proceeding in this manner we obtain f (1) = 2 f (2) = 3 = f ( f (1) ) f (3) = 6 = f ( f (2) ) f (4) = 7 f (5) = 8 f (6) = 9 = f ( f (3) ) f (7) = 12 = f ( f (4) ) f (8) = 15 = f ( f (5) ) f (9) = 18 = f ( f (6) ) f (10) = 19 f (11) = 20 f (12) = 21 = f ( f (7) ) f (13) = 22 f (14) = 23 f (15) = 24 = f ( f (8) ) f (16) = 25 f (17) = 26 f (18) = 27 = f ( f (9) ) f (19) = 30 = f ( f (10) ) f (20) = 33 = f ( f (11) ) f (21) = 36 = f ( f (12) ) f (22) = 39 = f ( f (13) ) f (23) = 42 = f ( f (14) ) f (24) = 45 = f ( f (15) ) f (25) = 48 = f ( f (16) ) f (26) = 51 = f ( f (17) ) f (27) = 54 = f ( f (18) ) f (28) = 55 f (29) = 56 f (30) = 57 = f ( f (19) ) We notice that when n is a power of 3, {1, 3, 9, 27, …} f doubles it: f (3^{p}) = 2x3^{p}. e.g., f (27) = 54 We also notice than when n is twice a power of 3, {2, 6, 18, …} f returns the next higher power of 3: f (2x3^{p}) = 3^{p+1}. e.g. f (2x9) = 27 To show that these relations hold for all p, we note first that they hold for p = 0 and 1 in the table. The inductive step is completed by noting that f (3^{p+1}) = f ( f (2x3^{p}) ) = 2x3^{p+1} f (2x3^{p+1}) = f ( f ( 3^{p+1}) ) = 3^{p+2} Now the intervening numbers (black numbers in the table) need to be accounted for. There are 3^{p} - 1 integers q in the interval q = (3^{p}, 2x3^{p}) and there are 3^{p} - 1 integers g in the interval g = (f (3^{p}) = 2x3^{p}, 3^{p}+1 = f(2x3^{p})). So there are always just enough numbers to go around. Thus, for q in [0, 3^{p}], f (3^{p} + q) = 2x3^{p} + q and f (2x3^{p} + q) = f ( f (3^{p} + q) ) = 3x(3^{p} + q). Since 3^{6} = 729, we find that 2015 = 2x3^{6} + 557. Thus f (2015) = 3x(3^{6} + 557) = 3,858. 1 Quote Link to comment Share on other sites More sharing options...

## Question

## bonanova

There is a function

f(n) on the positive integers n = 1, 2, 3, ...It is defined solely by these properties:

f(n) is itself a positive integerfis strictly increasing:f(n+1) >f(n)ftwice returns the argument multiplied by 3:f(f(n) ) = 3nWork out the values of f for the first 30 integers or so:

f(1),f(2),f(3), … ,f(30).Start, of course, with 1 and 2.

When you see some patterns, find

f(2015).Credit: Recent Math Olympiad.## Link to comment

## Share on other sites

## 4 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.