Putnam 1956 B7

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Putnam 1956 B7

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Putnam 1956

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

675 posts

sqrtX

#1 h Jul 5, 2022, 7:28 PM • 1 Y

Y by SatisfiedMagma

The polynomials $P(z)$ and $Q(z)$ with complex coefficients have the same set of numbers for their zeros but possibly different multiplicities. The same is true for the polynomials
$P(z)+1 \;\; \text{and} \;\; Q(z)+1.$ Prove that $P(z)=Q(z).$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1699 posts

#2 h Jul 12, 2022, 2:08 PM • 1 Y

Y by rama1728

Nice problem. We should probably assume that $P,Q$ are not constant. For the proof we use the following
Lemma: Let $P \in \mathbb{C} [x]$ be a non-constant polynomial. Let $d,e$ be the number of distinct roots of $P$ and $P+1$ , respectively. Then $d+e \ge \deg P + 1$ .
Proof of lemma
Back to the main problem: Let $d$ be the number of distinct roots of $P$ (and $Q$ ), and $e$ the number of distinct roots of $P+1$ (and $Q+1$ ).
Then we know from the lemma that $d+e \ge \max \{ \deg P , \deg Q \} + 1$ . However, all these roots are roots of
$P(Q+1)-Q(P+1)=P-Q,$ which has degree $\le \max \{ \deg P , \deg Q \}$ . This is only possible if $P=Q$ .

This post has been edited 1 time. Last edited by Gryphos, Jul 13, 2022, 8:58 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#4 h Sep 27, 2022, 3:25 PM • 1 Y

Y by Mango247

I assume that we're not allowed to have both $P$ and $Q$ constant, since otherwise it doesn't necessarily follow that $P=Q$ (just take $P(x)=1, Q(x)=2$ ).
WLOG suppose $d=\deg P \geq \deg Q$ . Suppose the set of common roots of $P$ and $Q$ is $S$ , and the set of common roots of $P+1$ and $Q+1$ is $T$ . Note that $S$ and $T$ are disjoint, and that every root of $S \cup T$ is a root of $P-Q$ . Thus there are at least $|S|+|T|$ roots of $P-Q$ .
On the other hand, note that if $r$ is a repeated root of $P$ or $P+1$ with multiplicity $m$ , then it is also a root (not necessarily repeated) of $P'$ with multiplicity $m-1$ . Then there are at least $2d-|S|-|T|$ roots of $P'$ , counted with multiplicity. It follows that there are at least $2d$ roots of $P'(P-Q)$ (with multiplicity). But $P'(P-Q)$ has degree at most $2d-1$ , so it must be identically zero. Since $P$ is nonconstant, $P'$ is nonzero, so $P-Q=0 \implies P=Q$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#5 h Jul 3, 2023, 8:54 AM

Y by

Set $\deg P = m$ and $\deg Q = n < m$ , and let $P$ and $Q$ share the roots $r_1, r_2, \cdots, r_k$ . Then $(x-r_1)(x-r_2)\cdots (x-r_k)$ divides the polynomial $R = P-Q$ . Similarly, if $P+1$ and $Q+1$ share the roots $s_1, s_2, \cdots, s_\ell$ , then $(x-s_1)(x-s_2) \cdots (x-s_\ell)$ divides $R$ .

Claim. $k+\ell \geq m+1$ .

The idea is to differentiate. For every root of multiplicity $i$ in $P$ or $P+1$ , it appears with multiplicity $i-1$ in $P'$ . As a result, $P'$ must contain at least total multiplicity $m - k$ of the $r_i$ and $m - \ell$ of the $s_j$ . Hence we have the inequality $m-k + m-\ell \leq m-1 \iff k+\ell \geq m + 1.$
To finish, this implies $R$ has at least $m+1$ roots. But $\deg R = m$ , so it follows $R \equiv 0$ and $P \equiv Q$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1727 posts

OronSH

#6 h Oct 5, 2024, 8:18 PM

Y by

Let $P$ have (larger) degree $p$ and roots $r_1,\dots,r_k$ with multiplicities $a_1,\dots,a_k$ and similarly let $P+1$ have roots $s_1,\dots,s_\ell$ with multiplicities $b_1,\dots,b_\ell$ . Clearly $r_i\ne s_j$ . Consider $P'$ , which must have roots $r_1,\dots,r_k,s_1,\dots,s_\ell$ with multiplicities at least $a_1-1,\dots,a_k-1,b_1-1,\dots,b_\ell-1$ and thus degree $p-1\ge(a_1-1)+\dots+(a_k-1)+(b_1-1)+\dots+(b_\ell-1)=a_1+\dots+a_k+b_1+\dots+b_\ell-k-\ell=2p-k-\ell$ so $k+\ell\ge p+1$ . Now $P(x)-Q(x)$ has $p+1$ roots $r_1,\dots,r_k,s_1,\dots,s_\ell$ but degree $\le p$ , thus it equals zero.

This post has been edited 1 time. Last edited by OronSH, Oct 5, 2024, 8:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

130 posts

#7 h Nov 30, 2024, 4:25 AM

Y by

Let $F$ be the base set of roots for $P,Q$ and let $G$ be the base set of roots for $P+1, Q+1.$ Whenever a lower case letter is used it denotes the degree of the corresponding upper case letter. WLOG let $p \geq q.$ Then note that $P'=(P+1)',$ so we see that as $P,P+1$ share no factors by Euclidean algorithm, that the derivative has at least $p-f$ roots from $P$ and $p-g$ from $P',$ so the degree of the derivative $p-1 \geq 2p-f-g.$ Therefore $f+g\geq p+1,$ or $f+g>p.$ Note that $P-Q$ is some constant $\cdot f(x) \cdot g(x)\cdot k$ for some polynomial $k.$ However note that if $k \neq 0$ then the right side must have a greater degree than the left, therefore $k=0$ and $P=Q.\blacksquare$

This post has been edited 1 time. Last edited by Martin2001, Nov 30, 2024, 4:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

721 posts

#8 h Feb 25, 2025, 6:43 PM

Y by

College math hits different

Attachments:

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a