Putnam Archive — Algebra

For which real polynomials $p$ is there a real polynomial $q$ such that $$p(p(x)) - x = (p(x) - x)^2 q(x)$$ for all real $x$?

Let $c_0,c_1,c_2,\dots$ be the sequence defined so that $$\frac{1-3x-\sqrt{1-14x+9x^2}}{4} = \sum_{k=0}^\infty c_k x^k$$ for sufficiently small $x$. For a positive integer $n$, let $A$ be the $n$-by-$n$ matrix with $i,j$-entry $c_{i+j-1}$ for $i$ and $j$ in $\{1,\dots,n\}$. Find the determinant of $A$.

Let $n$ be an even positive integer. Let $p$ be a monic, real polynomial of degree $2n$; that is to say, $p(x) = x^{2n} + a_{2n-1} x^{2n-1} + \cdots + a_1 x + a_0$ for some real coefficients $a_0, \dots, a_{2n-1}$. Suppose that $p(1/k) = k^2$ for all integers $k$ such that $1 \leq |k| \leq n$. Find all other real numbers $x$ for which $p(1/x) = x^2$.

For a nonnegative integer $k$, let $f(k)$ be the number of ones in the base 3 representation of $k$. Find all complex numbers $z$ such that $$\sum_{k=0}^{3^{1010}-1} (-2)^{f(k)} (z+k)^{2023} = 0.$$

For a nonnegative integer $n$ and a strictly increasing sequence of real numbers $t_0,t_1,\dots,t_n$, let $f(t)$ be the corresponding real-valued function defined for $t \geq t_0$ by the following properties:

1. (a)
   $f(t)$ is continuous for $t \geq t_0$, and is twice differentiable for all $t>t_0$ other than $t_1,\dots,t_n$;
2. (b)
   $f(t_0) = 1/2$;
3. (c)
   $\lim_{t \to t_k^+} f'(t) = 0$ for $0 \leq k \leq n$;
4. (d)
   For $0 \leq k \leq n-1$, we have $f''(t) = k+1$ when $t_k < t< t_{k+1}$, and $f''(t) = n+1$ when $t>t_n$.

Considering all choices of $n$ and $t_0,t_1,\dots,t_n$ such that $t_k \geq t_{k-1}+1$ for $1 \leq k \leq n$, what is the least possible value of $T$ for which $f(t_0+T) = 2023$?

Determine all ordered pairs of real numbers $(a,b)$ such that the line $y = ax+b$ intersects the curve $y = \ln(1+x^2)$ in exactly one point.

Let $n$ be an integer with $n \geq 2$. Over all real polynomials $p(x)$ of degree $n$, what is the largest possible number of negative coefficients of $p(x)^2$?

Let $n$ be a positive integer. Determine, in terms of $n$, the largest integer $m$ with the following property: There exist real numbers $x_1,\dots,x_{2n}$ with $-1 < x_1 < x_2 < \cdots < x_{2n} < 1$ such that the sum of the lengths of the $n$ intervals $$[x_1^{2k-1}, x_2^{2k-1}], [x_3^{2k-1},x_4^{2k-1}], \dots, [x_{2n-1}^{2k-1}, x_{2n}^{2k-1}]$$ is equal to 1 for all integers $k$ with $1 \leq k \leq m$.

Suppose that $P(x) = a_1 x + a_2 x^2 + \cdots + a_n x^n$ is a polynomial with integer coefficients, with $a_1$ odd. Suppose that $e^{P(x)} = b_0 + b_1 x + b_2 x^2 + \cdots$ for all $x$. Prove that $b_k$ is nonzero for all $k \geq 0$.

Let $\times$ represent the cross product in $\mathbb{R}^3$. For what positive integers $n$ does there exist a set $S \subset \mathbb{R}^3$ with exactly $n$ elements such that $$S = \{v \times w: v, w \in S\}?$$

Find all integers $n$ with $n \geq 4$ for which there exists a sequence of distinct real numbers $x_1,\dots,x_n$ such that each of the sets

forms a 3-term arithmetic progression when arranged in increasing order.

