Putnam 1994

Suppose that a sequence $a_1, a_2, a_3, \dots$ satisfies $0 < a_n \leq a_{2n} + a_{2n+1}$ for all $n \geq 1$. Prove that the series $\sum_{n=1}^{\infty} a_n$ diverges.

Let $A$ be the area of the region in the first quadrant bounded by the line $y = \frac{1}{2} x$, the $x$-axis, and the ellipse $\frac{1}{9} x^2 + y^2 = 1$. Find the positive number $m$ such that $A$ is equal to the area of the region in the first quadrant bounded by the line $y = mx$, the $y$-axis, and the ellipse $\frac{1}{9} x^2 + y^2 = 1$.

Show that if the points of an isosceles right triangle of side length 1 are each colored with one of four colors, then there must be two points of the same color whch are at least a distance $2 - \sqrt{2}$ apart.

Let $A$ and $B$ be $2 \times 2$ matrices with integer entries such that $A, A+B, A+2B, A+3B$, and $A+4B$ are all invertible matrices whose inverses have integer entries. Show that $A+5B$ is invertible and that its inverse has integer entries.

Let $(r_n)_{n \geq 0}$ be a sequence of positive real numbers such that $\lim_{n \to \infty} r_n = 0$. Let $S$ be the set of numbers representable as a sum $$r_{i_1} + r_{i_2} + \cdots + r_{i_{1994}},$$ with $i_1 < i_2 < \cdots < i_{1994}$. Show that every nonempty interval $(a,b)$ contains a nonempty subinterval $(c,d)$ that does not intersect $S$.

Let $f_1, \dots, f_{10}$ be bijections of the set of integers such that for each integer $n$, there is some composition $f_{i_1} \circ f_{i_2} \circ \cdots \circ f_{i_m}$ of these functions (allowing repetitions) which maps 0 to $n$. Consider the set of 1024 functions $$\mathcal{F} = \{f_1^{e_1} \circ f_2^{e_2} \circ \cdots \circ f_{10}^{e_{10}}\},$$ $e_i = 0$ or 1 for $1 \leq i \leq 10$. ($f_i^0$ is the identity function and $f_i^1 = f_i$.) Show that if $A$ is any nonempty finite set of integers, then at most 512 of the functions in $\mathcal{F}$ map $A$ to itself.

Find all positive integers $n$ that are within 250 of exactly 15 perfect squares.

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?

Find the set of all real numbers $k$ with the following property: For any positive, differentiable function $f$ that satisfies $f'(x) > f(x)$ for all $x$, there is some number $N$ such that $f(x) > e^{kx}$ for all $x > N$.

For $n \geq 1$, let $d_n$ be the greatest common divisor of the entries of $A^n - I$, where $$A = \begin{pmatrix} 3 & 2 \\ 4 & 3 \end{pmatrix} \text{ and } I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}.$$ Show that $\lim_{n \to \infty} d_n = \infty$.

For any real number $\alpha$, define the function $f_{\alpha}(x) = \lfloor \alpha x \rfloor$. Let $n$ be a positive integer. Show that there exists an $\alpha$ such that for $1 \leq k \leq n$, $$f_\alpha^k(n^2) = n^2 - k = f_{\alpha^k}(n^2).$$

For any integer $n$, set $$n_a = 101a - 100\cdot 2^a.$$ Show that for $0 \leq a,b,c,d \leq 99$, $n_a + n_b \equiv n_c + n_d \pmod{10100}$ implies $\{a,b\} = \{c,d\}$.