Putnam 2003

Let $n$ be a fixed positive integer. How many ways are there to write $n$ as a sum of positive integers, $$n = a_1 + a_2 + \cdots + a_k,$$ with $k$ an arbitrary positive integer and $a_1 \le a_2 \le \cdots \le a_k \le a_1 + 1$? For example, with $n=4$ there are four ways: 4, 2+2, 1+1+2, 1+1+1+1.

Let $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ be nonnegative real numbers. Show that $$(a_1a_2\cdots a_n)^{1/n} + (b_1b_2\cdots b_n)^{1/n} \leq \left[(a_1 + b_1)(a_2 + b_2)\cdots(a_n + b_n)\right]^{1/n}.$$

Find the minimum value of $$| \sin x + \cos x + \tan x + \cot x + \sec x + \csc x |$$ for real numbers $x$.

Suppose that $a, b, c, A, B, C$ are real numbers, $a \neq 0$ and $A \neq 0$, such that $$|ax^2 + bx + c| \leq |Ax^2 + Bx + C|$$ for all real numbers $x$. Show that $$|b^2 - 4ac| \leq |B^2 - 4AC|.$$

A Dyck $n$-path is a lattice path of $n$ upsteps $(1,1)$ and $n$ downsteps $(1,-1)$ that starts at the origin $O$ and never dips below the $x$-axis. A return is a maximal sequence of contiguous downsteps that terminates on the $x$-axis. For example, the Dyck 5-path illustrated has two returns, of length 3 and 1 respectively. Show that there is a one-to-one correspondence between the Dyck $n$-paths with no return of even length and the Dyck $(n-1)$-paths.

For a set $S$ of nonnegative integers, let $r_S(n)$ denote the number of ordered pairs $(s_1, s_2)$ such that $s_1 \in S$, $s_2 \in S$, $s_1 \ne s_2$, and $s_1 + s_2 = n$. Is it possible to partition the nonnegative integers into two sets $A$ and $B$ in such a way that $r_A(n) = r_B(n)$ for all $n$ ?

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 $n$ be a positive integer. Starting with the sequence $1, \frac{1}{2}, \frac{1}{3}, \dots, \frac{1}{n}$, form a new sequence of $n-1$ entries $\frac{3}{4}, \frac{5}{12}, \dots, \frac{2n-1}{2n(n-1)}$ by taking the averages of two consecutive entries in the first sequence. Repeat the averaging of neighbors on the second sequence to obtain a third sequence of $n-2$ entries, and continue until the final sequence produced consists of a single number $x_n$. Show that $x_n < 2/n$.

Show that for each positive integer n, $$n! = \prod_{i=1}^n \mathrm{lcm}\{1, 2, \dots, \lfloor n/i\rfloor\} .$$ (Here $\mathrm{lcm}$ denotes the least common multiple, and $\lfloor x \rfloor$ denotes the greatest integer $\leq x$.)

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

Let $A,B$, and $C$ be equidistant points on the circumference of a circle of unit radius centered at $O$, and let $P$ be any point in the circle's interior. Let $a, b, c$ be the distance from $P$ to $A, B, C$, respectively. Show that there is a triangle with side lengths $a, b, c$, and that the area of this triangle depends only on the distance from $P$ to $O$.

Let $f(x)$ be a continuous real-valued function defined on the interval $[0,1]$. Show that $$\int_0^1 \int_0^1 | f(x) + f(y) | dx dy \geq \int_0^1 |f(x)| dx.$$