Subscribe via feed.

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 ?


This post is under “Tom” and has 36 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

36 Responds so far- Add one»

  1. 1. Chris Said:

    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.

  2. 2. Zorglub Said:

    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.

  3. 3. Karl Sharman Said:

    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?

  4. 4. slavy Said:

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

  5. 5. Zorglub Said:

    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.

  6. 6. slavy Said:

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

  7. 7. Karl Sharman Said:

    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!

  8. 8. Karl Sharman Said:

    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…

  9. 9. Chris Said:

    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.

  10. 10. Chris Said:

    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.

  11. 11. slavy Said:

    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…

  12. 12. Chris Said:

    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.

  13. 13. slavy Said:

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

  14. 14. Chris Said:

    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.

  15. 15. Karl Sharman Said:

    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

  16. 16. Chris Said:

    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.

  17. 17. Chris Said:

    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

  18. 18. Zorglub Said:

    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.

  19. 19. Chris Said:

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

  20. 20. Chris Said:

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

  21. 21. Karl Sharman Said:

    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!

  22. 22. Zorglub Said:

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

  23. 23. Chris Said:

    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.

  24. 24. Karl Sharman Said:

    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.

  25. 25. Chris Said:

    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.

  26. 26. Chris Said:

    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.

  27. 27. Chris Said:

    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.

  28. 28. slavy Said:

    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

  29. 29. Zorglub Said:

    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.

  30. 30. Chris Said:

    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.

  31. 31. slavy Said:

    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)

  32. 32. Chris Said:

    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.

  33. 33. Chris Said:

    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.

  34. 34. Zorglub Said:

    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.

  35. 35. Chris Said:

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

  36. 36. slavy Said:

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

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0