Kvant Math Problem 83

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m27s
Source on kvant.digital

Problem

Prove that the numbers 1, 2, ..., $n$ cannot be divided into two groups in such a way that the product of the numbers in one group equals the product of the numbers in the other, for any $n$.

Exploration

For small values of $n$, the statement is easy to check directly.

For $n=1$, the only partition is ${1}$ and the empty set, whose products are $1$ and $1$. If empty groups are not allowed, the statement is trivial. The interesting cases begin with $n\ge 2$.

For $n=2$, the products are $1$ and $2$.

For $n=3$, the total product is $6$. If the numbers could be split into two groups with equal products, then the product of all numbers would have to be a square, because it would be the square of the common group product. But $6$ is not a square.

This suggests examining the total product

$$1\cdot2\cdot\ldots\cdot n=n!.$$

If a partition with equal products existed, then

$$n!=P^2$$

for some integer $P$. Thus the problem reduces to showing that $n!$ is never a perfect square for $n\ge2$.

Testing several values,

$$2!=2,\quad 3!=6,\quad 4!=24,\quad 5!=120,$$

none is a square. The crucial question is why this remains true for every $n$.

A natural idea is to use a prime larger than $n/2$. Such a prime can occur only once among the factors $1,2,\dots,n$, so its exponent in $n!$ is exactly $1$, which prevents $n!$ from being a square. The existence of a prime between $n/2$ and $n$ is precisely Bertrand's theorem. This appears to be the key step.

The point most likely to hide an error is the claim that a prime $p$ with $n/2<p\le n$ contributes exponent exactly $1$ to $n!$. One must check carefully that no multiple $2p,3p,\dots$ can also lie among $1,\dots,n$.

Problem Understanding

We must prove that for no positive integer $n$ can the numbers

$$1,2,\dots,n$$

be partitioned into two groups whose products are equal.

This is a Type B problem, a pure proof.

The core difficulty is to show that the total product

$$n!$$

cannot be the square of an integer. Once that is established, an equal-product partition is impossible, because the product of all numbers would then be the square of the common product.

Proof Architecture

First, show that if the numbers can be divided into two groups with equal product $P$, then $n!=P^2$.

Next, use Bertrand's theorem: for every integer $n\ge2$, there exists a prime $p$ satisfying

$$\frac n2<p\le n.$$

Then prove that the exponent of this prime $p$ in the factorization of $n!$ is exactly $1$, because $p$ appears among the factors $1,\dots,n$, while $2p>n$.

Conclude that $n!$ has a prime with odd exponent, hence is not a perfect square.

The lemma most likely to fail under scrutiny is the assertion that the exponent of $p$ in $n!$ equals $1$; this must be justified directly from the inequality $2p>n$.

Solution

Assume that the numbers

$$1,2,\dots,n$$

can be divided into two groups whose products are equal.

Let the common product be $P$. Since every number from $1$ to $n$ belongs to exactly one of the two groups, the product of all numbers is

$$1\cdot2\cdot\ldots\cdot n=P\cdot P=P^2.$$

Hence

$$n!=P^2.$$

It is therefore enough to prove that $n!$ is never a perfect square for any $n\ge2$.

By Bertrand's theorem, for every integer $n\ge2$ there exists a prime number $p$ such that

$$\frac n2<p\le n.$$

Since $p\le n$, the factor $p$ occurs in the product

$$n!=1\cdot2\cdot\ldots\cdot n.$$

Since $p>\frac n2$, we have

$$2p>n.$$

Consequently no multiple of $p$ other than $p$ itself lies among the numbers $1,2,\dots,n$. Therefore the exponent of $p$ in the prime factorization of $n!$ is exactly $1$.

A perfect square has even exponent at every prime. Since the exponent of $p$ in $n!$ is $1$, the number $n!$ is not a perfect square.

This contradicts the equality $n!=P^2$ obtained from the assumed partition.

Hence no partition of the numbers $1,2,\dots,n$ into two groups can have equal products.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the implication from an equal-product partition to the equation $n!=P^2$. If the two groups have product $P$, multiplying the products of the groups reproduces every factor from $1$ to $n$ exactly once. Thus the total product is $P\cdot P$, not merely a multiple of $P^2$.

The second delicate step is the computation of the exponent of the prime $p$. From

$$\frac n2<p,$$

we obtain

$$2p>n.$$

Every multiple of $p$ larger than $p$ is at least $2p$, hence exceeds $n$. Thus among the numbers $1,\dots,n$ the only multiple of $p$ is $p$ itself. The exponent is therefore exactly $1$.

A careless argument might say only that $p$ occurs in $n!$, which is insufficient. Many primes occur several times in a factorial. The inequality $2p>n$ is the precise input that excludes any second occurrence.

Alternative Approaches

Instead of invoking Bertrand's theorem explicitly, one may prove a slightly stronger statement: for every $n\ge2$, the prime factorization of $n!$ contains a prime with odd exponent. One route is to choose the largest prime not exceeding $n$. If one has already established, by a separate argument, that this prime exceeds $n/2$, the rest of the proof is identical.

Another approach uses Legendre's formula for the exponent of a prime in a factorial:

$$v_p(n!)=\left\lfloor\frac np\right\rfloor+\left\lfloor\frac n{p^2}\right\rfloor+\cdots.$$

Choosing a prime $p$ with $n/2<p\le n$ gives

$$v_p(n!)=1.$$

This again shows that $n!$ is not a square. The main proof is preferable because it requires only the elementary observation that no multiple of $p$ beyond $p$ itself can occur among the factors of $n!$.