Putnam 1993

The horizontal line $y=c$ intersects the curve $y = 2x - 3x^3$ in the first quadrant as in the figure. Find $c$ so that the areas of the two shaded regions are equal. [Figure not included. The first region is bounded by the $y$-axis, the line $y=c$ and the curve; the other lies under the curve and above the line $y=c$ between their two points of intersection.]

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$.

Let ${\cal P}_n$ be the set of subsets of $\{1, 2, \dots, n\}$. Let $c(n, m)$ be the number of functions $f: {\cal P}_n \to \{1, 2, \dots, m\}$ such that $f(A \cap B) = \min\{f(A), f(B)\}$. Prove that $$c(n, m) = \sum_{j=1}^m j^n.$$

Let $x_1, x_2, \dots, x_{19}$ be positive integers each of which is less than or equal to 93. Let $y_1, y_2, \dots, y_{93}$ be positive integers each of which is less than or equal to 19. Prove that there exists a (nonempty) sum of some $x_i$'s equal to a sum of some $y_j$'s.

Show that

$$\begin{gathered}\int_{-100}^{-10} \left( \frac{x^2 - x}{x^3 - 3x + 1} \right)^2 dx + \\ \int_{\frac{1}{101}}^{\frac{1}{11}} \left( \frac{x^2 - x}{x^3 - 3x + 1} \right)^2 dx + \\ \int_{\frac{101}{100}}^{\frac{11}{10}} \left( \frac{x^2 - x}{x^3 - 3x + 1} \right)^2 dx\end{gathered}$$

is a rational number.

The infinite sequence of 2's and 3's

$$\begin{aligned}&2,3,3,2,3,3,3,2,3,3,3,2,3,3,2,3,3, \\ &3,2,3,3,3,2,3,3,3,2,3,3,2,3,3,3,2,\dots\end{aligned}$$

has the property that, if one forms a second sequence that records the number of 3's between successive 2's, the result is identical to the given sequence. Show that there exists a real number $r$ such that, for any $n$, the $n$th term of the sequence is 2 if and only if $n = 1 + \lfloor rm \rfloor$ for some nonnegative integer $m$. (Note: $\lfloor x \rfloor$ denotes the largest integer less than or equal to $x$.)

Find the smallest positive integer $n$ such that for every integer $m$ with $0 < m < 1993$, there exists an integer $k$ for which $$\frac{m}{1993} < \frac{k}{n} < \frac{m+1}{1994}.$$

Consider the following game played with a deck of $2n$ cards numbered from 1 to $2n$. The deck is randomly shuffled and $n$ cards are dealt to each of two players. Beginning with $A$, the players take turns discarding one of their remaining cards and announcing its number. The game ends as soon as the sum of the numbers on the discarded cards is divisible by $2n+1$. The last person to discard wins the game. Assuming optimal strategy by both $A$ and $B$, what is the probability that $A$ wins?

Two real numbers $x$ and $y$ are chosen at random in the interval (0,1) with respect to the uniform distribution. What is the probability that the closest integer to $x/y$ is even? Express the answer in the form $r+s\pi$, where $r$ and $s$ are rational numbers.

The function $K(x,y)$ is positive and continuous for $0 \leq x \leq 1, 0 \leq y \leq 1$, and the functions $f(x)$ and $g(x)$ are positive and continuous for $0 \leq x \leq 1$. Suppose that for all $x$, $0 \leq x \leq 1$, $$\int_0^1 f(y)K(x,y) dy = g(x)$$ and $$\int_0^1 g(y)K(x,y) dy = f(x).$$ Show that $f(x) = g(x)$ for $0 \leq x \leq 1$.

Show there do not exist four points in the Euclidean plane such that the pairwise distances between the points are all odd integers.

Let $S$ be a set of three, not necessarily distinct, positive integers. Show that one can transform $S$ into a set containing 0 by a finite number of applications of the following rule: Select two of the three integers, say $x$ and $y$, where $x \leq y$ and replace them with $2x$ and $y-x$.