Math olympiad products question

1. May 30, 2017

vishnu 73

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. May 30, 2017

BvU

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

3. May 30, 2017

SammyS

Staff Emeritus
The first three factors certainly suggest that.

(Actually, the first 4 factors do.)

4. May 30, 2017

Buffu

Use AM-GM and properties of Logarithms.

5. May 30, 2017

haruspex

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?

6. May 30, 2017

Buffu

Wolfram alpha says the answer is 9.

7. May 30, 2017

haruspex

Ah, yes. I counted the 5 factor twice. Thanks.

8. May 31, 2017

vishnu 73

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

9. May 31, 2017

Buffu

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 ?

10. May 31, 2017

haruspex

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.

11. Jun 5, 2017

vishnu 73

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

12. Jun 5, 2017

haruspex

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?

13. Jun 5, 2017

vishnu 73

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

14. Jun 5, 2017

Buffu

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
15. Jun 5, 2017

vishnu 73

@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

16. Jun 5, 2017

haruspex

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.

17. Jun 5, 2017

vishnu 73

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

18. Jun 5, 2017

haruspex

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.

19. Jun 5, 2017

vishnu 73

oh ya i forgot about 5 now i am getting that but how does the closed form help

20. Jun 5, 2017

haruspex

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