IMO 2019/P4

Discussion on International Mathematical Olympiad (IMO)
tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

IMO 2019/P4

Unread post by tanmoy » Thu Jul 18, 2019 11:05 pm

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
"Questions we can't answer are far better than answers we can't question"

User avatar
Abdullah Al Tanzim
Posts: 20
Joined: Tue Apr 11, 2017 12:03 am
Location: Dhaka, Bangladesh.

Re: IMO 2019/P4

Unread post by Abdullah Al Tanzim » Tue Jul 23, 2019 12:31 am

Solution:
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
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

Post Reply