Let $P(x)$ be a polynomial whose coefficients are all either $0$ or $1$. Suppose that $P(x)$ can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that $P(2)$ is a composite integer?

Determine the maximum value of the sum $$S = \sum_{n=1}^\infty \frac{n}{2^n} (a_1 a_2 \cdots a_n)^{1/n}$$ over all sequences $a_1, a_2, a_3, \cdots$ of nonnegative real numbers satisfying $$\sum_{k=1}^\infty a_k = 1.$$

For $j \in \{1, 2, 3, 4\}$, let $z_j$ be a complex number with $|z_j| = 1$ and $z_j \neq 1$. Prove that $$3 - z_1 - z_2 - z_3 - z_4 + z_1 z_2 z_3 z_4 \neq 0.$$

Determine all possible values of the expression $$A^3+B^3+C^3-3ABC$$ where $A, B$, and $C$ are nonnegative integers.

Given real numbers $b_0, b_1, \dots, b_{2019}$ with $b_{2019} \neq 0$, let $z_1,z_2,\dots,z_{2019}$ be the roots in the complex plane of the polynomial $$P(z) = \sum_{k=0}^{2019} b_k z^k.$$ Let $\mu = (|z_1| + \cdots + |z_{2019}|)/2019$ be the average of the distances from $z_1,z_2,\dots,z_{2019}$ to the origin. Determine the largest constant $M$ such that $\mu \geq M$ for all choices of $b_0,b_1,\dots, b_{2019}$ that satisfy $$1 \leq b_0 < b_1 < b_2 < \cdots < b_{2019} \leq 2019.$$

Determine the greatest possible value of $\sum_{i=1}^{10} \cos(3x_i)$ for real numbers $x_1,x_2,\dots,x_{10}$ satisfying $\sum_{i=1}^{10} \cos(x_i) = 0$.

Let $n$ be a positive integer, and let $f_n(z) = n + (n-1) z + (n-2)z^2 + \cdots + z^{n-1}$. Prove that $f_n$ has no roots in the closed unit disk $\{z \in \mathbb{C}\colon |z| \leq 1 \}$.

Given a real number $a$, we define a sequence by $x_0 = 1$, $x_1 = x_2 = a$, and $x_{n+1} = 2x_n x_{n-1} - x_{n-2}$ for $n \geq 2$. Prove that if $x_n = 0$ for some $n$, then the sequence is periodic.

Let $Q_0(x) = 1$, $Q_1(x) = x$, and $$Q_n(x) = \frac{(Q_{n-1}(x))^2 - 1}{Q_{n-2}(x)}$$ for all $n \geq 2$. Show that, whenever $n$ is a positive integer, $Q_n(x)$ is equal to a polynomial with integer coefficients.

Compute $$\log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1+e^{2\pi i a b/2015}) \right)$$ Here $i$ is the imaginary unit (that is, $i^2=-1$).

Let $T$ be the set of all triples $(a,b,c)$ of positive integers for which there exist triangles with side lengths $a,b,c$. Express $$\sum_{(a,b,c) \in T} \frac{2^a}{3^b 5^c}$$ as a rational number in lowest terms.

Let $$P_n(x) = 1 + 2 x + 3 x^2 + \cdots + n x^{n-1}.$$ Prove that the polynomials $P_j(x)$ and $P_k(x)$ are relatively prime for all positive integers $j$ and $k$ with $j \neq k$.

Show that for each positive integer $n$, all the roots of the polynomial $$\sum_{k=0}^n 2^{k(n-k)} x^k$$ are real numbers.

Suppose that the real numbers $a_0, a_1, \dots, a_n$ and $x$, with $0 < x < 1$, satisfy $$\frac{a_0}{1-x} + \frac{a_1}{1-x^2} + \cdots + \frac{a_n}{1 - x^{n+1}} = 0.$$ Prove that there exists a real number $y$ with $0 < y < 1$ such that $$a_0 + a_1 y + \cdots + a_n y^n = 0.$$

