Putnam 1995

Let $S$ be a set of real numbers which is closed under multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$). Let $T$ and $U$ be disjoint subsets of $S$ whose union is $S$. Given that the product of any three (not necessarily distinct) elements of $T$ is in $T$ and that the product of any three elements of $U$ is in $U$, show that at least one of the two subsets $T,U$ is closed under multiplication.

For what pairs $(a,b)$ of positive real numbers does the improper integral $$\int_{b}^{\infty} \left( \sqrt{\sqrt{x+a}-\sqrt{x}} - \sqrt{\sqrt{x}-\sqrt{x-b}} \right) dx$$ converge?

The number $d_{1}d_{2}\dots d_{9}$ has nine (not necessarily distinct) decimal digits. The number $e_{1}e_{2}\dots e_{9}$ is such that each of the nine 9-digit numbers formed by replacing just one of the digits $d_{i}$ is $d_{1}d_{2}\dots d_{9}$ by the corresponding digit $e_{i}$ ($1 \leq i \leq 9$) is divisible by 7. The number $f_{1}f_{2}\dots f_{9}$ is related to $e_{1}e_{2}\dots e_{9}$ is the same way: that is, each of the nine numbers formed by replacing one of the $e_{i}$ by the corresponding $f_{i}$ is divisible by 7. Show that, for each $i$, $d_{i}-f_{i}$ is divisible by 7. [For example, if $d_{1}d_{2}\dots d_{9} = 199501996$, then $e_{6}$ may be 2 or 9, since $199502996$ and $199509996$ are multiples of 7.]

Suppose we have a necklace of $n$ beads. Each bead is labeled with an integer and the sum of all these labels is $n-1$. Prove that we can cut the necklace to form a string whose consecutive labels $x_{1},x_{2},\dots,x_{n}$ satisfy $$\sum_{i=1}^{k} x_{i} \leq k-1 \text{for} k=1,2,\dots,n.$$

Let $x_{1},x_{2},\dots,x_{n}$ be differentiable (real-valued) functions of a single variable $t$ which satisfy

$$\begin{aligned}\frac{dx_{1}}{dt} &= a_{11}x_{1} + a_{12}x_{2} + \cdots + a_{1n}x_{n} \\ \frac{dx_{2}}{dt} &= a_{21}x_{1} + a_{22}x_{2} + \cdots + a_{2n}x_{n} \\ \vdots && \vdots \\ \frac{dx_{n}}{dt} &= a_{n1}x_{1} + a_{n2}x_{2} + \cdots + a_{nn}x_{n}\end{aligned}$$

for some constants $a_{ij}>0$. Suppose that for all $i$, $x_{i}(t) \to 0$ as $t \to \infty$. Are the functions $x_{1},x_{2},\dots,x_{n}$ necessarily linearly dependent?

Suppose that each of $n$ people writes down the numbers 1,2,3 in random order in one column of a $3 \times n$ matrix, with all orders equally likely and with the orders for different columns independent of each other. Let the row sums $a,b,c$ of the resulting matrix be rearranged (if necessary) so that $a \leq b \leq c$. Show that for some $n \geq 1995$, it is at least four times as likely that both $b=a+1$ and $c=a+2$ as that $a=b=c$.

For a partition $\pi$ of $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$, let $\pi(x)$ be the number of elements in the part containing $x$. Prove that for any two partitions $\pi$ and $\pi'$, there are two distinct numbers $x$ and $y$ in $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ such that $\pi(x) = \pi(y)$ and $\pi'(x) = \pi'(y)$. [A partition of a set $S$ is a collection of disjoint subsets (parts) whose union is $S$.]

An ellipse, whose semi-axes have lengths $a$ and $b$, rolls without slipping on the curve $y = c \sin \left( \frac{x}{a} \right)$. How are $a,b,c$ related, given that the ellipse completes one revolution when it traverses one period of the curve?

To each positive integer with $n^{2}$ decimal digits, we associate the determinant of the matrix obtained by writing the digits in order across the rows. For example, for $n=2$, to the integer 8617 we associate $\det \left( \begin{array}{cc} 8 & 6 \\ 1 & 7 \end{array} \right) = 50$. Find, as a function of $n$, the sum of all the determinants associated with $n^{2}$-digit integers. (Leading digits are assumed to be nonzero; for example, for $n=2$, there are 9000 determinants.)

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.

A game starts with four heaps of beans, containing 3,4,5 and 6 beans. The two players move alternately. A move consists of taking either

a) one bean from a heap, provided at least two beans are left behind in that heap, or

b) a complete heap of two or three beans.

The player who takes the last heap wins. To win the game, do you want to move first or second? Give a winning strategy.

For a positive real number $\alpha$, define $$S(\alpha) = \{ \lfloor n\alpha \rfloor : n = 1,2,3,\dots \}.$$ Prove that $\{1,2,3,\dots\}$ cannot be expressed as the disjoint union of three sets $S(\alpha), S(\beta)$ and $S(\gamma)$. [As usual, $\lfloor x \rfloor$ is the greatest integer $\leq x$.]