matematikk.net

La $n$ og $m$ være positive heltall. Vis at $\frac{(2m)!(2n)!}{m!n!(m+n)!}$ er et heltall.

plutarco wrote:La $n$ og $m$ være positive heltall. Vis at $\frac{(2m)!(2n)!}{m!n!(m+n)!}$ er et heltall.

$\large\frac{(2m)!(2n)!}{m!n!(m+n)!}=\frac{(m+1)(m+2)\cdot ...\cdot 2m(n+1)(n+2)\cdot ...\cdot 2n}{(m+n)!}$

så må der vises at dette er et heltall (som er lettere sagt enn gjort :=) ).

Jeg lurer på om ikke jeg har sett denne før, men det var en stund siden, og jeg mener å huske at jeg ikke klarte å løse den da, så jeg tar sjansen på å prøve meg likevel. Velg et primtall p, og la [tex]v_p(n)[/tex] være den største potensen av primtallet p som deler n. Om vi kan vise at [tex]v_p((2m!)(2n!)) \geq v_p(m! n! (m+n)!)[/tex] er vi ferdige, fordi vi da kan forkorte brøken og ende med 1 i nevneren. Vi vet at [tex]v_p(N!) = \sum_{i>0} \lfloor \frac {N} {p^i} \rfloor[/tex] fordi [tex]N!=1\cdot \ldots \cdot N[/tex] og nøyaktig [tex]\lfloor \frac {N} {p} \rfloor[/tex] av faktorene har minst én faktor p, nøyaktig [tex]\lfloor \frac {N} {p^2} \rfloor[/tex] har minst to faktorer p, og så videre. Følgelig er

[tex]v_p((2m)!(2n)!) - v_p(m!n!(m+n)!= v_p((2m)!)+ v_p((2n)!) - v_p(m!)-v_p(n!)-v_p(n+m) =\sum_{i>0} \lfloor \frac {2m} {p^i} \rfloor + \lfloor \frac {2m} {p^i} \rfloor - \lfloor \frac {m} {p^i} \rfloor - \lfloor \frac {n} {p^i} \rfloor - \lfloor \frac {m+n} {p^i} \rfloor[/tex]

Det holder altså å vise at [tex]\lfloor \frac {2m} {a} \rfloor + \lfloor \frac {2n} {a} \rfloor - \lfloor \frac {n} {a} \rfloor - \lfloor \frac {m} {a} \rfloor - \lfloor \frac {m+n} {a} \rfloor \geq 0[/tex] Dette er litt kronglete, men relativt rett frem. Skriv [tex]\frac n a = N + r_n[/tex] der [tex]0 \leq r_n<1[/tex] er desimaldelen av [tex]\frac n a[/tex], og definer tilsvarende [tex]\frac m a = M + r_m[/tex]. Da er [tex]\lfloor \frac {2n} a \rfloor = 2N + \lfloor 2r_n \rfloor[/tex] og tilsvarende for de andre leddende, slik at venstresiden av ulikheten vi vil vise blir [tex](2M+2N-N-M-(M+N)) + \lfloor 2r_m \rfloor + \lfloor 2r_n \rfloor - \lfloor r_n \rfloor - \lfloor r_m \rfloor - \lfloor r_n + r_m \rfloor = \lfloor 2r_n \rfloor + \lfloor 2r_m \rfloor - \lfloor r_n + r_m \rfloor[/tex]. Her er alle ledd enten 0 eller 1, så den eneste måten dette kan bli negativt på er om [tex]\lfloor 2r_n \rfloor = \lfloor 2r_m \rfloor = 0[/tex], som betyr at [tex]r_n, r_m <\frac 1 2 \Rightarrow r_n + r_m < 1 \Rightarrow \lfloor r_n + r_m \rfloor = 0[/tex], og vi er ferdige.

Karl_Erik wrote:Jeg lurer på om ikke jeg har sett denne før

Mulig den har vært postet en gang tidligere her. Husker dessverre ikke helt hvor jeg fant denne oppgaven, men tror det var en gammel IMO-oppgave.

Tror den er fra 104 Number Theory Problems av blant andre Titu Andrescu.