Find all pairs of polynomials $p(x)$ and $q(x)$ with real coefficients for which $$p(x) q(x+1) - p(x+1) q(x) = 1.$$

Let $f$ be a real-valued function on the plane such that for every square $ABCD$ in the plane, $f(A)+f(B)+f(C)+f(D)=0$. Does it follow that $f(P)=0$ for all points $P$ in the plane?

A game involves jumping to the right on the real number line. If $a$ and $b$ are real numbers and $b > a$, the cost of jumping from $a$ to $b$ is $b^3-ab^2$. For what real numbers $c$ can one travel from $0$ to $1$ in a finite number of jumps with total cost exactly $c$?

Let $f: \mathbb{R}^2 \to \mathbb{R}$ be a function such that $f(x,y) + f(y,z) + f(z,x) = 0$ for all real numbers $x$, $y$, and $z$. Prove that there exists a function $g: \mathbb{R} \to \mathbb{R}$ such that $f(x,y) = g(x) - g(y)$ for all real numbers $x$ and $y$.

Let $n \geq 3$ be an integer. Let $f(x)$ and $g(x)$ be polynomials with real coefficients such that the points $(f(1), g(1)), (f(2), g(2)), \dots, (f(n), g(n))$ in $\mathbb{R}^2$ are the vertices of a regular $n$-gon in counterclockwise order. Prove that at least one of $f(x)$ and $g(x)$ has degree greater than or equal to $n-1$.

Find all values of $\alpha$ for which the curves $y = \alpha x^2 + \alpha x + \frac{1}{24}$ and $x = \alpha y^2 + \alpha y + \frac{1}{24}$ are tangent to each other.

A repunit is a positive integer whose digits in base 10 are all ones. Find all polynomials $f$ with real coefficients such that if $n$ is a repunit, then so is $f(n)$.

