Saturday 3 September 2011

how many zeros in the end of huge number

Note: Came across this Q at TIFR-Ph.D.entrance test.

Let n > 1 be an odd integer. How many zeros are at the end of number S = 99^n+1 (Read as S = 99 raised to the power n and then 1 added to it)

At first glance, this indicates some trick, for two reasons. First, S is going to be huge very fast, even with comparatively small n and second, this was asked in Ph.D test of TIFR! :D

I thought of splitting 99 as 100-1 and getting a generic result form for S.
i.e.

S = 99 ^ n - 1 = P - 1..................... s.t. P = 99 ^ n (n > 1, odd)
so,
P = 99 ^ n = (100 - 1) ^ n = (-1 + 100) ^ n
Using binomial theorem for expansion,
P = \sum_over_k=0_to_k=n {nCk * (-1)^k * 100 ^ (n-k)}
P = nC0 * (-1)^0 * 100 ^ n
   + nC1 * (-1)^1 * 100 ^ (n-1)
   + .....
   + nC{n-1} * (-1) ^ (n-1) * 100 ^ 1  ..................... note n-1 is even
   + nCn * (-1) ^ n * 100 ^ 0              ..................... note n is odd

Solving we get alternate terms positive and negative s.t. first term is positive (due to (-1)^0) and last term negative (due to (-1) ^ n, n being odd)

P = P1 - P2 + P3 - ....... - Pk + 100n - 1

where P1, P2, ..., Pk are terms which are multiples of powers (>=2) of 100.

Thus,
P = a_term_multiple_of_powers>=2_of_hundred +100n - 1

Thus,
S = P + 1 = a_term_multiple_of_powers>=2_of_hundred + 100n - 1 + 1 a_number_multiple_of_powers>=2_of_hundred + 100n = a_number_ending_with_two_zeros.

Thus, S ends with 2 zeros.

No comments:

Post a Comment