Putnam 2003 B1

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 2003 B1

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

439 posts

#1 h Jun 23, 2011, 12:11 AM • 4 Y

Y by Mathuzb, itslumi, Adventure10, Mango247

Do there exist polynomials $a(x)$ , $b(x)$ , $c(y)$ , $d(y)$ such that $1 + xy + x^2y^2= a(x)c(y) + b(x)d(y)$ holds identically?

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Jun 23, 2011, 1:13 AM • 7 Y

Y by Leooooo, Kezer, Binomial-theorem, Adventure10, Mango247, Doru2718, and 1 other user

The answer is no, that is not possible.

Let $m$ be the maximum degree of any of the polynomials $a, b, c,$ or $d.$ (In practice, it is a little silly to imagine that $m$ could be anything other than $2,$ but it causes no harm in the proof). Write $a(x) = \sum_{k=0}^m a_kx^k,$ with similar notation for $b, c,$ and $d.$ Then
$a(x)c(y) + b(x)d(y) = \sum_{j=0}^m \sum_{j=0}^m (a_jc_k + b_jd_k)x^jy^k.$ This has the structure of a matrix multiplication. In particular, take the $(m + 1) \times 2$ matrix whose columns are the coefficients $a_j$ and $b_j$ and multiply it by the $2 \times (m + 1)$ matrix whose rows are the coefficients $c_k$ and $d_k.$ The result is an $(m + 1) \times (m + 1)$ matrix whose $(j, k)$ entry is $a_jc_k + b_jd_k$ - that is, the coefficient of $x^jy^k$ in the product polynomial. Since the set of these monomials $x^jy^k$ is linearly independent in the set of polynomials, the only way for this to equal a particular polynomial is for each and every of the $(m + 1)^2$ coefficients to be identical. But the polynomial $1 + xy + x^2y^2$ corresponds to the matrix with $1$ ’s in each of the first three elements of the main diagonal and zeros everywhere else. That is, it has the $3 \times 3$ identity matrix in the upper left corner and is otherwise zero. But this is a matrix of rank $3.$ The product of an $(m + 1) \times 2$ matrix by a $2 \times (m + 1)$ matrix must have rank no greater than $2.$ So the identity is not possible.

Z K Y

The post below has been deleted. Click to close.

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

479 posts

#3 h Jul 29, 2011, 7:11 AM • 2 Y

Y by Adventure10, Mango247

Here is an interesting thought:
Is there a partial differential equation whose solutions are precisely the functions of the form $p(x)q(y) + r(x)s(y)$ ?

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#4 h Jul 31, 2011, 6:34 AM • 2 Y

Y by Adventure10, Mango247

An odd doubt occurs to me concerning this problem, and it centers on the words "holds identically."

I always envisioned this problem as being about real polynomials, in which case the issue I'm worried about doesn't arise. But what if these are polynomials over a finite field? Note that a key point in my argument above is the linear independence of the monomials $x^jy^k.$ If by "holds identically" you intend that these be the same elements of the ring $\mathbb{F}[x,y],$ then that independence is a given, and the argument still stands. But what if by "holds identically" you intend that these take on the same values as functions for all $(x,y)?$ Then the monomials $x^jy^k$ might not be independent. If $\mathbb{F}=\mathbb{F}_2,$ the field with two elements, then the set of all functions in $(x,y)$ is a 4-dimensional vector space - and if that is so, then the argument collapses.

That's taking it in a rather different direction than BoyosircuWem's speculation.

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#5 h Jul 31, 2011, 6:45 AM • 5 Y

Y by FlakeLCR, MSTang, MissionModi2019, Adventure10, and 1 other user

The old clear difference between a polynomial (as an object) and a polynomial function (as a recipe). Surely $X$ and $X^2$ as polynomials are distinct, even in $\mathbb{F}_2[X]$ , while as polynomial functions defined on $\mathbb{F}_2$ they coincide. For me, any time the word polynomial is used, we deal with "objects", and so expressions like "equality identically holds" are just an over-emphasizing that we have equality, the same as one talks about the identically null polynomial, instead of just saying the zero polynomial.

