A number theory problem by Jai sahota

What is the number of trailing zeroes in ( 200 100 ) { 200 \choose 100} ?

10 1992 132 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

Naren Bhandari
Oct 22, 2017

C ( 200 , 100 ) = ( 200 100 ) = 200 ! 100 ! 100 ! C(200,100)= \binom{200}{100} =\frac{200!}{100!100!} Total numbers of trailing zeros hold by ( 200 100 ) \binom{200}{100} are the prime factor of 5 5 . So highest power of prime p = 5 p= 5 for 200 ! 200! , 100 ! 100! is given by \begin{aligned}& H_p(n!) & =\displaystyle\sum_{k=1}^{m}\left\lfloor\frac{n}{p^k}\right\rfloor\phantom{cccccccc}\text{where p^m≤n<p^{m+1}} \end{aligned} H 5 ( 200 ! ) = 200 5 + 200 25 + 200 125 = 40 + 9 + 1 = 49 \begin{aligned} H_5(200!) & = \left\lfloor\frac{200}{5}\right\rfloor +\left\lfloor\frac{200}{25}\right\rfloor+\left\lfloor\frac{200}{125}\right\rfloor \\& = 40+9+1 = 49\end{aligned} H 5 ( 100 ! ) = 100 5 + 100 25 = 20 + 4 = 24 \begin{aligned} H_5(100!) & = \left\lfloor\frac{100}{5}\right\rfloor +\left\lfloor\frac{100}{25}\right\rfloor \\& = 20+4= 24\end{aligned}

It can be noted that the total number of zeros in denominator are 2 × 24 = 48 2\times24 = 48 .There are altogether 49 49 zeros in the numerator and 48 48 zeros in denominator. Remaining numbers of are ending zeros of ( 200 100 ) \binom{200}{100} ie 1 1 .

Note: You should also check the number of powers of 2.

To elaborate, 100 40 \frac{ 100 } { 40 } does not end with 1 0, even though the powers of 5 are H 5 = 2 1 = 1 H_5 = 2 - 1 = 1 .

Calvin Lin Staff - 3 years, 7 months ago
Vilakshan Gupta
Oct 22, 2017

( 200 100 ) = 200 ! 100 ! × 100 ! \binom{200}{100}= \frac{200!}{100! \times 100!} ,which again is equal to 200 × 199 × 198 × × 102 × 101 100 × 99 × 98 × × 2 × 1 \large \frac{200 \times 199 \times 198 \times \cdots \times 102 \times 101}{100 \times 99 \times 98 \times \cdots \times 2 \times 1} Now by using floor function\greatest integer function on 100 ! 100! we will get number of 0 0 's equal to 24 24 and similarly using floor function on 200 ! 200! , we will get number of 0 0 's equal to 49 49 .But the product in the numerator will have only 49 24 = 25 49-24=25 0 0 's. Hence, the number of zeroes in the expression will be 1 \boxed{1} because 24 24 0 0 's will get cancelled from numerator and denominator both.

You made a serious misconception. Can you identify it?

Calvin Lin Staff - 3 years, 7 months ago

What's my mistake? I can't understand.Please tell me sir.

Vilakshan Gupta - 3 years, 6 months ago

Log in to reply

Does 100 80 \frac{ 100} { 80} end with 1 zero "because 1 0's will get cancelled from numerator and denominator both"?

Calvin Lin Staff - 3 years, 6 months ago

Log in to reply

Oh yes! I got it. I did not show that the numerator will be completely divisible by the denominator. Sir I request you to change my solution,because you will write it in a good way.

Vilakshan Gupta - 3 years, 6 months ago

Log in to reply

@Vilakshan Gupta Well, that's not the only issue. For example, 100 20 \frac{100}{20} doesn't end with 1 0's, even though the numerator is completely divisible by the denominator.

So, figure out what the crux of the issue is.

Unfortunately, I do not think there is a simple way to fix your solution, without introducing a new idea to it.

Calvin Lin Staff - 3 years, 6 months ago

Log in to reply

@Calvin Lin Then what will be a perfect solution for the problem, as @Naren Bhandari 's solution is also incomplete due to similar reasons, what can be the good solution.

Vilakshan Gupta - 3 years, 6 months ago

Log in to reply

@Vilakshan Gupta Naren's solution is fine (once he fills the gap about the powers of 2). That is the correct way of proceeding. Instead of focusing on the "number of zeros", he focused on the "number of powers of 5 (and 2)". This way, if we can guarantee that 5 divides the number, and 2 divides the number, then we can conclude that 10 divides the number.

IE In the example of 100 20 \frac{100}{20} , because 2 doesn't divide the number (since the power of 2 in the numerator and denominator are both 2^2), hence it will not be divisible by 10.

Calvin Lin Staff - 3 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...