Occasionally I don’t understand how the pigeonhole principle should be used in some relevant problems. For example the following exercise is supposed to be solved by this principle:
Exercise. Let $n$ be a positive integer that has exactly three prime divisors, and at least seven divisors of the form $p^k$, where $p$ is a prime, and $k$ is a positive integer. Prove that $n$ must be divisible by the cube of an integer that is larger than $1$.
My solution. Toward a contradiction, assume that $n=p_1^{k_1}p_2^{k_2}p_3^{k_3}$ where $k_i\le2$. But this contradicts the hypothesis that $n$ has at least seven divisors of the $p^k$ form.
Maybe this has a solution using the pigeonhole principle that eludes my mind, does it?
P.S: the comments below led me to provide more clarification on the problem. The problem was to solve a specific exercise using the pigeonhole principle, possibly without applying any other proof method like the proof by contradiction method.
Best Answer
I found the answer using the pigeonhole principle, that’s pretty easy:
Let the holes be named $p_1,p_2,p_3$, so we have three boxes. And let the pigeons be the “distinct” renamed prime divisors (after renaming the same primes to make them distinct in the prime factorization of $n$). According to the hypothesis, there are at least $7$ “distinct” prime divisors. As $7\gt 2\times 3$, by the generalized pigeonhole principle there’s at least one hole where there are $2+1$ pigeons.