Z K Y

The post below has been deleted. Click to close.

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

1502 posts

SCP

#6 h Oct 27, 2012, 2:58 PM • 2 Y

Y by Adventure10, Mango247

Kent Merryfield wrote:

The product of an $(m + 1) \times 2$ matrix by a $2 \times (m + 1)$ matrix must have rank no greater than $2$ .

Why the $(m+1)\times (m+1)$ matrix has a rank of max $2$ / why did that quote holds?

Z K Y

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#7 h Oct 27, 2012, 6:56 PM • 3 Y

Y by SCP, Adventure10, Mango247

Two theorems of linear algebra, both very basic, and which hold for matrices over any field.

If $A$ is $m\times n,$ then $\text{rank}(A)\le\min(m,n).$

$\text{rank}(AB)\le\min(\text{rank}(A),\text{rank}(B)).$

Z K Y

The post below has been deleted. Click to close.

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

1198 posts

#8 h Jul 23, 2014, 6:38 PM • 2 Y

Y by Adventure10, Mango247

An elementary solution but does this work?

Z K Y

The post below has been deleted. Click to close.

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

1276 posts

va2010

#9 h Aug 26, 2015, 3:39 PM • 9 Y

Y by tapir1729, kapilpavase, Mathuzb, Imayormaynotknowcalculus, itslumi, Pluto1708, CyclicISLscelesTrapezoid, Adventure10, Mango247

This problem has a very fast solution:

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

986 posts

Kezer

#10 h Sep 16, 2018, 3:21 PM • 3 Y

Y by methylbenzene, Adventure10, Mango247

I'm almost embarrassed to post my bashy solution after seeing actual nice solutions on this thread. It does seem different than the other proofs here, though.

Suppose $a(x) = a_0+a_1x+\dots+a_nx^n$ , then we can quickly conclude that $b(x) = b_0+b_1x+b_2x^2 - \frac{c(y)}{d(y)} \left(x^3+x^4+\dots+x^n \right)$ for every $y$ and $d(y) \neq 0$ . So $c = d$ . Setting $x=0$ shows that they are a constant which quickly yields a contradiction.

So the degrees of $a,b,c,d$ are all $\leq 2$ . (same argument for $c,d$ ) Setting $a(x) = a_0 + a_1x + a_2x^2, b(x) = b_0 + b_1x+b_2x^2$ and so on gives us a lot of equations to work with by simply comparing the coefficients of the sides of the equation. $a_0c_1+b_0d_1 = a_0c_2+b_0d_2 = a_1c_0+b_1d_0 = a_1c_2+b_1d_2 = a_2c_0+b_2d_0=a_2c_1+b_2d_1 = 0$ If some of $c_0, c_1, c_2$ were $0$ , then we can quickly reach a contradiction - it'll eventually yield $c= 0$ giving $1+xy+x^2y^2 = b(x)d(y)$ . Set $x=0$ , that shows that $d$ is constant, contradiction.

So now we will get $\begin{align*} a_0 &= -b_0 \frac{d_1}{c_1} = -b_0 \frac{d_2}{c_2} \\ a_1 &= -b_1 \frac{d_0}{c_0} = -b_1 \frac{d_2}{c_2} \\ a_2 &= -b_2 \frac{d_0}{c_0} = -b_2 \frac{d_1}{c_1} \end{align*}$ In particular $\frac{d_0}{c_0} = \frac{d_1}{c_1} = \frac{d_2}{c_2}$ . Summing gives $a(x) = -\frac{d_0}{c_0}(b_0+b_1x+b_2x^2) = -\frac{d_0}{c_0}b(x).$ Similarly $c(x) = -\frac{b_0}{a_0}d(x)$ . Hence, we have to solve $1 + xy + x^2y^2 = \left(-\frac{d_0}{c_0}-\frac{b_0}{a_0} \right) b(x)c(y) =: \lambda b(x)c(y)$ It becomes easy now. Set $x=0$ , that shows that $c$ is constant. Contradiction.

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#11 h Nov 27, 2018, 2:36 AM • 1 Y

