PMO problem

1 × 3 × 5 × × 31 × 33 × 35 \large1 \times 3 \times 5 \times \cdot \cdot \cdot \times 31 \times 33 \times 35

Find the largest power of 3 that divides the number above.


The answer is 9.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Vighnesh Raut
Apr 24, 2015

1 × 3 × 5 × . . . . × 35 = 1 × 2 × 3 × 4 × 5 × . . . . . . × 35 × 36 2 × 4 × 6 × 8 × . . . . . × 36 = 36 ! 2 18 × 18 ! 1\times 3\times 5\times ....\times 35\\ =\frac { 1\times 2\times 3\times 4\times 5\times ......\times 35\times 36 }{ 2\times 4\times 6\times 8\times .....\times 36 } \\ =\frac { 36! }{ { 2 }^{ 18 }\times 18! }

Now, power of 3 in 36! is 36 3 + 36 9 + 36 27 = 12 + 4 + 1 = 17 \left\lfloor \frac { 36 }{ 3 } \right\rfloor +\left\lfloor \frac { 36 }{ 9 } \right\rfloor +\left\lfloor \frac { 36 }{ 27 } \right\rfloor \\ =12+4+1\\ =17

And the power of 3 in 18! is 18 3 + 18 9 = 6 + 2 = 8 \left\lfloor \frac { 18 }{ 3 } \right\rfloor +\left\lfloor \frac { 18 }{ 9 } \right\rfloor \\ =6+2\\ =8

So, 1 × 3 × 5 × . . . . × 35 1\times 3\times 5\times ....\times 35\\ can be written as k × 3 17 m × 3 8 \frac { k\times { 3 }^{ 17 } }{ m\times { 3 }^{ 8 } } for some constants k & m and in simple power of 3 it can be further reduced to A × 3 9 A\times { 3 }^{ 9 } where mA=k

Moderator note:

There's a slightly easier method to do this. Can you solve it the number of terms multiplied became much larger, i.e.: 3 × 5 × 7 × × 100001 3 \times 5 \times 7 \times \cdot\cdot\cdot \times 100001 ? Hint: Which of these numbers being multiplied are multiples of 3 3 ? Can you spot a pattern?

@challenge master ... Can you please give a small hint so that I can get to know of which method you are talking about?

Vighnesh Raut - 6 years, 1 month ago

Beautiful solution 😍

Akhil Bansal - 5 years, 8 months ago

NIce Solution @Vighnesh Raut . Exactly the same way As I solved it :)

Mehul Arora - 6 years, 1 month ago
Kunal Verma
Apr 25, 2015

I'm gonna give a general solution to this.

First we find the first and last numbers divisible by 3 3 ( 3 3 and 33 33 here) which are formed by multiplying 3 3 by 1 1 and 11 11

This is an A.P of 1 1 to 11 11 with d = 2 d \ = \ 2 Thus, there are n = 6 n \ = \ 6 terms in the sequence. Now, we find the smallest power x x of 3 3 greater than 1 1 ( 2 2 here) and find all of it's odd multiples, except the ones containing any multiple of 3 3 in the sequence y y and write this as ( x 1 ) × y (x \ - \ 1) \times y ( which is equal to 1 1 for 3 2 3^{2} and 2 2 for 3 3 3^{3} here). We go on till there are no more powers of 3 3 in the sequence. Now sum these and add it to the original n n i.e:- 6 + 2 + 1 = 9 6 \ + \ 2 \ + \ 1 \ = \boxed{9} here.

This can be used for any huge sequence for 3 3 or any other odd number except one( probably not even).

Ramiel To-ong
Dec 16, 2015

the largest power of 3 for 35! is 15, deleting the even numbers of the set, gives us 6 powers of 3, thus 15 -6 = 9 largest remaining powers of 3 for the given set.

Arulx Z
Jun 19, 2015

11 11 is the largest number for which 11 3 35 11 \cdot 3 \le 35 .

Therefore powers of three are enclosed within this series:

( 1 3 ) ( 3 3 ) ( 5 3 ) . . . ( 11 3 ) (1\cdot 3)(3\cdot 3)(5\cdot 3)...(11\cdot 3)

Now we need to find the largest power of 3 which can divide the above series.

Since we have already simplified the sum, we just need to count the threes from above series. By doing that, we find out that that the largest power of 3 3 is 6 6 .

Now, the simplified series (after removing the powers of 3 which we have counted):

1 3 5...11 1\cdot 3\cdot 5...11

But we are not done yet as some terms still contain powers of three. We separate these terms and rewrite the series:

3 9 3\cdot 9

Since there are only two terms, we can count the largest power 3 3 which can divide the above product which is three.

We add the two powers 6 + 3 6 + 3 . So the answer is 9 9 .

Moderator note:

Good approach.

How can this be generalized?

Andrew Machkasov
Apr 27, 2015

The multiples of 3 are the terms whose index gives a remainder of 2 when divided by 3. There are 18 terms total, so there are 6 terms which have a factor of 3. Of those, 2 have a factor of 9, and 1 of those has a factor of 27. Thus we have 6 + 2(2-1) + 1(3-2) = 6 + 2 + 1 = 9.

However, the question is a bit ambiguous. I put 3^9 = 19683 as my answer at first. Maybe it's just me though.

Trying an easier (but lazier) approach: Among 1, 3, 5, ... , 33 and 35, there are six numbers that are divisible by 3: 3,9,15,21,27, and 33.

With 9=3^2 , and 27=3^3, and the other four numbers having 3 in a single multiplicity, then 3+2+1+1+1+1 = 9.

Moderator note:

Yes, often times the simplest straightforward method works. However, it's very impractical to use this method if the number of terms multiplied became much larger, i.e.: 3 × 5 × 7 × × 100001 3 \times 5 \times 7 \times \cdot\cdot\cdot \times 100001 . But obviously there's still a shortcut to this. Can you find it?

What's your shortcut challenge master?

Jun Arro Estrella - 5 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...