1

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.

user1176409
  • 1
  • 2
    Well, what divisors of the form $p^k$ has that got? I see at most ${p_1^1, p_1^2, p_2^1, p_2^2, p_3^1, p_3^2}$. That's only $6$. – lulu Jul 31 '22 at 10:41
  • @lulu that solves the exercise via proof by contradiction. That isn’t my question as explained in the post –  Jul 31 '22 at 11:30
  • 1
    I don't understand. The problem appears to be a triviality. You've got $7$ pigeons (or more) and only $6$ holes. I really don't think it's more subtle than that. – lulu Jul 31 '22 at 11:35
  • This is not the pigeonhole principle. Rather this is the addition principle used in a proof by contradiction –  Jul 31 '22 at 11:49
  • @lulu my answer below explains what I meant –  Jul 31 '22 at 12:25
  • 2
    In many situations like this one, the pigeonhole principle is applied so simply and intuitively that even without explicitly mentioning it, the proof is clear anyway. – Ned Jul 31 '22 at 12:41
  • @Ned the question was not about understanding a proof and recognizing the possibly implicitly applied pigeonhole principle. Rather I needed to find such a solution –  Jul 31 '22 at 12:45

1 Answers1

0

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.

  • 2
    That's pretty much what @lulu told you in the comments. – Gerry Myerson Jul 31 '22 at 12:54
  • No, that was just a rephrasing of my proof by contradiction. I needed to explicitly apply the pigeonhole principle. So I found such an answer (also without using the method of proof by contradiction) –  Jul 31 '22 at 12:59
  • Seven pigeons and six holes, or seven pigeons and three holes, what's the difference? – Gerry Myerson Jul 31 '22 at 13:31
  • In this case, pedagogically they’re different. Suppose you’re a teacher and you’re teaching elementary combinatorics to beginning students and the first lesson is on the (generalized) pigeonhole principle. Certainly you would want them to solve the above-mentioned problem like how I did, not by proof by contradiction, because there’s already a direct proof using the pigeonhole principle –  Jul 31 '22 at 13:39
  • Also, what you mentioned as holes are not really holes. Otherwise, say $p_1$ without any power could be the hole holding two “pigeons” and it would not give a cube of an integer –  Jul 31 '22 at 13:42
  • Well, I see no meaningful difference at all between these arguments, but there's nothing wrong with rephrasing the obvious argument the way you have. – lulu Jul 31 '22 at 13:43
  • @lulu probably you have more insight into this principle –  Jul 31 '22 at 13:44
  • My point: in its simplest (and in my view most useful) form, the pigeonhole principle holds that you can't put $n+1$ pigeons in $n$ holes without doubling up some of the holes. Here you have $7$ or more pigeons and $6$ holes, so the principle applies directly. – lulu Jul 31 '22 at 14:04
  • @lulu This exercise is in the subsection dealing exclusively with the generalized pigeonhole principle, so any simplest form using the principle would be similar to my answer –  Jul 31 '22 at 14:16