Putnam Problem of the Day

[http://math.harvard.edu/putnam(...) !!84u21X0KjW+ No.10602626]

[math]
\text{Prove that the expression}
\\
\qquad \qquad \qquad \displaystyle\frac{gcd(m,n)}{n}\binom{n}{m}
\\
\text{is an integer for all pairs of integers }n\geq m\geq 1 \text{.}
[/math]

[http://math.harvard.edu/putnam(...) !!84u21X0KjW+ No.10602629]

Previous Thread >>10592377

[Anonymous No.10602632]

>>10602626
>>10602626
Welcome back.

[Anonymous No.10602641]

>>10602626
Pffffft this is easy. Watch this engie solve this and shit all over you mathfags

[Anonymous No.10602771]

>>10602626
thinly veiled homework thread
glad to see you back remmy!

[Anonymous No.10602785]

What does that second term mean? (The parenthesis with n and m)

[Anonymous No.10602824]

>>10602626
I just realized I don't even know how to prove that the binomial coefficient is an integer...

[Anonymous No.10602830]

>>10602785

n! / (m!(n-m)!)

[Anonymous No.10602840]

lmao I got a B- in calc 1 and never looked back

nerds

[Anonymous No.10602886]

>>10602824
It is the number of subsets of size m in {1,...,n}.
To see that the two things coincide, you can give a combinatorial argument. The neatest I think is to look at the action of [math]\mathfrak S_n[/math] on the set of subsets of {1,...,n} of size k.
The action is transitive, hence the number of subsets of size k in {1,...,n} is exactly the order of [math]\mathfrak S_n[/math], ie. n!, divided by the order of the stabilizer of any subset of size k. But note that the stabilizer of {1,...,k} is exactly [math]\mathfrak S_(\{1,...,k\}) \times \mathfrak S(\{k+1,...,n\})[/math] which has order [math]k!(n-k)![/math], which completes the proof.

[Anonymous No.10602889]

>>10602886
woops, replaced m by k everywhere, but you see what i meant

[Anonymous No.10602892]

>>10602830
Oh, I’ve only seen that as C(n, m)
I think the C stands for choose

[Anonymous No.10602996]

>>10602886
Isn't that a little overkill.
Isn't easier to remember why the binomial coefficients are called BINOMIAL coefficients?

Just recals I binomial is:
[math] (x + y)^n [/math] which is just a polynomial in [math] x [/math] and [math] y [/math].

So it takes the form of:
[math] (x + y)^n = a_0 x^n + a_1 x^{n-1}y + \cdots + a_{n-1} x y^{n-1} + a_{n} y^n [/math].
So the coefficients [math] a_k [/math] are all binomial coefficients which are derived by only adding and multiplying whole numbers...which must mean they are also whole numbers.

[Anonymous No.10604108]

>>10602626
The highest exponent of p that divides n! is known (it depends on the expression of n in base p I think). I would guess one could start from there (and maybe it is enough). I am not going to go through the rest of the computations though.

[Anonymous No.10604125]

>>10602626
If n = m, gcd(m,n) = n, gcd(m,n)/n = 1, and n choose m = 1. Therefore, the statement will always evaluate to 1.

If n > m:
gcd(n,m) is the product of the prime factors shared by n and m. Therefore gcd(n/m)/n equals 1 over the product of prime factors exclusive to n. Note the this number is necessarily greater than or equal to 1/n.

When n > m, n choose m must be a multiple of n. Therefore n choose m contains all the prime factors of n.

Finally, if you take gcd(n,m)/n times n choose m, you will have a multiple of all the prime factors of n, divided by some number of the prime factors of n. The numerator consists of at least every prime factor of n, while the denominator consists of at most every prime factor of n. Therefore, the factors will cancel and you will be left with an integer (possibly 1, but in most cases larger).

[Anonymous No.10604133]

>>10602996
>Isn't easier to remember why the binomial coefficients are called BINOMIAL coefficients?
Yes but why is the "binomial coefficient" in the sense of the coefficient of x^{n-k}y^k in (x+y)^n equal to n!/k!(n-k)! ?
It is not completely clear from the definition that these quantities are the same. That is what I was doing above (with another definition).
Your polynomial argument can be milked a bit more to actually yield the identity between the two definitions of binomial coefficient but you will need a combinatorial argument at one point, which will probably resemble the one I gave above.

[Anonymous No.10604138]

>>10604125
>gcd(n,m) is the product of the prime factors shared by n and m
with multiplicity right ?
>When n > m, n choose m must be a multiple of n.
nope, eg. [math]{6 \choose 3} = 20[/math]

[Sage No.10604139]

>>10604125
>When n > m, n choose m must be a multiple of n
Take n = 4, m = 2

[Anonymous No.10604142]

>>10604139
I didn't actually sage btw. Just forgot to remove the name

[Anonymous No.10604242]

>>10602626
It suffices to prove that, for each prime [math]p[/math], we have [math]v_p(\frac{n}{gcd(m,n)}) \le v_p\left({n \choose m}\right)[/math], where [math]v_p(n)[/math] denotes the p-adic valuation, ie. the highest power of p that divides n (cf. https://en.wikipedia.org/wiki/P-adic_order).).
Note that we have the following identites, for each positive m and n:
[math]v_p(gcd(m,n)) = \min(v_p(m), v_p(n))[/math]
[math]\displaystyle v_p(n!) = \sum_{j \ge 1}\left\lfloor \frac{n}{p^j}\right\rfloor[/math] (this one is more tricky, I can provide a proof later)
Therefore, it suffices to prove that, for each prime [math]p[/math] such that [math]v_p(m) < v_p(n)[/math], we have [math] v_p\left({n \choose m}\right) \ge v_p(n) - v_p(m)[/math].
So we start with a prime [math]p[/math] such that [math]v_p(m) < v_p(n)[/math].
By the formula above, we have [math]\displaystyle v_p\left({n \choose m}\right) = \sum_{j \ge 1}\left( \left\lfloor \frac{n}{p^j}\right\rfloor - \left\lfloor \frac{m}{p^j}\right\rfloor - \left\lfloor \frac{n-m}{p^j}\right\rfloor\right) \ge \sum_{1 \le j \le v_p(n)}\left( \left\lfloor \frac{n}{p^j}\right\rfloor - \left\lfloor \frac{m}{p^j}\right\rfloor - \left\lfloor \frac{n-m}{p^j}\right\rfloor\right)[/math].
Note that, for each [math]j \in [\![1,v_p(n)]\!][/math], we have [math] \left\lfloor \frac{n}{p^j}\right\rfloor - \left\lfloor \frac{m}{p^j}\right\rfloor - \left\lfloor \frac{n-m}{p^j}\right\rfloor = \frac{n}{p^j} - \left\lfloor \frac{m}{p^j}\right\rfloor - \left\lfloor \frac{n-m}{p^j}\right\rfloor \ge 0[/math] with equality if and only if [math]\frac{m}{p^j}[/math] and [math]\frac{n-m}{p^j}[/math] are integers, that is if and only if [math]p^j[/math] divides [math]m[/math].
(cont.)

[Anonymous No.10604244]

>>10604242
(cont.)

To sum up, the quantity [math]\displaystyle \left\lfloor \frac{n}{p^j}\right\rfloor - \left\lfloor \frac{m}{p^j}\right\rfloor - \left\lfloor \frac{n-m}{p^j}\right\rfloor [/math] is zero whenever [math]1 \le j \le v_p(m)[/math] and at least [math] 1[/math] whenever [math]v_p(m) < j \le v_p(n)[/math].
Hence: [math]\displaystyle v_p\left({n \choose m}\right) \ge \sum_{v_p(m) < j \le v_p(n)} 1 = v_p(n) - v_p(m)[/math], qed.

[Anonymous No.10604310]

>>10604133
I see.

[Anonymous No.10604343]

>>10602626
First, note that if [math]k=\mbox{gcd}(n,m)[/math], then there exist integers [math]a[/math] and [math]b[/math] such that
[eqn]an +bm = k.[/eqn]

Since [math]\frac{m}{n}{n \choose m} = {n-1 \choose m-1} [/math], this gives
[eqn] \frac{k}{n} {n \choose m} = a {n \choose m} + b {n-1 \choose m-1} [/eqn]
which i clearly an integer.

[Anonymous No.10604377]

>>10604343
nice

[Anonymous No.10604478]

>>10604343
Fuck, I did this >>10604242 and now I feel really dumb for not thinking of this. Well done

[Anonymous No.10604647]

>>10604343
Sweet, this tied the pieces together for me.

[Anonymous No.10604792]

>>10602886
>>10602996
>overkill
Not by much, and 'combinatorial proof' is a useful technique that's worth practicing on toy problems

[Anonymous No.10605259]

>>10604343
Nice, did it the same way.

[Anonymous No.10605332]

>>10602824
You can prove something is a integer by proving it counts something, so prove binomial coeficients count something

[Anonymous No.10606683]

>>10602886
What action is that?

[Anonymous No.10606700]

>>10606683
Well [math]\mathfrak S_n[/math] acts naturally on {1,...,n} by permuatation, but this action extends to the set of subsets of {1,...,n} of a given size.
The reason simply being that, if [math]S \subset \{1,...,n\}[/math] and [math]\sigma \in \mathfrak S_n[/math], then [math]\sigma(S) = \{\sigma(i), i \in S\}[/math] is a subset of [math]\{1,...,n\}[/math] of the same size as S (because [math]\sigma[/math] is injective).
So in addition to permuting the elements of {1,...,n}, [math]\mathfrak S_n[/math] also permutes its subsets and preserves size.

[Anonymous No.10606956]

>>10606700
Ah, I just meant to ask what the action is because of the weird letter, my uni always describes the set of permutations as S_n.

[Anonymous No.10606966]

>>10606956
oh yeah it's a gothic S lol