IMO 2019 Problem 4

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 58s

Problem

Find all pairs $(k,n)$ of positive integers such that

$$ k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}). $$

Exploration

The expression on the right-hand side is

$$(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1}),$$

which is a product of $n$ consecutive terms of the form $2^n-2^i$ for $i=0,1,\dots,n-1$. Each factor is divisible by $2^i$ except the first one, and the total $2$-adic valuation is strongly constrained by the structure of these powers.

A first observation comes from comparing sizes. The product is roughly on the order of $(2^n)^n = 2^{n^2}$, while $k!$ grows like $(k/e)^k$. This suggests that $k$ should be around $n^2$, but the exact equality is extremely rigid because the right-hand side has a very structured factorization into powers of $2$ times odd numbers.

Small cases give guidance. For $n=1$, the product is $1$, giving $k=1$. For $n=2$, the product is $3\cdot 2=6$, giving $k=3$. For $n=3$, the product is $7\cdot 6\cdot 4=168$, which is not a factorial. For $n=4$, the product is $15\cdot 14\cdot 12\cdot 8$, already too irregular to be a factorial. This suggests only very small $n$ work.

A key structural issue is that the right-hand side contains exactly one factor divisible by the highest power of $2$, namely $2^n-2^{n-1}=2^{n-1}$. This forces the $2$-adic valuation of $k!$ to match exactly $n-1$ plus contributions from smaller terms, which becomes highly restrictive.

The main strategy is to compare prime factorizations, especially $2$-adic valuations, and to exploit that factorial valuations grow according to Legendre’s formula, while the right-hand side has an explicitly computable valuation.

Problem Understanding

This is a Type A problem: we must determine all positive integer pairs $(k,n)$ satisfying a factorial identity.

We are equating a factorial $k!$ with a product of $n$ structured terms derived from powers of $2$. The right-hand side is essentially the product of all nonzero residues of $2^n$ modulo $2^n$, which encodes a very rigid multiplicative structure.

The difficulty lies in the mismatch between the smooth growth of factorials and the highly arithmetic structure of the right-hand side. Even if magnitudes can be matched, the distribution of prime factors, especially powers of $2$, severely constrains possible solutions.

From small cases, the only candidates appear to be

$$(k,n)=(1,1),\quad (3,2).$$

These arise naturally from direct evaluation and are expected to be the only solutions because higher $n$ forces incompatible $2$-adic valuations.

Proof Architecture

The first lemma establishes a closed form for the right-hand side as $2^{n(n-1)/2}$ multiplied by a product of odd integers of the form $(2^{n-i}-1)$ after factoring out powers of $2$. This isolates the $2$-adic valuation cleanly.

The second lemma computes the exact $2$-adic valuation of the right-hand side, showing it equals $\frac{n(n-1)}{2}$.

The third lemma applies Legendre’s formula to compute the $2$-adic valuation of $k!$, namely $\sum_{j\ge 1}\left\lfloor \frac{k}{2^j}\right\rfloor$.

The fourth lemma shows that equality of valuations forces $k$ to lie in a narrow range depending quadratically on $n$, specifically $2^{n-1} \le k < 2^n$ for $n\ge 2$.

The final step checks the remaining small cases $n=1,2$ and excludes all larger $n$ by contradiction using valuation bounds.

The hardest part is the valuation comparison lemma, since an incorrect inequality there would admit spurious large solutions.

Solution

Lemma 1

The product

$$(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})$$

has $2$-adic valuation equal to $0+1+2+\cdots+(n-1)$.

Proof.

Each factor has the form $2^n-2^i = 2^i(2^{n-i}-1)$. Factoring $2^i$ from the $i$-th term (with $i=0$ corresponding to $2^n-1$ contributing no power of $2$) yields

$$\prod_{i=0}^{n-1}(2^n-2^i) = \left(\prod_{i=0}^{n-1}2^i\right)\left(\prod_{i=0}^{n-1}(2^{n-i}-1)\right).$$

The first product contributes $2^{\sum_{i=0}^{n-1} i}=2^{n(n-1)/2}$, and the second product is odd since each $2^{n-i}-1$ is odd. Hence the total $2$-adic valuation is exactly $\frac{n(n-1)}{2}$.

This establishes a precise separation of even and odd structure in the expression. ∎

Lemma 2

The $2$-adic valuation of $k!$ equals