Y by Adventure10

Storage

Z K Y

The post below has been deleted. Click to close.

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

60 posts

#12 h Apr 10, 2019, 6:49 PM • 4 Y

Y by Arkajit_Ganguly, Pluto1708, Adventure10, Mango247

Since $a(1)c(1) + b(1)d(1) = 3$ , we can assume WLOG that $b(1)d(1) \not = 0$ so that $b(1), d(1) \not =0$ . Now, note that $\begin{align} \label{1} a(\omega)c(\omega) + b(\omega)d(\omega) = 1 + w^2 + w^4 = 0 \\ a(1)c(\omega) + b(1)d(\omega) = 1 + w + w^2 = 0 \\ a(\omega)c(1) + b(\omega)d(1) = 0,\end{align}$ so that $d(\omega) = -a(1)c(\omega)/b(1)$ and $b(\omega) = -a(\omega)c(1)/d(1)$ . If we put, this into $(1)$ , we get $a(\omega)c(\omega)\Big(1 + \frac{a(1)c(1)}{b(1)d(1)}\Big) = 0.$ Thus we must have $a(\omega)c(\omega) = 0$ , so that at least $a(\omega) = 0$ or $c(\omega) = 0$ . WLOG assume $a(\omega) = 0$ , then through $(3)$ we see that $b(\omega) = 0$ and therefore $0 = a(\omega)c(-1) + b(\omega)d(-1) = 1 -\omega + \omega^2 = -2\omega,$ implying such polynomials don't exist.

Z K Y

The post below has been deleted. Click to close.

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

1900 posts

#13 h May 21, 2019, 11:15 AM • 2 Y

Y by Adventure10, Mango247

Kezer wrote:

Suppose $a(x) = a_0+a_1x+\dots+a_nx^n$ , then we can quickly conclude that $b(x) = b_0+b_1x+b_2x^2 - \frac{c(y)}{d(y)} \left(x^3+x^4+\dots+x^n \right)$ for every $y$ and $d(y) \neq 0$ .

Didn't you loose somewhere $1+xy+x^2y^2$ part?
my sol

Z K Y

The post below has been deleted. Click to close.

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

224 posts

#14 h Apr 13, 2025, 12:08 AM • 1 Y

Y by centslordm

The answer is no. Let $A(0)=a_0$ and etc., and let the functional equation be $P(x,y)$ .

If $b_0=0$ , $P(0,y)$ implies $C(y)=\frac{1}{a_0}$ , so $D(y)$ must be nonconstant and $A(x)=a_0$ . However, this implies $(b_1x+b_2x^2)(d_0+d_1y+d_2y^2)=xy+x^2y^2$ , so $b_1d_1=b_2d_2=1$ . In particular, this implies $b_1,d_2\neq0$ , which contradicts the $xy^2$ coefficient $b_1d_2=0$ . $d_0=0$ leads to a similar contradiction.

If $b_0,d_0\neq0$ , $P(0,y)$ and $P(x,0)$ give $D(y)=\frac{1-a_0C(y)}{b_0}$ and $B(x)=\frac{1-c_0A(x)}{d_0}$ , so we can rewrite $P(x,y)$ as $1+xy+x^2y^2=k_1A(x)C(y)+k_2A(x)+k_3C(y)+k_4$ for real $k_i$ . If either of $A$ or $C$ are constant, then it is impossible to have a $xy$ term on the RHS side, but if both are nonconstant, then as above, $k_1a_1c_1=k_1a_2c_2=1$ while $k_1a_1c_2=0$ , contradiction.

(when you do a non lin alg solution in a lin alg unit

)

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a