1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Math olympiad products question

  1. May 30, 2017 #1
    1. The problem statement, all variables and given/known data
    ok here is another problem that wrecked me in todays olympiad

    find smallest integer n such that

    5 (32 + 22)(34 + 24)(38 + 28)....(32n + 22n) > 9256

    2. Relevant equations


    3. The attempt at a solution
    ok once again how am i supposed to start

    does writing 3 = 2+1 help?
    i don't see how i can factorize or cancel terms cant telescope cause not summation
    hint please!
     
    Last edited by a moderator: May 30, 2017
  2. jcsd
  3. May 30, 2017 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Could that last factor be $$( 3^{2^n}+2^{2^n} ) \quad\rm ? $$
    In which case we have to decide between n=8 or n=9
     
  4. May 30, 2017 #3

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    The first three factors certainly suggest that.


    (Actually, the first 4 factors do.)
     
  5. May 30, 2017 #4
    Use AM-GM and properties of Logarithms.
     
  6. May 30, 2017 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The powers of 2 are swiftly dwarfed by the powers of 3, so you can get a lower bound on the LHS by ignoring the powers of 2. You can improve it a bit by multiplying by 13/9 so as to bring back in the 22 term, etc.
    You mean 8 or something less, right?
     
  7. May 30, 2017 #6
    Wolfram alpha says the answer is 9.
     
  8. May 30, 2017 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Ah, yes. I counted the 5 factor twice. Thanks.
     
  9. May 31, 2017 #8
    ok does it go something like this

    @haruspex
    the sum ignoring 2k terms for now can be written as

    5 ( 32)(34) ... ( 32n)
    5 ( 91)(92) ... (92(n-1)) > 928
    5( 920+21 + ... 2n-1)
    5( 9 2n-1 )
    then
    5/9 (92n) > 928
    now for the correction factor how is it 13/9 where did you get that from

    @Buffu
    by am gm do you mean i apply it terms like
    32 + 22 ≥ 2 (3) (2)

    or do you mean like taking the whole left hand side as the product and ending up with

    LHS ≤ (5 + 32 + 22 .... 32n + 22n)n+1/(n+1) n+1

    or none of theses please help
     
  10. May 31, 2017 #9
    Yes I mean term wise,

    ##\displaystyle \prod_{n= 0}^k (2^{2^n} + 3^{2^n}) \ge \prod_{n=0}^k 2 \sqrt{6^{2^n}}##

    Can you find a closed form for the second product ?
     
  11. May 31, 2017 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Not quite. The LHS is a lower bound for the expression you started with, so it is not necessarily greater than 9256. But if you find an n that satisfies this inequality (9 is obviously the lowest) then that is an upper bound for the answer to the question.
    Having found the answer is 9 or less, the question is whether it might be 8, say.
    In throwing away the 22n terms, the first discarded one turned 32+22=13 into 9. Multiplying by 13/9 merely restores that. Note that this is more significant than the discarding of 2 term in the next bracket, and so on. So my thinking was to see whether restoring them successively from the left would push the n=8 product over 9256.

    However, it is quite likely that Buffu's method is more effective at that. On the other hand, this is still only a lower bound for the expression. If the more accurate approximation still does not get you over 9256 with n=8 then you are no further forward. You need an upper bound on the LHS if we are to rule out n=8 as being too low.
     
  12. Jun 5, 2017 #11
    sorry for the late reply currently in overseas

    @Buffu

    22n + 32n ≥ 2 * 62n-1

    so the product on the left hand side can be simplified after extracting the first term as the first term is 2 * √6

    the product on the left hand side is equivalent to

    ≥2k * 62K+1-1 * √6

    is this correct? how to proceed?

    @haruspex

    now i see where you got the 13/9

    but the given answer was actually 8 by a local source
     
  13. Jun 5, 2017 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Doh!
    The left hand side reduces to a remarkably simple closed form.
    Imagine expanding the product. You will get a sum of terms like 2a3b.
    What are the possible values of a? What is the relationship between a and b?
     
  14. Jun 5, 2017 #13
    @haruspex
    oh wow it does it is sort of like a binomial expansion in the sense that powers add up to a constant depending on the highest power in the product except that you dont have binomial coefficients and the powers in subsequent terms decrease by 2 instead of 1

    so a + b always add up to 2n+1-2 where n is the highest power in the product
    correct?
     
  15. Jun 5, 2017 #14
    I get the answer as ##\displaystyle \prod^k_{n = 0} 3^{2^n} + 2^{2^n} \ge 2^k \times 6^{2^k - 2^{-1}} > 3^{512}##

    Taking log base 6,

    ##k \log_6 2 + 2^k - 1/2 > 512\log_6 3 \iff k \log_6 2 + 2^k > 512\log_6 3 + 1/2##

    You can solve this and get ##k = 9##.
     
    Last edited: Jun 5, 2017
  16. Jun 5, 2017 #15
    @Buffu but once again as @haruspex said when we take the am gm we only get a lower bound

    for example we can 4 ≥ 2 but that does not mean 4 is bigger than 3 only if 2 is bigger than 3 it is the same logic the right hand side of the am- gm can be lesser than 3512 while the lhs still being greater than 3512 i.e. lhs of am-gm ≥ 3512≥ rhs of am-gm

    i think this is what @haruspex was trying to drive at
     
  17. Jun 5, 2017 #16

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Well, you get a lower bound for the product, which leads to an upper bound for n. I.e. you can show n is at most 9. But the cruder approach I started with, omitting the powers of 2, leads to that also. We need the collapse to the closed form to show n cannot be 8.
     
  18. Jun 5, 2017 #17
    why not 8 because after all we only considered the correction factor for the first term
    and i am sorry i meant you get a upper bound with am gm
     
  19. Jun 5, 2017 #18

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    What do you get for the closed form expression?
    If you write the factor 5 at the front as 2+3 you should get a+b=2n+1-1.
     
  20. Jun 5, 2017 #19
    oh ya i forgot about 5 now i am getting that but how does the closed form help
     
  21. Jun 5, 2017 #20

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I ask again, do you have the closed form? It shows immediately that 8 is not enough.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Math olympiad products question
Loading...