## f(2014)

Posted by Zorglub on July 16, 2014 – 7:49 am

f is a function that maps a positive integer to a positive integer, and satisfy the properties f(n+1) > f(n) and f(f(n)) = 3n for every integer n.

a) what is f(2014) ?

b) Is f uniquely defined ? If so, what is its expression ?

July 16th, 2014 at 2:18 pm

Hi Zorglub. A BMO question. I had a go with this but for f(1995), I think. I never cracked it. But it was masochistic fun.

July 16th, 2014 at 2:35 pm

Yes Chris, it is a BMO question, but I updated the 1995 for 2014.

Once that you see the solution, you will realize that it is beautifully simple, with a spectacular use of the pigeonhole principle.

July 17th, 2014 at 4:34 am

Looking at the question – Define f(n) such that f(n) is a positive integer, f(n+1) > f(n) and f(f(n)) = 3n .

Thus, starting at the beginning: f(f(1))=3⟹f(1)=2 This gives me f(2)=3

f(f(2))=3×2=6⟹f(3)=6

f(f(3))=3×3=9⟹f(6)=9

Since we have

6=f(3)

And I have to get to f(2014) and I am already losing it/confusing myself?

July 17th, 2014 at 6:54 am

Good start, Karl I suggest you continue to f(27) and most probably you’ll find the pattern (at least this is what I did). f(2014) = 3855, the function is unique, but I won’t give its explicit formula until everybody gives up

July 17th, 2014 at 7:03 am

Yes Karl, you have the first step to compute f(1), f(2) and f(3). This gives you enough information to compute f(n) for some specific values of n.

Afterward, its a 2-sentence proof.

Slavy, I agree with f(2014) = 3855. I am looking forward to see your approach, but let the others suffer a bit longer.

July 17th, 2014 at 7:09 am

Zorglub, I believe my approach is the same as yours, judging from the hints you gave to Karl and Chris

July 17th, 2014 at 10:46 am

I had started to write something, I felt I could write something for f(n) with the info I had deduced, but the bell rang, and I had to go and train the monkeys some more… Once I have relaxed with a botlle of wine or two, I shall re-address the problem, if I can decipher my original scrawls!

July 18th, 2014 at 12:53 am

Carrying on from where I left off, since f(3) and f(6) differ by 3, the only possibility is f(4) = 7 and f(5) = 8. This determines:

f(7) = 12

f(8) = 15

f(12) = 21

f(15) = 24

We’ll note similarly that f(9), f(12), f(15) and f(18) have steps of 3, so for or all positive integer n, f(3n) = 3f(n).

Next legible bits of text I have on my notes is this formula f(n) = n + r for 3a ≤ n ≤ 3b. But by now the wine was getting to me, but I think it might be cracked – there is a pattern emerging! To whit – 3^n to 2*3^n…

And that is as far as I have gone…

July 18th, 2014 at 1:35 am

Hi Karl. I’ve not cracked it yet, but I have the following useful formulae.

f(f(f(a))) = f(3a) = 3f(a). So f(3^n a) = 3^n f(a), by recursive application of the previous.

I easily generated all f(a) for a = 1 to 39. The pigeonhole principle is needed several times. In fact for f(28) to f(35), we use that f(27) = 27 f(1) = 54 and f(36) = f(3^2 4) = 9 f(4) = 9*7 = 63 and then the pigeonhole principle gives f(28) to f(35) = 55 to 62. Some of those could have been found using other intermediate results.

I only stopped at f(39) due to boredom.

The only thing I have noticed (so far) is that f(a+1) – f(a) = 1 or 3. But I haven’t proven it to be generally true.

July 18th, 2014 at 2:49 am

2013 = 3*671 and 2016 = 3^2 224. So f(2013) = 3 f(671) and

f(2016) = 9 f(224). If they differ by 3, then we’re done (and the answer is unique).

Proof that f(1) = 2. NB f(1) ≥ 1, trivially by the problem definition. It readily follows that f(n) ≥ n.

Try f(1) = 1. Then 3 = f(f(1)) = f(1) = 1, so obviously not true and so f(1) > 1.

We immediately have that f(n) > n for all n.

Try f(1) = n. Then f(f(1)) = 3 = f(n). But f(n) > n so n = 1 or 2, and as 1 has already been disallowed, we must have f(1) = 2.

Now f(f(1)) = f(2) = 3. f(3) = f(f(2)) = 3*2 = 6, etc…

We can also calculate f(3) from f(3n) = 3f(n), i.e. f(3) = 3 f(1) = 6.

July 18th, 2014 at 3:20 am

Chris is correct in what he’s writing, but it seems Karl is getting closer – he already mentioned the 2 key sequences of n’s now he simply needs to find out how to properly use them…

