challenging question for you math wizs?

Question

show that (n^2)!/(n!)^n is a natutal no foar all nbelongs to N
the answer next week the smaller the better (i know 2 ways so far)
and PLEASE no stupid answers for points its irritating

like pascal and jay h and scott r

the induction method is ok but the question asks to be solved without using induction

Answer 1

This method is by proving there are more prime number factors for the numerator than the denominator for those prime numbers less than n.

(n^2)! = n^2.(n-1)^2 ... 3.2.1
(n!)^n = n^n.(n-1)^n.(n-2)^n....3^n.2^n.1
Since any non-prime number can be expressed as the product of some smaller prime numbers, n! can be expressed as p1^m1.p2^m2...pk^mk, and (n!)^n = (p1^m1.p2^m2...pk^mk)^n
where p(i) are prime numbers and 1 < p(i) <= n, m(i) are natural numbers, i=1..k.
Now, lets see if (n^2)! can be expressed in the similar form as p1^q1.p2^q2...pk^qk.r where q(i)<=m(i).n, i=1..k, and r is a natural number such that this expression = (n^2)!.

Lets find m1,m2,...,mk.
Consider p(i), i = 1..k
m(i) = floor(n/p(i)) + floor(n/p(i)^2) + ... + floor(n/p(i)^s),
where p(i)^s <= n.
Illustration: n = 10, i = 2, p(2) = 3 (2nd prime number of 2,3,5,7)
floor(10/3) + floor(10/3^2) = 3 + 1 = 4, i.e. 10!/3^4 is natural but not 10!/3^5. Because from 1 to 10, 3 is a factor of 3, 6, 9, and 3 is again a factor of 9.

By the same method,
q(i) = floor(n^2/p(i)) + floor(n^2/p(i)^2) + ... + floor(n^2/p(i)^t),
where p(i)^t <= n^2

Since n <= n^2, s <= t.
Since for all real x >= 0, n.floor(x) <= floor(nx).
Thus, n.m(i) <= q(i) for i = 1..k
Therefore,
(p1^q1.p2^q2...pk^qk.r)/((p1^(n.m1).p2^(n.m2)...pk^(n.mk)) is a natural number, so
(n^2)!/(n!)^n is a natural number.

===========
Verify with n = 6:
m1 = floor(6/2) + floor(6/4) = 3+1 = 4
m2 = floor(6/3) = 2
m3 = floor(6/5) = 1
2^4 . 3^2 . 5^1 = 16 . 9 . 5 = 720 = 6!
Alternatively: 6.5.4.3.2.1 = 3.2.5.2.2.3.2 = 2^4 . 3^2 . 5^1
q1 = floor(36/2) + floor(36/4) + floor(36/8) + floor(36/16) + floor(36/32) = 18 + 9 + 4 + 2 + 1 = 34
q2 = floor(36/3) + floor(36/9) + floor(36/27) = 12 + 4 + 1 = 17
q3 = floor(36/5) + floor(36/25) = 7 + 1 = 8
So, q1 > 6m1, q2 > 6m2, and q3 > 6m3.

Answer 2

I factored out n! from top and bottom to simplify it a bit, but I'm still getting the answer as true for N if and only if n=1 or n=2. For n>2 in N, I'm getting a fraction.
Back to the drawing board.

Answer 3

ok shall we see... teach that for each non-detrimental integer n, the selection 7^7^n +a million is the fabricated from a minimum of 2n+3 (no longer unavoidably different) top factors. This grow to be from the 2007 USAMO. on the competition, I only wrote for n=0, the subject is trivial. something of the evidence via induction is left as an workout for the grader. LOL

Answer 4

Wait -- are you saying I'm a math whiz, or that my answers are irritating? :-D

In all fairness, I'm kinda doodling out a proof by induction, but alas I'm at work, with work stuff that I have to focus on, so one of the other math whizzes will probably get it first. :-) But I've got most of it scribbled out... I just have yet to show that n!·(n+1)^(n+1) goes into (n²+1)(n²+2)···(n²+2n+1), if that helps anyone else!

Answer 5

It is well know that binomial coefficients

x C y = x! / (x-y)! y!

are integral. Therefore

(n^2) C n = (n^2)! / (n^2 - n)! n!

is integral, as well as

(n^2 - n) C n = (n^2 - n)! / (n^2 - 2n)! n!

and in general,

(n^2 - kn) C n = (n^2 - kn)! / (n^2 - [k+1]n)! n!

The product of all these coefficients is

[(n^2) C n] * [(n^2 - n) C n] * ... * [n C n] = (n^2)!/(n!)^n

which is therefore also an integer.

Answer 6

First we prove a more general case: (kn)!/(n!)^k is a natural number for all n, k. We proceed by induction: This is trivially true when k=1. Suppose this is true for some k: for k+1 we have (kn+n)!/((n!)(kn)!) * (kn)!/(n!)^k. (kn+n)!/((n!)(kn)!) is simply the binomial coeffiecient for kn+n choose n, and is therefore a natural number, and (kn)!/(n!)^k by our inductive hypothesis is also a natural number, so (kn+n)!/((n!)(kn)!) * (kn)!/(n!)^k is also natural and thus by induction (kn)!/(n!)^k is a natural number for all k. Setting k=n we have (n^2)!/(n!)^n is natural, which completes the proof.

Answer 7

{
no of ways of arranging N balls in which (P1 balls identical,P2
balls identical,...Pn balls identical such that P1+P2+....+Pn=N
is given by N!/(P1!P2!....Pn!).
}

let us assume we have n^2 balls and there are n balls of one kind, n balls of second kind and so on.

the no of ways of arranging these n^2 balls is

(n^2)!/(n!)(n!)....(n times) = (n^2)!/(n!)^n

the no of ways of arrangments for the above problem is an integer and hence the proof.

Answer 8

maybe if you made your problems clearer.....and spoke english.....math is my subject...not english