pigeonhole principle question about polynomials The product of five given polynomials is a polynomial of degree 21.
Prove that we can choose two of those polynomials so that the degree
of their product is at least nine.
By pigeonhole principle, at least one polynomial will have a degree of at least 5 because $5\cdot 4<21$. I don't know what to do from here.
 A: Assume all pairs of polynomials have the degree of their product at most $8$
There are $\frac{5\cdot 4}{2}=10$ pairs of two polynomials that can be chosen out of the $5$
If you multiply all pairs together you will get a polynomial of a degree at most $80$
But each pair shows up four times in each pair, so the degree of their product is $84$.
A: Suppose every pair of factors has degree of their product at most 8. There are $\binom{5}{2}=10$ such pairs, each factor appearing in exactly 4 of them. Symbolically: call the factors $f_i$, $i\in[5]$, so $\deg f_if_j\le8$ ($i<j$). Now,
$$g=\prod\limits_{i<j}f_if_j=\left(\prod\limits_if_i\right)^4$$
so $\deg g=4\cdot21=84$ by looking at the right-hand side. However, the middle expression is a product of 10 polynomials of degree at most 8, so its degree is at most 80. Contradiction.
A: By generalized pigeon hole principle, there is at least one polynomial $p_1$ with at least degree 5 .
If no two polynomials have a product of degree 9 or more, then $deg(p_1) \leq 8$. Hence $deg(p_2) + deg(p3) + deg(p4) + deg(p5) = 21 - deg(p_1) \geq 13$. Essentially there are at least 13 pigeons and 4 holes so by pigeon hole, there is at least one hole with at least 4 pigeons. Hence there is always a $deg(p_1) \geq 5$ and $deg(p_2) \geq 4$, which proves the statement.
A: You can use (and prove) the stronger form of PP, which states that there given $n$ pigeons in $k$ holes, we can find $l$ holes with at least $ \lceil \frac{ ln}{k} \rceil$ pigeons.
The proof is similar to PP (and is reflected in the rest of the proofs.
A: Assume the contrary that any pair of polynomials taken out the five given polynomials result a product whose degree is less than $9$. Now, if all the polynomials have a degree greater than or equal to $5$ then, the resultant polynomial product will have a degree greater than or equal to $25$. Thus, at least one polynomial will have degree less than $5$. Now, Except this polynomial(which we will call $p(x)$,multiply the other $4$ out there. Their product $P(x)$ will obviously have a degree less than or equal to $16$(Since,the degree of pair product of polynomials is less than $9$ which means less than or equal to $8$). Now, if $h<5$ be the degree of $p(x)$ and and that of $P(x)$ be $d$.Thus,the degree of net product will be $d+h<d+5\leq 16+5=21$ which leads to contradiction.
A: This question already has answers but none of them use the pigeon hole principle (which was the topic of the chapter on which this exercise is in), so I decided to post my answer.
First of all, please rethink what effect polynomial multiplication has on the degree of the result.
Now for the answer:
We use the PHP on the pairs of polynomials $(p_1, \ldots p_5)$: There are 10 of them (5 choose 2) and their possible degrees are between 0 and 8, because otherwise the proposition would hold trivially, giving us a total of 9 possibilities.
By the PHP, there must be two pairs of polynomials $(p_a,p_b)$ and $(p_c,p_d)$ such that: $$\deg(p_a \times p_b) = \deg( p_c \times p_d)$$
If $p_a \neq p_b \neq p_c \neq p_d$: $$\deg(p_a\times p_b) = \deg(p_c \times p_d) = n \to\deg(p_{r}) \geq 21-2n$$ where $p_r$ is the remaining polynomial.
Now: $$\max(\deg(p_a),\deg(p_b)) \geq n/2$$
And thus $$\max(\deg(p_a),\deg(p_b)) + \deg(p_r) \geq 21- 3n/2 \geq 9 \; \forall n \leq 8$$
Else, some polynomial is repeated in the set $\{p_a,p_b,p_c,p_d\}$, we can assume without loss of generality that the $p_a$ and $p_d$ are the repeated polynomial and write: $$\deg( p_a \times p_b) = \deg( p_a \times p_c) \leq 8$$ then $$\deg(p_b) = \deg(p_c) = n \leq 4$$ and $$\deg(p_a) = 8 - n \geq 4$$
finally, $$\deg(p_{r1} \times p_{r2}) = 13 -n \geq 9  $$
$\square$
