Sweet Arrival

What is the largest power of 3 3 that divides ( 200 100 ) \dbinom{200}{100} ?


The answer is 1.

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.

2 solutions

( 200 100 ) = 200 ! 100 ! ( 200 100 ) ! = 200 ! 100 ! 100 ! = 200 199 . . . 100 99 . . . 1 100 99 . . . 1 100 99 . . . 1 = 200 199 . . . 101 100 99 . . . 1 \dbinom{200}{100} = \frac{200!}{100! (200-100)!} = \frac{200!}{100! * 100!} =\frac{200 * 199 * ... * 100 * 99 * ... 1}{100*99*...*1 * 100*99*...*1} =\frac{200 * 199 * ... * 101}{100*99*...*1}

Now we can start counting the factors of 3 in the numerator and denominator and cancel them out.

Looking at the denominator we have 33 numbers that are divisible by 3 1 3^1 . 100 3 = 33 \lfloor{\frac{100}{3}} \rfloor = 33

We use the same method for the numerator but now we subtract the factors in the range 1 ... 100.

200 3 100 3 = 33 \lfloor{\frac{200}{3}} \rfloor - \lfloor{\frac{100}{3}} \rfloor = 33

Both the numerator and the denominator had 33 factors of 3 1 3^1 . We continue by looking at 3 2 3^2

Denominator: 100 3 2 = 11 \lfloor{\frac{100}{3^2}} \rfloor = 11

Numerator: 200 3 2 100 3 2 = 11 \lfloor{\frac{200}{3^2}} \rfloor - \lfloor{\frac{100}{3^2}} \rfloor = 11

Now 3 3 3^3

Denominator: 100 3 3 = 3 \lfloor{\frac{100}{3^3}} \rfloor = 3

Numerator: 200 3 3 100 3 3 = 4 \lfloor{\frac{200}{3^3}} \rfloor - \lfloor{\frac{100}{3^3}} \rfloor = 4

Aha! The numerator have 4 factors that are divisible by 3 3 3^3 while the denominator only had 3. This means that the whole expression is divisible by 3 1 3^1 .

However, we have to check 3 4 3^4 too before we can be certain.

Denominator: 100 3 4 = 1 \lfloor{\frac{100}{3^4}} \rfloor = 1

Numerator: 200 3 4 100 3 4 = 1 \lfloor{\frac{200}{3^4}} \rfloor - \lfloor{\frac{100}{3^4}} \rfloor = 1

3 5 3^5 is bigger than 200 so there is no need to check that. We can conclude that the numerator has one factor of 3 more than the denominator and thus the answer is 1.

First we have to find number of 3 in each number.

Number of 3 in 100! is 100 3 + 100 9 + 100 27 + 100 51 = 33 + 11 + 3 + 1 = 48 \left\lfloor \frac { 100 }{ 3 } \right\rfloor +\left\lfloor \frac { 100 }{ 9 } \right\rfloor +\left\lfloor \frac { 100 }{ 27 } \right\rfloor +\left\lfloor \frac { 100 }{ 51 } \right\rfloor =33+11+3+1=48

Number of 3 in 200! is 200 3 + 200 9 + 200 27 + 200 81 = 66 + 22 + 7 + 2 = 97 \left\lfloor \frac { 200 }{ 3 } \right\rfloor +\left\lfloor \frac { 200 }{ 9 } \right\rfloor +\left\lfloor \frac { 200 }{ 27 } \right\rfloor +\left\lfloor \frac { 200 }{ 81 } \right\rfloor =66+22+7+2=97

So, the number of 3 that left in this expression is 97 2 × 48 = 97 96 = 1 97-2 \times 48=97-96=\boxed{1}

good solution ...thanx for providing the solution...:)

Mishita Meena - 5 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...