Faculteit van specifieke vorm

Opgave - IMO 2019 dag 2 vraag 1

Bepaal alle paren $(k,n)$ van positieve gehele getallen zodanig dat
\[
k!=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1}).
\]

Oplossing

Het is eenvoudig om na te gaan dat
\[v_2((2^n-1)(2^n-2)(...)(2^n-2^{n-1})) = v_2(\prod_{i=1}^{n-1}2^i) = \frac{n(n-1)}{2}\]
We weten echter dat $$v_2{(k!)} = \sum_{i=1}^{}\lfloor{\frac{k}{2^i}}\rfloor$$
en er moet dus gelden dat
\[\sum_{i=1}^{}\lfloor{\frac{k}{2^i}}\rfloor = \frac{n(n-1)}{2}\]
Merk echter op dat $k \geq v_2{(k!)}$, dus $k \geq \frac{n(n-1)}{2}$.

Nu zullen we inductief bewijzen dat voor $n\geq 6$ geldt dat $(\frac{n(n-1)}{2})! \geq 2^{n^2}$ want het is duidelijk om in te zien dat
$$(2^n - 1)(2^n-2)(...)(2^n - 2^{n-1}) < 2^{n^2}$$ (elke factor is kleiner dan $2^n$)

Inductiestap:
Eerst bewijzen we dat $15! > 2^{36}$, dit klopt want
\[15! = 2^{11} \cdot 3^7 \cdot 5^3 \cdot 7^2 \cdot 11 \cdot 13\]
Aangezien $3^2 > 2^3$ is $3^6 > 2^9$, en ook is $3 \cdot 11 > 2^5$ en als laatste is $5 \cdot 13 > 2^6$
\[15! > 2^{11} \cdot 2^9 \cdot 2^5 \cdot 2^6 \cdot 5^2 \cdot 7^2\]
Duidelijk is dat $5^2 \cdot 7^2 = (35)^2 > 32$, dus
\[15! > 2^{36}\]

Inductiehypothese:
Stel dat het geldt voor $n=x\geq 6$, waarbij dus
\[(\frac{x(x-1)}{2})! = (\frac{x^2-x}{2})! \geq 2^{x^2}\]
Nu bewijzen we dat
\[(\frac{x^2+x}{2})! \geq 2^{(x+1)^2}\]
\[(\frac{x^2+x}{2})! = (\frac{x^2-x}{2})! \cdot \prod_{i=1}^{x}(\frac{x^2-x}{2} + i)!\]
\[> 2^{x^2} \cdot \prod_{i=1}^{x}(\frac{x^2-x}{2} + i)! > 2^{x^2} \cdot x^x\]
want er geldt voor $x\geq 6$ dat $x <\frac{x^2-x}{2}$.
Nu moeten we alleen nog bewijzen dat $$x^x > \frac{2^{(x+1)^2}}{2^{x^2}} = 2^{2x+1}$$
$$\iff \frac{x^x}{2^{2x}} > 2 \iff (\frac{x}{4})^x > 2$$ wat duidelijk waar is voor $x \geq 6$ en is ons inductiebewijs af. Nu concluderen we dat
\[k! > (\frac{n(n-1)}{2})! > 2^{n^2} > (2^n-1)(2^n-2)(...)(2^n-2^{n-1})\]
en hoeven we alleen $n=1,2,3,4,5$ te controleren waaruit we als enige oplossingen
$(n,k) = (1,1),(3,2)$ halen.