Determine the highest power of $1980$ which divides \[\frac{(1980n)!}{(n!)^{1980}}.\]
Problem
Source:
Tags: function, Divisibility Theory
22.07.2007 05:53
Peter wrote: baz wrote: I think I can show that this tends to infinity. Does this sound correct to anyone else? See http://www.artofproblemsolving.com/Forum/viewtopic.php?t=153926 for more information. Thanks It certainly tends to infinity. But I think the problem wants an explicit formula in function of $ n$ (and hopefully a more elegant one than the immediate form t0rajir0u gives). At least I think that, I don't have a solution myself, but from the statement I think that is what the problem authors intended. Welcome to this forum by the way.
05.02.2008 23:28
It definitely does not tend to infinity. The largest number k such that 1980^k is a factor of ((1980n)!)/((n!)^1980) is no larger than the largest number k such that 11^k is a factor of ((1980n)!)/((n!)^1980). Denote this number by k(n) Now, let f(n)=(11n)! / (11^n) (n!). I claim that f(n) is an integer, but is not divisible by 11. For f(0)=1 and f(n+1)/f(n)=(11n+11)(11n+10)(11n+9)(11n+8)...(11n+1)/(11(n+1))=(11n+10)...(11n+1). Thus the largest power of 11 that divides into (11n)!/n! is n. Let T(n)=((1980n)!)/((n!)^1980). Then T(11n)/T(n)=f(1980n)/(f(n)^1980). The right hand side is expressed as a fraction where neither top nor bottom is divisible by 11. Thus T(11n) and T(n) are divisible by exactly the same powers of 11. Thus k(11n)=k(n), so k(n) does not tend to infinity.
06.02.2008 02:45
Interesting. Baz proved there is a subsequence $ (n_k)$ that converges to infinity, and you proved that not every sequence converges to infinity. Both do, however, not answer the original question, do they?
06.02.2008 05:18
Peter wrote: Determine the highest power of $ 1980$ which divides \[ \frac {(1980n)!}{(n!)^{1980}}. \] \[ \frac {(1980n)!}{(n!)^{1980}}=\prod_{i=1}^{1980}{in \choose n} \] Trying to extend this to something more useful but it just keeps going back into what t0r said
06.02.2008 07:59
Let \[ or(p)=ord_p(\frac{(1980n)!}{(n!)^{1980}}=\sum_{k=1}^{\infty}([\frac{1980n}{p^k}]-1980[\frac{n}{p^k}]).\] Because $ 1980=2^2*3^2*5*11$ we get highest power is $ x(n)=min([\frac{or(2)}{2}],[\frac{or(3)}{2}],or(5),or(11)).$