Kvant Math Problem 2866

Verified: yes
Verdicts: PASS + PASS
Solve time: 30m37s
Source on kvant.digital

Problem

The numbers 1, 2, 3, $\ldots$, 127 were divided into two groups. Can the sum of the products of the numbers in these groups end with exactly:

10 zeros;
30 zeros?

K. Sukhov

South Russian Mathematical Olympiad “Assara” (IV)

Exploration

The problem asks whether the integers from $1$ through $127$ can be divided into two groups such that the sum of the products of the numbers in each group ends with exactly ten zeros or exactly thirty zeros. The number of trailing zeros of a natural number is determined by the minimum of the exponents of $2$ and $5$ in its prime factorization, because each factor of $10$ contributes one trailing zero. Among the integers from $1$ to $127$, powers of $2$ are more abundant than powers of $5$, so the feasibility of achieving a given number of trailing zeros is primarily constrained by the distribution of factors of $5$ between the two groups. The problem therefore reduces to constructing a partition for ten trailing zeros and proving impossibility for thirty trailing zeros by analyzing $5$-adic and $2$-adic valuations.

Problem Understanding

Let the two groups be $A$ and $B$, with products $P_A$ and $P_B$. Denote $v_5(P_A) = a$ and $v_5(P_B) = b$, where $v_5(x)$ denotes the exponent of $5$ in the prime factorization of $x$. Since the product of all numbers equals $127!$, it follows that $a + b = v_5(127!)$. The sum $S = P_A + P_B$ satisfies $v_5(S) \ge \min(a, b)$ and $v_5(S) = \min(a, b)$ if the summands do not cancel modulo the smaller power of $5$. The number of trailing zeros of $S$ is given by $\min(v_2(S), v_5(S))$, so to achieve exactly ten trailing zeros, it suffices to find a partition where the smaller $5$-adic valuation among $P_A$ and $P_B$ equals ten and the corresponding $2$-adic valuation is at least ten.

Proof Architecture

The total $5$-adic valuation of $127!$ is first computed using Legendre’s formula. Once the total number of factors of $5$ is known, one analyzes whether it is possible to partition the numbers so that the smaller of $v_5(P_A)$ and $v_5(P_B)$ equals ten. To ensure exactly ten trailing zeros, one must verify rigorously that the sum $S = P_A + P_B$ has $5$-adic valuation exactly ten and $2$-adic valuation at least ten. For thirty trailing zeros, the sum must have $v_5(S) \ge 30$, but the total number of factors of $5$ limits the maximum attainable $5$-adic valuation in any sum, providing a rigorous impossibility argument.

Solution

The $5$-adic valuation of $127!$ is computed using Legendre’s formula:

$v_5(127!) = \left\lfloor \frac{127}{5} \right\rfloor + \left\lfloor \frac{127}{25} \right\rfloor + \left\lfloor \frac{127}{125} \right\rfloor = 25 + 5 + 1 = 31.$

The total number of factors of $5$ in $127!$ is $31$. Let the two groups be $A$ and $B$, with products $P_A$ and $P_B$, and let $v_5(P_A) = a$, $v_5(P_B) = b$. Then $a + b = 31$, and for any partition the sum $S = P_A + P_B$ satisfies $v_5(S) \ge \min(a,b)$, with equality if the two summands do not cancel modulo the smaller power of $5$.

To construct a sum ending with exactly ten zeros, consider the subset

$A = {5, 10, 15, 20, 25, 50, 75, 2, 4, 8, 16}.$

The $5$-adic contributions are $v_5(5) = 1$, $v_5(10) = 1$, $v_5(15) = 1$, $v_5(20) = 1$, $v_5(25) = 2$, $v_5(50) = 2$, and $v_5(75) = 2$, summing to $v_5(P_A) = 10$. The $2$-adic contributions are $v_2(2) = 1$, $v_2(4) = 2$, $v_2(8) = 3$, $v_2(16) = 4$, $v_2(10) = 1$, $v_2(20) = 2$, $v_2(50) = 1$, summing to $v_2(P_A) = 14$. The complementary group $B$ contains the remaining numbers $1,3,6,7,\dots,127\setminus A$, and its product $P_B$ contains the remaining factors of $5$, totaling $v_5(P_B) = 31 - 10 = 21$, and an abundance of factors of $2$, certainly more than $14$.

Let $P_A = 5^{10} u$ and $P_B = 5^{21} v$, where $u$ and $v$ are integers not divisible by $5$. Then

$S = P_A + P_B = 5^{10} u + 5^{21} v = 5^{10} (u + 5^{11} v).$

Since $u$ is not divisible by $5$, the inner term satisfies $u + 5^{11} v \not\equiv 0 \pmod 5$, so $v_5(S) = 10$. For the $2$-adic valuation, $v_2(P_A) = 14 \ge 10$, and $v_2(P_B)$ is certainly larger than $10$, so

$v_2(S) \ge \min(v_2(P_A), v_2(P_B)) \ge 10.$

Therefore the sum $S = P_A + P_B$ has exactly $v_{10}(S) = \min(v_2(S), v_5(S)) = 10$ trailing zeros. This rigorously confirms that the chosen partition produces a sum ending with exactly ten zeros.

For thirty trailing zeros, the maximum possible $5$-adic valuation in the sum is $\min(a,b) \le 15$, since $a + b = 31$. To have $v_5(S) \ge 30$, both $a$ and $b$ would need to be at least $30$, which is impossible. The $2$-adic valuation is abundant, but the number of trailing zeros is limited by the $5$-adic valuation. Consequently, no partition of ${1, 2, \dots, 127}$ can produce a sum ending with thirty zeros.

Verification of Key Steps

The computation $v_5(127!) = 31$ using Legendre’s formula is correct. The construction of the subset $A$ ensures $v_5(P_A) = 10$ and $v_2(P_A) = 14$, which, together with the abundantly large $v_2(P_B)$, guarantees that $v_{10}(S) = 10$. The $5$-adic valuation of the sum is rigorously established by writing $P_A = 5^{10} u$ and $P_B = 5^{21} v$, noting that $u + 5^{11} v$ is not divisible by $5$. The impossibility argument for thirty trailing zeros relies on the additive constraint $a + b = 31$ and is fully justified, since $\min(a,b) \le 15$ prevents the sum from having more than fifteen factors of $5$, making thirty trailing zeros unattainable.

Alternative Approaches

A generating function approach could encode subsets as coefficients of a polynomial and track $5$-adic and $2$-adic valuations combinatorially. Each subset corresponds to a term in the expansion of $\prod_{k=1}^{127} (1 + x^k)$, and the exponent of $x$ encodes the sum over subset products. Analysis of $5$-adic and $2$-adic valuations in this framework could determine feasible sums. This method is more complex than the direct $p$-adic argument combined with explicit partitioning, which immediately demonstrates existence and impossibility with minimal calculation.