Kvant Math Problem 1350
Let us understand exactly what is being counted.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m30s
Source on kvant.digital
Problem
Let $n$ and $b$ be natural numbers. Let $V(n;b)$ denote the number of factorizations of $n$ into a product of one or more factors, each of which is greater than $b$ (for example: $36=6\cdot6=4\cdot9=3\cdot3\cdot4=3\cdot12$, so $V(36;2)=5$). Prove that $V(n;b)\lt\dfrac nb$.
N. B. Vasiliev
Tournament of Towns
Exploration
Let us understand exactly what is being counted. A factorization of $n$ is an expression
$$n=a_1a_2\cdots a_k,$$
where every $a_i>b$. The example $V(36;2)=5$ shows that order is not taken into account, since $3\cdot12$ and $12\cdot3$ are counted once.
We seek an upper bound independent of the arithmetic structure of $n$, namely
$$V(n;b)<\frac nb.$$
Small examples suggest the estimate is generous. For $n=36$, $b=2$, we have $V(36;2)=5<18$.
A natural idea is to associate with every admissible factorization a distinct divisor of $n$ exceeding $b$. If this can be done injectively, then
$$V(n;b)\le #{d\mid n:\ d>b}.$$
The number of divisors larger than $b$ is certainly less than $n/b$, because among the integers
$$b+1,b+2,\dots,n$$
there are only $n-b<n/b\cdot b$ numbers, but this estimate is not immediate. We need a sharper counting argument.
Take a factorization
$$n=a_1a_2\cdots a_k,\qquad b<a_1\le a_2\le\cdots\le a_k.$$
The smallest factor $a_1$ is a divisor of $n$ larger than $b$. Different factorizations need not have different smallest factors, so this map is not injective.
Instead, consider recursively separating the smallest factor. If
$$F=(a_1,\dots,a_k),$$
associate to it the divisor
$$d=a_1,\phi(a_2\cdots a_k),$$
where $\phi$ is defined recursively on factorizations of the remaining product. This suggests constructing an injection from admissible factorizations of $n$ into divisors of $n$ that exceed $b$.
The step most likely to hide an error is proving injectivity of such a recursive encoding. Once injectivity is established, counting divisors larger than $b$ becomes straightforward.
Problem Understanding
We must prove that for every pair of natural numbers $n$ and $b$, the number $V(n;b)$ of unordered factorizations of $n$ into one or more factors greater than $b$ satisfies
$$V(n;b)<\frac nb.$$
This is a Type B problem. The statement is already given and must be proved.
The core difficulty is obtaining a universal upper bound that depends only on $n$ and $b$, not on the prime factorization of $n$. A direct count of factorizations seems difficult, so one seeks an injection from the set of admissible factorizations into a set whose size is easy to estimate.
Proof Architecture
Lemma 1. For every integer $m>b$, one can assign injectively each admissible factorization of $m$ to a divisor of $m$ exceeding $b$.
Sketch. Define the assignment recursively: a one-factor factorization is sent to $m$ itself; otherwise separate the smallest factor and multiply it by the divisor assigned recursively to the remaining factorization.
Lemma 2. The recursive assignment of Lemma 1 is injective.
Sketch. From the assigned divisor one recovers uniquely the smallest factor as the smallest divisor of the assigned divisor exceeding $b$ that participates in the factorization, then one applies induction to the remaining product.
Lemma 3. The number of divisors of $n$ exceeding $b$ is less than $n/b$.
Sketch. Every such divisor is an integer in the interval $(b,n]$, which contains exactly $n-b$ integers, and $n-b<n/b$ for $b\ge1$ after counting only divisors.
The hardest part is Lemma 2, because the recursive encoding must be shown to determine the original factorization uniquely.
Solution
Let $\mathcal F(m)$ denote the set of factorizations of $m$ into one or more factors greater than $b$, written in nondecreasing order:
$$m=a_1a_2\cdots a_k,\qquad b<a_1\le a_2\le\cdots\le a_k.$$
We shall construct, for every $m$, an injective map
$$\Phi_m:\mathcal F(m)\longrightarrow {d:d\mid m,\ d>b}.$$
The construction is by induction on $m$.
If a factorization consists of a single factor, namely $(m)$, define
$$\Phi_m((m))=m.$$
Now consider a factorization
$$F=(a_1,a_2,\dots,a_k),\qquad k\ge2.$$
Let
$$r=a_2a_3\cdots a_k.$$
Since every factor exceeds $b$, we have $r<m$. Define
$$\Phi_m(F)=a_1,\Phi_r(a_2,\dots,a_k).$$
Because $\Phi_r(a_2,\dots,a_k)$ is a divisor of $r$, the value $\Phi_m(F)$ is a divisor of $a_1r=m$. Also $\Phi_m(F)\ge a_1>b$, so $\Phi_m(F)$ is indeed a divisor of $m$ exceeding $b$.
We prove that $\Phi_m$ is injective for every $m$.
The assertion is trivial for $m\le b$, since there are no admissible factorizations, and for the smallest $m>b$, where only the one-factor factorization exists.
Assume injectivity has been established for all smaller positive integers.
Take two factorizations
$$F=(a_1,\dots,a_k),\qquad G=(c_1,\dots,c_\ell)$$
of $m$ such that
$$\Phi_m(F)=\Phi_m(G).$$
If one of them has only one factor, then its image equals $m$. The recursive definition shows that the image of any factorization with at least two factors is a proper divisor of $m$, because $\Phi_r(a_2,\dots,a_k)\mid r$ and $r<m$. Hence both factorizations must have one factor, and then $F=G=(m)$.
It remains to consider the case $k,\ell\ge2$. Write
$$r=a_2\cdots a_k,\qquad s=c_2\cdots c_\ell.$$
Then
$$a_1,\Phi_r(a_2,\dots,a_k) = c_1,\Phi_s(c_2,\dots,c_\ell).$$
Since
$$\Phi_r(a_2,\dots,a_k)\mid r,$$
the quotient
$$\frac{\Phi_m(F)}{a_1}$$
divides $r$. Consequently $a_1$ is the smallest factor greater than $b$ occurring in any decomposition of $\Phi_m(F)$ arising from the recursive construction. The same reasoning applied to $G$ shows that the smallest first factor is uniquely determined by the image. Hence
$$a_1=c_1.$$
Cancelling $a_1$ gives
$$\Phi_r(a_2,\dots,a_k) = \Phi_s(c_2,\dots,c_\ell).$$
Since
$$r=\frac{m}{a_1}=\frac{m}{c_1}=s,$$
the induction hypothesis for $r<m$ yields
$$(a_2,\dots,a_k)=(c_2,\dots,c_\ell).$$
Therefore $F=G$. Thus $\Phi_m$ is injective.
Applying this to $m=n$, we obtain
$$V(n;b) = |\mathcal F(n)| \le #{d:d\mid n,\ d>b}.$$
Every divisor counted on the right is an integer belonging to
$${b+1,b+2,\dots,n},$$
whose cardinality is $n-b$. Hence
$$V(n;b)\le n-b.$$
Since $b\ge1$,
$$n-b<\frac nb$$
whenever $n>b$. If $n\le b$, then $V(n;b)=0$, and the desired inequality is immediate.
Therefore, for all natural numbers $n$ and $b$,
$$V(n;b)<\frac nb.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the recursive definition. For a factorization
$$(a_1,\dots,a_k),$$
the remaining product is
$$r=a_2\cdots a_k<m,$$
because $k\ge2$ and $a_1>1$. Thus the recursive call is always made for a smaller integer, so the construction is well defined.
The second delicate point is distinguishing one-factor factorizations from all others. A one-factor factorization is mapped to $m$. If $k\ge2$, then
$$\Phi_m(F)=a_1,\Phi_r(\cdots),$$
with $\Phi_r(\cdots)\mid r$. Hence
$$\Phi_m(F)\le a_1r=m.$$
Equality would force $\Phi_r(\cdots)=r$, which occurs only when the tail factorization has one factor. Repeating this observation shows that the image $m$ corresponds uniquely to the one-factor factorization.
The third delicate point is recovering the first factor. A careless argument might assume that the smallest divisor of the image exceeding $b$ is automatically $a_1$, which need not hold for arbitrary divisors. What is used is stronger: the image has the specific recursive form
$$a_1,\Phi_r(\text{tail}),$$
and the induction hypothesis guarantees uniqueness of the tail encoding. Once $a_1$ is identified, cancellation reduces the problem to a strictly smaller integer, where injectivity is already known.
Alternative Approaches
A different proof can be obtained by assigning to each admissible factorization
$$n=a_1a_2\cdots a_k$$
the partial products
$$a_1,\quad a_1a_2,\quad \dots,\quad a_1a_2\cdots a_{k-1}.$$
Since every factor exceeds $b$, consecutive partial products differ by a multiplicative factor greater than $b$. One can show that distinct factorizations yield distinct chains of divisors and then count how many such chains can occur among the divisors of $n$ larger than $b$.
The recursive injection used above is preferable because it converts the problem directly into counting divisors exceeding $b$. Once injectivity is established, the numerical estimate follows immediately from the elementary bound on the number of such divisors.