For positive integer $k>1$, let $f(k)$ be the number of ways of factoring $k$ into product of positive integers greater than $1$ (The order of factors are not countered, for example $f(12)=4$, as $12$ can be factored in these $4$ ways: $12,2\cdot 6,3\cdot 4, 2\cdot 2\cdot 3$. Prove: If $n$ is a positive integer greater than $1$, $p$ is a prime factor of $n$, then $f(n)\leq \frac{n}{p}$
Problem
Source: 2014 China TST 3 Day 2 Q6
Tags: induction, number theory proposed, number theory
07.04.2014 02:21
Clearly we can just assume that $p$ is the largest prime dividing $n$. We'll call the ways to split it up partitions $f(n)$. Lemma 1: $\phi(n) \ge \frac{n}{p}$ for the largest prime $p | n$. Proof: This is trivial. $\phi(n) = n \prod_{q|n} \frac{q-1}{q} \ge n \prod_{i \le p} \frac{i-1}{i} = \frac{n}{p}$. Now we use induction. By the hypothesis, $f(x) \le \frac{x}{p} \le \phi(x)$. Take the largest prime factor $p$ of a number $np$. Now for this $p$ look at which factor of the partition that its in. Say that it is part of $pd$. Then the remaining $n/d$ can be partitioned in $f(n/d)$ ways. Note that if $p$ is not the unique largest, we are overcounting by a lot, so summing over all divisors $d$ of $n$, $f(np) \le \sum_{d|n} f(d) \le \sum_{d|n} \phi(d) = n$ which is well known. So our induction is complete.
08.03.2015 02:24
Let $e_1 \le e_2 \le ... \le e_{\ell}$ be the exponents in the prime factorization of $n$ and let $2=p_1<p_2<...$ be all the prime numbers, in order. Suppose we have $\ell$ bags of balls, and the bags have $e_1, ..., e_{\ell}$ balls, respectively. All the balls in one bag are identical, but two balls in different bags are distinct. Let $f(e_1,...,e_{\ell})$ be the number of ways to put all of these balls into baskets, such that the order of the baskets doesn't matter, and if two identical balls switch places then the division is considered the same. Clearly it is enough to prove $f(e_1,...,e_{\ell}) \le p_{\ell}^{e_1-1}p_{\ell-1}^{e_2}...p_2^{e_{\ell-1}}p_1^{e_{\ell}}$, but, since $p_i \ge i+1$, I will prove that $f(e_1,...,e_{\ell}) \le 2^{e_{\ell}}3^{e_{\ell-1}}4^{e_{\ell-2}}...\ell^{e_2}(\ell+1)^{e_1-1}$. Put the bags in order, starting from smallest to biggest: $B_1,...,B_{\ell}$. Now, number the balls in $B_i$ in any order: $b_{i,1},...,b_{i,e_i}$. Begin with ball $b_{1,1}$, and throw it into any basket. Now, assume you have already thrown $b_{i',j'}$ for $i'<i$ and for $i'=i,j' \le j$. Let $B$ be the basket in which $b_{i,j}$ is. You have $\ell-i+2$ options: > to throw ball $b_{i,j+1}$ into $B$ (notice this is only a possibility if $j < e_i$). > to decide that you will throw $b_{i+1,k}$ into $B$ (where $k$ is the minimal number such that $b_{i+1,k}$ hasn't already been decided where we will throw it) and don't throw any $b_{i,j'}$ for $j'>j$. > to decide that you will throw $b_{i+2,k}$ into $B$ (where $k$ is the minimal number such that $b_{i+2,k}$ hasn't already been decided where we will throw it) and don't throw any $b_{i,j'}$ (for $j'>j$) nor $b_{i+1,j'}$ > ... > to decide that you will throw $b_{\ell,k}$ into $B$ (where $k$ is the minimal number such that $b_{\ell,k}$ hasn't already been decided where we will throw it) and don't throw any $b_{i,j'}$ (for $j'>j$) nor $b_{i',j}$ where $i'>i$. > Don't throw any more balls into the basket. (note that, if for one of those options, no such $k$ exists, then there are actually less options than $\ell-i+2$). For each ball you will make a decision. A ball in $B_i$ has $i+1$ options except the last one, which only has $i$ options. Notice that every way to put all of these balls into baskets corresponds to exactly one sequence of decisions. This proves $\boxed{f(e_1,...,e_{\ell}) \le 2^{e_{\ell}}3^{e_{\ell-1}}4^{e_{\ell-2}}...\ell^{e_2}(\ell+1)^{e_1-1}}$. , as desired.
20.08.2021 08:29
China TST 2014 wrote: For positive integer $k>1$, let $f(k)$ be the number of ways of factoring $k$ into product of positive integers greater than $1$ (The order of factors are not countered, for example $f(12)=4$, as $12$ can be factored in these $4$ ways: $12,2\cdot 6,3\cdot 4, 2\cdot 2\cdot 3$. Prove: If $n$ is a positive integer greater than $1$, $p$ is a prime factor of $n$, then $f(n)\leq \frac{n}{p}$