Let $f$ be a polynomial with positive integer coefficients. Prove that if $n$ is a positive integer, then $f(n)$ divides $f(f(n)+1)$ if and only if $n=1$. [Editor's note: one must assume $f$ is nonconstant.]

Let $x_0 = 1$ and for $n \geq 0$, let $x_{n+1} = 3x_n + \lfloor x_n \sqrt{5} \rfloor$. In particular, $x_1 = 5$, $x_2 = 26$, $x_3 = 136$, $x_4 = 712$. Find a closed-form expression for $x_{2007}$. ($\lfloor a \rfloor$ means the largest integer $\leq a$.)

Let $n$ be a positive integer. Find the number of pairs $P, Q$ of polynomials with real coefficients such that $$(P(X))^2 + (Q(X))^2 = X^{2n} + 1$$ and $\deg P > \deg Q$.

Let $k$ be a positive integer. Prove that there exist polynomials $P_0(n), P_1(n), \dots, P_{k-1}(n)$ (which may depend on $k$) such that for any integer $n$, $$\left\lfloor \frac{n}{k} \right\rfloor^k = P_0(n) + P_1(n) \left\lfloor \frac{n}{k} \right\rfloor + \cdots + P_{k-1}(n) \left\lfloor \frac{n}{k} \right\rfloor^{k-1}.$$ ($\lfloor a \rfloor$ means the largest integer $\leq a$.)

Let $n$ be a positive odd integer and let $\theta$ be a real number such that $\theta/\pi$ is irrational. Set $a_k = \tan (\theta + k \pi/n)$, $k=1,2,\dots,n$. Prove that $$\frac{a_1 + a_2 + \cdots + a_n}{a_1 a_2 \cdots a_n}$$ is an integer, and determine its value.

Show that the curve $x^3 + 3xy + y^3 = 1$ contains only one set of three distinct points, $A$, $B$, and $C$, which are vertices of an equilateral triangle, and find its area.

Let $p(z)$ be a polynomial of degree $n$ all of whose zeros have absolute value 1 in the complex plane. Put $g(z) = p(z)/z^{n/2}$. Show that all zeros of $g'(z) = 0$ have absolute value 1.

Find a nonzero polynomial $P(x,y)$ such that $P(\lfloor a \rfloor, \lfloor 2a \rfloor) = 0$ for all real numbers $a$. (Note: $\lfloor \nu \rfloor$ is the greatest integer less than or equal to $\nu$.)

Let $P(x_1,\dots,x_n)$ denote a polynomial with real coefficients in the variables $x_1, \dots, x_n$, and suppose that $$\left( \frac{\partial^2}{\partial x_1^2} + \cdots + \frac{\partial^2}{\partial x_n^2}\right) P(x_1, \dots,x_n) = 0 \quad \mbox{(identically)}$$ % Equation labelled (a) (label to the left of the equation) in AMM version. and that $$x_1^2 + \cdots + x_n^2 \mbox{ divides } P(x_1, \dots, x_n).$$ % Equation labelled (b) (label to the left of the equation) in AMM version. Show that $P=0$ identically.

Show that for any positive integer $n$ there is an integer $N$ such that the product $x_1 x_2 \cdots x_n$ can be expressed identically in the form $$x_1 x_2 \cdots x_n = \sum_{i=1}^N c_i ( a_{i1} x_1 + a_{i2} x_2 + \cdots + a_{in} x_n )^n$$ where the $c_i$ are rational numbers and each $a_{ij}$ is one of the numbers $-1, 0, 1$.

Let $P(x) = c_n x^n + c_{n-1} x^{n-1} + \cdots + c_0$ be a polynomial with integer coefficients. Suppose that $r$ is a rational number such that $P(r) = 0$. Show that the $n$ numbers

are integers.

Let $m$ and $n$ be positive integers. Show that $$\frac{(m+n)!}{(m+n)^{m+n}} < \frac{m!}{m^m} \frac{n!}{n^n}.$$

Let $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ be nonnegative real numbers. Show that

Suppose that $a,b,c,A,B,C$ are real numbers, $a\ne 0$ and $A \ne 0$, such that $$| a x^2 + b x + c | \leq | A x^2 + B x + C |$$ for all real numbers $x$. Show that $$| b^2 - 4 a c | \leq | B^2 - 4 A C |.$$

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

Let $f(z) = a z^4 + b z^3 + c z^2 + d z + e = a(z-r_1)(z-r_2)(z-r_3)(z-r_4)$ where $a,b,c,d,e$ are integers, $a \ne 0$. Show that if $r_1 + r_2$ is a rational number and $r_1 + r_2 \ne r_3 + r_4$, then $r_1 r_2$ is a rational number.

Let $k$ be a fixed positive integer. The $n$-th derivative of $\frac{1}{x^k - 1}$ has the form $\frac{P_n(x)}{(x^k - 1)^{n+1}}$ where $P_n(x)$ is a polynomial. Find $P_n(1)$.

For each integer $m$, consider the polynomial $$P_m(x)=x^4-(2m+4)x^2+(m-2)^2.$$ For what values of $m$ is $P_m(x)$ the product of two non-constant polynomials with integer coefficients?

Find all pairs of real numbers $(x,y)$ satisfying the system of equations

Let $S$ denote the set of rational numbers different from $\{-1,0,1\}$. Define $f:S\rightarrow S$ by $f(x)=x-1/x$. Prove or disprove that $$\bigcap_{n=1}^\infty f^{(n)}(S) = \emptyset,$$ where $f^{(n)}$ denotes $f$ composed with itself $n$ times.

Find polynomials $f(x)$,$g(x)$, and $h(x)$, if they exist, such that for all $x$, $$|f(x)|-|g(x)|+h(x) = \begin{cases} -1 & \mbox{if $x<-1$} \\ 3x+2 & \mbox{if $-1 \leq x \leq 0$} \\ -2x+2 & \mbox{if $x>0$.} \end{cases}$$

Let $p(x)$ be a polynomial that is nonnegative for all real $x$. Prove that for some $k$, there are polynomials $f_1(x),\dots,f_k(x$) such that $$p(x) = \sum_{j=1}^k (f_j(x))^2.$$

Consider the power series expansion $$\frac{1}{1-2x-x^2} = \sum_{n=0}^\infty a_n x^n.$$ Prove that, for each integer $n\geq 0$, there is an integer $m$ such that $$a_n^2 + a_{n+1}^2 = a_m .$$

Let $P(x)$ be a polynomial of degree $n$ such that $P(x)=Q(x)P''(x)$, where $Q(x)$ is a quadratic polynomial and $P''(x)$ is the second derivative of $P(x)$. Show that if $P(x)$ has at least two distinct roots then it must have $n$ distinct roots.

Find the minimum value of $$\frac{(x+1/x)^6-(x^6+1/x^6)-2}{(x+1/x)^3+(x^3+1/x^3)}$$ for $x>0$.

For a positive integer $n$ and any real number $c$, define $x_k$ recursively by $x_0=0$, $x_1=1$, and for $k\geq 0$, $$x_{k+2}=\frac{cx_{k+1}-(n-k)x_k}{k+1}.$$ Fix $n$ and then take $c$ to be the largest value for which $x_{n+1}=0$. Find $x_k$ in terms of $n$ and $k$, $1\leq k\leq n$.

Let $a_{m,n}$ denote the coefficient of $x^n$ in the expansion of $(1+x+x^2)^m$. Prove that for all [integers] $k\geq 0$, $$0\leq \sum_{i=0}^{\lfloor \frac{2k}{3}\rfloor} (-1)^i a_{k-i,i}\leq 1.$$

Given that $\{x_1, x_2, \ldots, x_n\} = \{1, 2, \ldots, n\}$, find, with proof, the largest possible value, as a function of $n$ (with $n \geq 2$), of $$x_1x_2 + x_2x_3 + \cdots + x_{n-1}x_n + x_nx_1.$$

Let $(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$ be the vertices of a convex polygon which contains the origin in its interior. Prove that there exist positive real numbers $x$ and $y$ such that

Evaluate $$\sqrt[8]{2207 - \frac{1}{2207-\frac{1}{2207-\dots}}}.$$ Express your answer in the form $\frac{a+b\sqrt{c}}{d}$, where $a,b,c,d$ are integers.

For which real numbers $c$ is there a straight line that intersects the curve $$x^4 + 9x^3 + cx^2 + 9x + 4$$ in four distinct points?

Let $(x_n)_{n \geq 0}$ be a sequence of nonzero real numbers such that $x_n^2 - x_{n-1}x_{n+1} = 1$ for $n=1,2,3,\dots$. Prove there exists a real number $a$ such that $x_{n+1} = ax_n - x_{n-1}$ for all $n \geq 1$.

Prove that $f(n) = 1-n$ is the only integer-valued function defined on the integers that satisfies the following conditions.

• (i)
  $f(f(n)) = n$, for all integers $n$;
• (ii)
  $f(f(n+2)+2) = n$ for all integers $n$;
• (iii)
  $f(0) = 1$.

Let $p(x)$ be a nonzero polynomial of degree less than 1992 having no nonconstant factor in common with $x^3 - x$. Let $$\frac{d^{1992}}{dx^{1992}} \left( \frac{p(x)}{x^3 - x} \right) = \frac{f(x)}{g(x)}$$ for polynomials $f(x)$ and $g(x)$. Find the smallest possible degree of $f(x)$.

Find all real polynomials $p(x)$ of degree $n \geq 2$ for which there exist real numbers $r_1 < r_2 < \cdots < r_n$ such that

1. $p(r_i) = 0, \qquad i = 1, 2, \dots, n,$ and
2. $p' \left( \frac{r_i + r_{i+1}}{2} \right) = 0 \qquad i = 1, 2, \dots, n-1,$

where $p'(x)$ denotes the derivative of $p(x)$.

Let $a$ and $b$ be positive numbers. Find the largest number $c$, in terms of $a$ and $b$, such that $$a^x b^{1-x} \leq a \frac{\sinh ux}{\sinh u} + b \frac{\sinh u(1-x)}{\sinh u}$$ for all $u$ with $0 < |u| \leq c$ and for all $x$, $0 < x < 1$. (Note: $\sinh u = (e^u - e^{-u})/2$.)