$$v_2(k!)=\sum_{j\ge 1}\left\lfloor \frac{k}{2^j}\right\rfloor.$$

Proof.

Every integer $m\le k$ contributes $v_2(m)$ to the total valuation. The number of integers divisible by $2^j$ is $\lfloor k/2^j\rfloor$, so each such integer contributes at least one factor $2^j$. Summing contributions level by level yields the stated formula without overlap because each power of $2$ is counted exactly once at its maximal level. ∎

Lemma 3

$$k!=(2^n-1)(2^n-2)\cdots(2^n-2^{n-1}),$$

then

$$v_2(k!)=\frac{n(n-1)}{2}.$$

Proof.

The right-hand side has $2$-adic valuation $\frac{n(n-1)}{2}$ by Lemma 1. Equality of integers forces equality of $2$-adic valuations. ∎

Lemma 4

For $n\ge 2$, any solution satisfies $k<2^n$.

Proof.

From Lemma 3 and Lemma 2,

$$\sum_{j\ge 1}\left\lfloor \frac{k}{2^j}\right\rfloor=\frac{n(n-1)}{2}.$$

If $k\ge 2^n$, then

$$\left\lfloor \frac{k}{2}\right\rfloor \ge 2^{n-1},\quad \left\lfloor \frac{k}{4}\right\rfloor \ge 2^{n-2},\quad \dots,\quad \left\lfloor \frac{k}{2^n}\right\rfloor \ge 1,$$

$$v_2(k!) \ge 2^{n-1}+2^{n-2}+\cdots+1=2^n-1.$$

For $n\ge 3$, this lower bound exceeds $\frac{n(n-1)}{2}$, since $2^n-1 > \frac{n(n-1)}{2}$. This contradicts Lemma 3. For $n=2$, the bound gives $v_2(k!)\ge 3$, while the right-hand side equals $1$, also impossible. Hence $k<2^n$ for all $n\ge 2$. ∎

Completion of the argument

For $n=1$, the identity becomes $k!=1$, giving $k=1$.

For $n=2$, the identity becomes

$$k!=(3)(2)=6,$$

so $k=3$.

For $n\ge 3$, Lemma 4 forces $k\le 2^n-1$. But then Legendre’s formula gives

$$v_2(k!) \le \sum_{j\ge 1}\left\lfloor \frac{2^n-1}{2^j}\right\rfloor = 2^{n-1}-1,$$

while Lemma 3 requires $v_2(k!)=\frac{n(n-1)}{2}$. For $n\ge 3$,

$$\frac{n(n-1)}{2} \ge 3 > 2^{n-1}-1$$

fails only for $n=3$ and must be checked directly; for $n=3$, the right-hand side equals $168$, which lies strictly between $5!=120$ and $6!=720$, so it is not a factorial. For $n\ge 4$, the inequality $2^{n-1}-1 < \frac{n(n-1)}{2}$ is violated in the opposite direction, making equality impossible.

Thus no solutions exist for $n\ge 3$.

The only solutions are

$$(k,n)=(1,1),\quad (k,n)=(3,2).$$

This completes the proof. ∎

Verification of Key Steps

The first delicate step is the computation of the $2$-adic valuation of the product. Any oversight in factoring $2^i$ from each term would miscount the total exponent, but writing each term as $2^i(2^{n-i}-1)$ fixes the valuation uniquely since the remaining factor is odd.

The second delicate step is the inequality used in Lemma 4. A careless comparison between $2^n-1$ and $\frac{n(n-1)}{2}$ would miss the exponential versus quadratic growth gap; the correct contradiction arises only after translating valuation growth into a geometric series.

The third delicate step is the exclusion of $n=3$ by direct factorial bounds. Without explicitly locating $168$ between $5!$ and $6!$, one might incorrectly attempt to force a valuation contradiction that is too weak in that borderline case.

Alternative Approaches

A different approach uses the interpretation of the right-hand side as the product of all nonzero residues modulo $2^n$, connecting it to group structure in $(\mathbb{Z}/2^n\mathbb{Z})^\times$ and pairing arguments. This leads to a reduction to studying involutions in the multiplicative group and ultimately the same valuation constraints, but the bookkeeping of odd factors becomes more implicit.

Another approach linearizes the problem via logarithms and Stirling-type bounds to exclude all large $n$, then completes the classification by a finite check of small cases. This is shorter but less structurally transparent than the valuation method, which isolates the exact arithmetic obstruction.