July 18th, 2014 at 7:09 am

I finally realised that all those powers of 3 suggested looking at the numbers in base 3.

~~I’ve cracked the main part, but I have no idea how to prove any of it or if it is even just a coincidence that the following seems to work.~~~~The only confirmation I have is that after looking at about twenty examples, the pattern is there and most importantly it gives f(2014) = 3855.~~The following is in base 3. It’s the first 10 values of the sequence.

f(1) =2, f(2) =10, f(10) =20, f(11) =21, f(12) = 22, f(20) = 100,

f(21) = 110, f(22) =120, f(100) =200, f(101) =201

I also checked a few randomly chosen larger numbers and can see that e.g.

f(3^4) = 2*3^4 => f(10000) = 20000 and

f(2*3^4) = 3^5 => f(20000) = 100000

Without fail, f(1dd..dd) = 2dd..dd and f(2dd..dd) = 1dd..dd0, i.e. the function simply replaces the leading 1 with a 2 and 2 with a 1 and adds a 0 the the other end. (the d’s aren’t affected).

So, immediately we can do the calculation ([3] and [10] denote the base used:

2014 [10] = 2202121 [3] so f(2202121 [3]) = 12021210 [3] = 3855 [10].

——

After writing the above I realised that if the above is right then using f(f(n)) = 3f(n)

=> f(f(1dd..dd)) = f(2dd..dd) = 1dd..dd0 and f(f(2dd..dd)) = f(1dd..dd0) = 2dd..dd0, as required. I think that’s a proof, ‘cept my head is in such a mess now, I’m not sure, but I don’t think it’s a [fallacious] circular argument.

I never expected a solution like that. I used quite a big pile of paper getting there. Thanks for posting this one Zorglub. I had considered posting it myself (a few months ago). But decided not to as I couldn’t make any useful headway with it. I now suspect that you are also a mathematician.

July 18th, 2014 at 7:49 am

Good job, Chris. The formula is correct You haven’t proved uniqueness of the function, but nevertheless did very well Congrats!

July 18th, 2014 at 7:53 am

Hi Slavy, thanks for the confirmation. I can’t imagine how to prove the uniqueness. Is there a way, or is it that another possibility exists? {seconds later, I guess you need to show that the “gaps”, like f(4) = 7 and f(5) = 8, must be a contiguous chain between the directly calculable values.

I’m still not sure if my “proof” is a proof. I’m pretty sure that it implies that the defined function is self-consistent and the function that I’ve given is consistent with all the defining rules i.e. only positive integers, f(n+1) > f(n) and the consequential f(n) > n etc.

Although the above looks quite easy it took a lot of sweat converting base 10 to base 3. Even after doing that, I still nearly missed the pattern.

July 18th, 2014 at 8:59 am

Darn Chris – I have just used a technique known as brute force to look for the pattern and I came to the same conclusion that base three might be the key as per your post 12.

This is the pattern that clued me in:

f(9)=18

f(18)=27

f(27)=54

f(36)=63

f(45)=81

July 18th, 2014 at 9:07 am

Hi Karl. After I posted, I felt a bit mean in not letting you have a go. Because of Slavy’s comment I suspected that the 2*3^n and 3^n stuff was important, but I couldn’t see why. As far as I was concerned they were much the same because f(2) = 3. I still can’t really see why it should be a clue. Really, it was just the abundance of powers of 3 that triggered me, to try base 3 (really it was only a shot in the dark). There was quite a lot of brute force too.

I’m trying to give a proof of uniqueness, but keep getting it wrong, I think only due to silly mistakes.

July 18th, 2014 at 9:33 am

Fifth time lucky (I hope).

Proof of uniqueness: Let two solutions be f(n) = u and f(n) = v.

Now f(f(n)) = 3n = f(u) = f(v) => there is no ambiguity about f(u) or f(v).

So we must have f(f(u)) = f(f(v)) = 3u = 3v => u = v QED

July 18th, 2014 at 9:38 am

Chris and Karl:

what are the values of f(3^n) and of f(2*3^n) ?

And yes Chris, you have blown my cover in post #12: I am a mathematician.

July 18th, 2014 at 10:00 am

The above proof is dodgy, due to using f(n) to mean two different things. I’ll be back with a cleaner proof.

July 18th, 2014 at 10:24 am

Hi Zorglub. Sorry about blowing your cover (but not really). As you can probably tell, I’m no mathematician. I feel quite privileged that mathematicians visit this site.

f(f(f(a))) = f(3a) = 3f(a). So you can pull all the factors of 3 out of the function => so f(a * 3^n) = 3^n f(a). So f(3^n) = 3^n f(1) = 2 * 3^n and f(2 * 3^n) = 3^n f(2) = 3^(n+1).

July 18th, 2014 at 10:25 am

My proof resides in https://oeis.org/

I worked out the theory, ran my results by this site – they matched – proof positive…..?

Not a mathologist!

July 18th, 2014 at 12:18 pm

To sum up, you got :

f(3^n) = 2 * 3^n

f(2 * 3^n) = 3 *3^n

So what’s

f(3^n + d) for d in D = { 0,1,2,…,3^n } ?

July 18th, 2014 at 1:02 pm

I had (slowly) realised that you were giving a hint in post 18. I followed it the wrong way. The last suggestion does it, thank you.

d = 0 => f(3^n + d) = f(3^n) = 2*3^n

d = 3^n => f(3^n + d) = f(2*3^n) = 3*3^n

The difference in d = 3^n – 0 = 3^n and the difference of the functions also = 3^n.

Setting a = 3^n + d => f(a) = 2*3^n + d.

Aaargh. Just as you said, a beautiful example of the pigeonhole principle. It means all that base 3 stuff was unnecessary. I’ve got to give my head a thorough slapping. I told you I wasn’t a mathematician, I’ve now provided proof.

That’s a very nice solution.

I’m going to show the problem to my son. He’s due to start a 4 year masters in maths this year.

July 18th, 2014 at 1:49 pm

This is where I went with base 3 – having established the following:

f(1)=2

f(2)=3

f(3)=6

f(4)=7

f(5)=8

f(6)=9

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 n is “1″ then f(n) is n with the first “1″ replaced with “2″.

If the first base-3 digit of n is “2″ then f(n) is n with the first “2″ replaced with a “1″, and a “0″ appended to the end of it.

This function meets the conditions, because f(n+1)>f(n) and f(f(n)) replaces the first digit of n 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(n))=3n.

But seeing Chris’s post 23. I shall quietly drink my hot cocoa, and retire for the evening.

July 18th, 2014 at 1:55 pm

Hi Karl. Only a plonker would do it in base 3 and

I’m not sure if base 3 would help with the three tray problem though.

July 18th, 2014 at 8:54 pm

Hi Karl. Seriously, I think that the base 3 breakthrough was pretty nice and you did good.

My embarrassment is multi-faceted. Slavy and Zorglub fed out good clues. But worst is that having got the base 3 ruls, I didn’t notice that they should simply have brought about recognition of the final solution.

But the reason I came back is that my son now knows the solution (he did rather better than me at it, but that’s no surprise as he’s done maths and physics Olympiads – it’s also why I’ve posted some BMO problems). In discussing it with him (we’re both up at 4 am UK time), I did some Googling and found a mathsy site that also had the base 3 solution. After a good giggle, I sent the owner a concise version of the excellent solution that Zorglub rung out of me, here. So that’s my good deed for the day.

July 18th, 2014 at 11:48 pm

I’ve noticed a gaping hole in the overall uniqueness argument. Not all numbers can be represented in the form 3^n + d with d = 0,1,…,3^n. In particular 2014 isn’t of that form. 2014 can be written as 2*3^6 + 556 though. If we include numbers of the form 2*3^n + d, d = 0,1,2,…,3^n then we can write any number in one of those two forms.

For the 3^n numbers of the form x1 = 2*3^n + d, d = 0,1,2,…,3^n we get

d = 0 => f(2*3^n) = 3*3^n = 3^(n+1)

d = 3^n => f(3*3^n) = 6*3^n = 2*3^(n+1)

So there are 3 times as many holes as numbers. 1 in 3 of those holes corresponds a mapping x2 = f(x1), but we don’t yet know if that mapping is uniquely defined, i.e. x2’s are not well defined (yet). The remaining 2/3 are start points that can only be found via the pigeonhole principle – they are not mapped from any previous number.

Consider x3 = f(x2). We know from post 23 that the x3 numbers are well defined and that x3 = f(x2) is also well defined. We can invert the mapping to uniquely determine an x2 from an x3. But x3 = f(f(x1)) =3*x1 so we now have established a unique (but indirect) correspondence between x1 and x2.

I’ll cheat now – because the mapping is unique, it must be the same as the base 3 mapping. So f(2*3^n + d) = 3*3^n + 3*d. The pigeonhole principle let’s us uniquely fill the remaining holes.

Now f(2014) = f(2*3^6 + 556) = 3*3^6 + 3*556 = 3855 (phew).

I’ve not slept, so am getting gaga and much of the above was written in that state. I’ll improve it after a good kip.

July 19th, 2014 at 3:02 am

First of all, Chris, don’t be harsh on yourself for the base 3 stuff. This is a natural idea, and I also exploited it a little at the beginning. Just, once all the dots are connected, a mathematician (usually) has the ability to simplify the solution and to get rid of all the unnecessary details. This doesn’t mean that those details/ideas were stupid

Regarding the uniqueness of the function – you are partially correct. Yes, you just proved that f(3^n+d)=2*3^n+d, whenever d is between 0 and 3^n. However, while d runs through this interval, the function values run through the remaining interval [2*3^n,3^(n+1)], meaning that each of those numbers is a value of f. More precisely, let d in [3^n,2*3^n]. Then f(3^n+d)=f(f(d))=3d

July 19th, 2014 at 6:12 am

I also tried for a long time the base-3 approach. And was not satisfied with it.

Here is a different way than Slavy’s to write the proof (but similar in essence). We now have, by the pigeonhole principle:

f(3^n + d) = 2*3^n+d for d in D = { 0,1,2,…,3^n }

apply f on both sides, and use the second property of f:

f(2*3^n+d) = 3^(n+1) + 3d for d in D = { 0,1,2,…,3^n }

———

If we summarize: any strictly positive integer p can be written in a unique way as

p = a*3^n +d where a is either 1 or 2, n >=0 is an integer and d is in D.

Therefore,

f( p ) = 2*3^n+d when a =1

and

f( p ) = 3^(n+1) + 3d when a =2

which determines f in a unique way.

July 19th, 2014 at 10:51 am

Hi Slavy and Zorglub. Thanks for the feedback.

Really I was quite pleased with the base 3 stuff. In particular that it fulfilled the basic function definition requirements.

My only real personal disappointment is that I hadn’t spotted that a*3^n + d was at the heart of those base 3 expressions – it was begging to be noticed.

My last post was also an attempt at explicitly covering the completeness and uniqueness of the “root” values that are not mapped from previous cases – and can only determined using the pigeonhole principle. Considering the state I was in when I wrote it (I was slipping in and out of consciousness), I’m pleased that it was more or less coherent. My head isn’t clear enough at this moment to see that it wasn’t necessary to tackle it the way I did, and that e.g. Zorglub’s post is sufficient for the purpose. I’ll blame alcohol for that this time.

Would you believe that after writing my last post, I thought I’d try k instead of 3. I couldn’t pin f(1) down, so have abandoned it (for now). I expect it’s a hopeless cause though.

July 19th, 2014 at 5:12 pm

Hi, Chris! k is a lost cause! Regarding the proof here – you’re just lacking self-assurance to take your time and publish whenever you’re done Reducing your posts from 5 to 1 will bring us the optimal solution, but you felt unsecured and improved step by step. This is not a problem, at all, because you did learn something throughout the process, so the biggest winner is you (and Karl, supposedly)

July 19th, 2014 at 6:50 pm

My head’s a lot clearer now. I had got hold of the wrong end of a stick when concerning my self about the numbers that are not representable as f(a). It was a form of detachment from reality. I’m now completely satisfied that there no loose ends and that f(n) is unique, well defined and that we have explicit formulae for it.

In mitigation, lately my brain seems to be fuzzy much of the time – I think it’s due to the meds I’m taking for my heart.

July 19th, 2014 at 7:38 pm

Altogether we have:

I’ll assume f(1) = 2 and f(2) = 3.

Using f(f(x)) = 3x => f(f(f(x))) = f(3x) = 3 f(x) => f(3^n x) = 3^n f(x).

Any positive integer, x, may be uniquely written as

x = a*3^n + d, where a = 1 or 2 and d is one of 0, 1, 2, …, 3^n – 1.

The a = 1 and a = 2 cases are disjoint.

For a = 1, f(x) = f(3^n + d)

d = 0 => f(3^n) = 3^n f(1) = 2*3^n

d = 3^n => f(2*3^n) = 3^n f(2) = 3*3^n

Both d and f(3^n + d) changed by 3^n. The pigeonhole principle then =>

f(3^n + d) = 2*3^n + d, d in range 0 … 3^n

Now f(f(x)) = 3x, so f(f(3^n + d)) = f(2*3^n + d) = 3(3^n + d)

d in range 0… 3^n.

We now uniquely know f(x) for every x.

July 21st, 2014 at 6:08 am

Here is way to pose the question with a positive integer k instead of 3:

f is a function that maps a positive integer to a positive integer, and satisfy the properties

f(n+1) > f(n)

and

g(n) = k *n for every integer n, where

g(n) = f( f( f(…f(n)…))) – where f is applied k-1 times.

Notice that if k= 3 we are back to the original problem.

And if k = 2, the problem is very easy.

Give a function f that satisfies the above requirements, for any k.

July 21st, 2014 at 7:09 am

Thank you Zorglub. I might have a look at that variation.

July 21st, 2014 at 11:39 am

My fault – this is the correct generalization and it’s straightforward. I referred as hopeless to the problem f(f(n))=kn, k>3