Page 1 of 1

IMO 2019/P4

Posted: Thu Jul 18, 2019 11:05 pm
by tanmoy
Find all pairs $(k,n)$ of positive integers such that $k!=(2^n-1)(2^n-2)\cdots(2^n-2^{n-1})$

Proposed by Gabriel Chicas Reyes, El Salvador

Re: IMO 2019/P4

Posted: Tue Jul 23, 2019 12:31 am
by Abdullah Al Tanzim
We will show that $(1,1)$ and $(3,2)$ are the only possible pairs.

Claim1: $\lfloor\frac{k}{3}\rfloor =\lfloor\frac{n}{2}\rfloor$
Proof: $k!=(2^n-1)(2^n-2)(2^n-4)......(2^n-2^{n-1})$
$ =2^{\frac{n(n-1)}{2}}(2^n-1)(2^{n-1}-1)(2^{n-2}-1)....(2-1)$ ...............(1)

As $2$ is a primitive root modulo $3^2$, we can say $2$ is a primitive root modulo $3^r$ for all positive integer $r$.
So,for any positive integer $r$, $2.3^{r-1}$ is the smallest positive integer such that $2^{2.3^{r-1}} \equiv 1 ($mod $3.3^{r-1})$

Now, we will use induction.Assume that $\lfloor\frac{k}{3}\rfloor=\lfloor\frac{n}{2}\rfloor= m$ for some integers $k,m,n$.
If we increase $\lfloor\frac{k}{3}\rfloor$ by $1$ which is $\lfloor\frac{k}{3}\rfloor= m+1$ assume that $v_3(k!)$ increases by $m'$ which implies
$v_3(3(m+1))= m' \Rightarrow v_3(m+1)=m'-1$.

As, $2^{2.3^{m'-1}}\equiv 1($mod $3^{m'}$)$\Rightarrow 2^{2.(m+1)}\equiv 1 ($mod $3^{m'})$ we can say $\lfloor\frac{n}{2}\rfloor = m+1$
Initially, for $k=3$, $n$ must be $2$ otherwise both sides in $(1)$ will not be the same.Here, $\lfloor\frac{3}{3}\rfloor = \lfloor\frac{2}{2}\rfloor$

Thus, $\lfloor\frac{k}{3}\rfloor = \lfloor\frac{n}{2}\rfloor$.

Claim2: $n\leq 4$

Proof: $v_2(k!)<k$.
So, $v_2(k!)= \frac{n(n-1)}{2} \Rightarrow$ $\frac{n(n-1)}{2}<k \Rightarrow \frac{2t(2t-1)}{2}< 3t+2$ [let $\lfloor\frac{k}{3}\rfloor=\lfloor\frac{n}{2}\rfloor = t$]
$\Rightarrow t^2<2t+1 \Rightarrow t\leq 2 \Rightarrow n\leq 4$.
Now, by checking for $n\leq 4$ we can easily get that $(1,1)$ and $(3,2)$ are the only solutions.
(Q.E.D.) :D :D