\documentclass{article}
\usepackage{amssymb,amsmath}

\hyphenation{Birk-hoff}

\def\course{Putnam Practice}
\def\semester{Fall 2003}
\def\PostscriptAdjustment{\addtolength{\topmargin}{49pt}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\def\psfile#1#2#3{\begin{center}
\begin{figure}[ht] \begin{center}
\ \psfig{figure=#1.ps,height=#2in,width=#3in}
\end{center}
\end{figure}
\end{center}}
\def\exp#1{^{\raise3pt\hbox{$\scriptstyle{#1}$}}}
\def\tothe#1#2{^{\raise#1pt\hbox{$\scriptstyle{#2}$}}}
\def\sub#1#2{_{\raise-#1pt\hbox{$\scriptstyle{#2}$}}}
\def\lh{\stackrel{\mathrm{\scriptscriptstyle{L'H}}}{=}}
\def\arccsc{\mathrm{arccsc}\,}
\def\arcsec{\mathrm{arcsec}\,}
\def\arccot{\mathrm{arccot}\,}
\def\({\left(} 
\def\){\right)}                   
\def\[{\left[}
\def\]{\right]}
\def\={\quad = \quad}
\def\+{\quad + \quad}
\def\-{\quad - \quad}
\def\dx{\, dx}
\def\dy{\, dy}
\def\dz{\, dz}
\def\dt{\, dt}
\def\q{\quad}
\def\qq{\qquad}
\def\w{\wedge}
\def\F{\mathbf F}
\def\cl{\centerline}
\def\grad{\nabla}
\def\ni{\noindent}
\def\ms{\medskip}
\def\bs{\bigskip}
\def\ss{\smallskip}
\def\vf{\vfill}
\def\br{\break}
\def\i{{\mathbf i}}          
\def\j{{\mathbf j}}
\def\k{{\mathbf k}}
\def\sol{{\noindent {\bf Solution.} }}
\def\le{\left|}
\def\ri{\right|}
\def\p{\partial}
\def\rh{\rho}
\def\ph{\phi}
\def\th{\theta}
\def\D{\mathbf D}
\def\la{\longrightarrow}
\def\La{\Longrightarrow}
\def\Vec{\overrightarrow}
\def\bm{\left[\begin{matrix}}
\def\em{\end{matrix}\right]}
\def\det{\left|\begin{matrix}}
\def\edet{\end{matrix}\right|}
\def\dint{\int\!\!\!\int}
\def\trint{\int\!\!\!\int\!\!\!\int}
\def\l{\lambda}
\def\pb{\vfill \pagebreak}            
\def\hb{\vskip 4in}
\def\ds{\displaystyle}
\def\curl{\mathrm{curl}}

\def\singlepage{
\addtolength{\textheight}{154pt} 
\addtolength{\topmargin}{-77pt}
\addtolength{\textwidth}{154pt}
\addtolength{\oddsidemargin}{-77pt}
\pagestyle{empty}}  

\def\multipage{
\addtolength{\textheight}{134pt}
\addtolength{\topmargin}{-78pt}
\addtolength{\textwidth}{150pt}
\addtolength{\oddsidemargin}{-75pt}  }


% \pagestyle{empty}

% \PostscriptAdjustment


\multipage

\def\halfenlargementpt{5pt}
\def\halfenlargementptii{23pt}


\addtolength{\textheight}{\halfenlargementpt}
\addtolength{\textheight}{\halfenlargementpt}
\addtolength{\topmargin}{-\halfenlargementpt}
\addtolength{\topmargin}{-\halfenlargementpt}


\addtolength{\textwidth}{\halfenlargementptii} 
\addtolength{\textwidth}{\halfenlargementptii} 
\addtolength{\oddsidemargin}{-\halfenlargementptii}


\begin{document}

\setlength{\topskip}{0in}


\noindent
\begin{minipage}[c]{1.2in}
{\footnotesize
{\sc St.\ Louis University\\ \semester}}
\end{minipage}
\hfill
\begin{minipage}[c]{4.0in}
\begin{center}
{\LARGE {\bf Solutions: Putnam LXIII}}
\end{center}
\end{minipage}
\hfill
\begin{minipage}[c]{1.2in}
{\footnotesize
{\sc \flushright 
\course\\ \hfill Prof.\ G. Marks}}
\end{minipage}


\def\epsilon{\varepsilon}

\bigskip

\bigskip


\ni {\normalsize {\rm Problems A1 through A6 were given during the 
3-hour morning session of the Putnam Exam of December 7, 2002; 
problems B1 through B6 were given during the 3-hour afternoon session 
of this exam.}}

\bigskip

\ni\dotfill

\bigskip

\it
\ni 
{\bf A1.}
Let $k$ be a fixed positive integer.  The $n$th derivative of 
$\ds\,\frac{1}{x^{k} - 1}\,$ has the form 
$\ds\,\frac{P_{n}(x)}{\(x^{k} - 1\)^{\!  n+1}}\,$ where $P_{n}(x)$ is 
a polynomial.  Find $P_{n}(1)$.

\rm

\bs

\sol
We have 
\begin{equation}
P_{n}(1) = (-1)^{n} n! \, k^{n}
\label{Putnam2002ProblemA1Eqn1}
\end{equation}
for each integer $n \geq 0$.  We prove this by induction on $n$.  
Since $P_{0}(x) = 1$, Equation~(\ref{Putnam2002ProblemA1Eqn1}) holds 
when $n=0$.  Now pick any integer $m\geq 0$ and assume that 
Equation~(\ref{Putnam2002ProblemA1Eqn1}) holds when $n=m$.  Since 
$$\frac{d^{m+1}}{dx^{m+1}}\!\(\frac{1}{x^{k} - 1}\) = \frac{d}{dx}\!\( 
\frac{P_{m}(x)}{\(x^{k} - 1\)^{\!  m+1}}\) = \frac{\(x^{k} - 1\) 
P_{m}'(x) - k(m+1) P_{m}(x) x^{k-1}}{\(x^{k} - 1\)^{\!  m+2}} =
\frac{P_{m+1}(x)}{\(x^{k} - 1\)^{\!  m+2}},$$
we infer that
\begin{eqnarray*}
P_{m+1}(1) \q = \q \(1^{k} - 1\) 
P_{m}'(1) - k(m+1) P_{m}(1) 1^{k-1} 
&=& -k(m+1) P_{m}(1) \\
&=&  -k(m+1) (-1)^{m} m! \, k^{m} \qq\mbox{(by inductive hypothesis)}\\
&=& (-1)^{m+1} (m+1)! \, k^{m+1},
\end{eqnarray*}
which shows that Equation~(\ref{Putnam2002ProblemA1Eqn1}) holds when 
$n=m+1$.  This completes the induction, and the proof.


\bigskip

\ni\dotfill

\bigskip

\it
\ni 
{\bf A2.}
Given any five points on a sphere, show that some four of them must 
lie on a closed hemisphere.

\rm

\bs

\sol Call the five points $\mathbf{P}_{1}, \ldots, \mathbf{P}_{5}$.  
Choose a great circle $C$ passing through $\mathbf{P}_{4}$ and 
$\mathbf{P}_{5}$.  This great circle divides the sphere into two 
closed hemispheres $H_{1}$ and $H_{2}$ with the property that $H_{1} 
\cap H_{2} = C$ and $H_{1} \cup H_{2}$ is the whole sphere.  By the 
pigeonhole principle, $H_{1}$ or $H_{2}$ must contain two of the three 
points $\mathbf{P}_{1}, \mathbf{P}_{2}, \mathbf{P}_{3}$, and thus 
contains four of the original five points.

\bigskip

\ni\dotfill

\bigskip

\it
\ni 
{\bf A3.}
Let $n \geq 2$ be an integer and $T_{n}$ be the number of non-empty 
subsets $S$ of $\{1, 2, 3, \ldots, n\}$ with the property that the 
average of the elements of $S$ is an integer.  Prove that $T_{n} - n$ 
is always even.

\rm

\bs

\sol Define $$\Omega_{n} = \left\{ S \subseteq \{1, 2, 3, \ldots, n\} 
\; \left| \;\; \frac{\sum_{a\in S}a}{\sum_{a\in S}1} \in \mathbb{Z} 
\;\; \mbox{and}\; \le S \ri > 1 \right.\right\}.$$ Then $T_{n} - n = 
\le \Omega_{n}\ri$.  Let $\varphi$ be the bijection from the power set 
of $\{1, 2, 3, \ldots, n\}$ to the power set of $\{1, 2, 3, \ldots, 
n\}$ defined by $\varphi(\emptyset) = \emptyset$ and 
$$\varphi(\{k_{1}, k_{2}, \ldots, k_{m}\}) = \{n+1-k_{m}, n+1-k_{m-1}, 
\ldots, n+1-k_{1}\}
\qq\mbox{(where $1\leq k_{1} < k_{2} < \cdots < k_{m} \leq n$)}.$$
Clearly $\varphi(\Omega_{n}) = \Omega_{n}$.  Since 
$\varphi(\varphi(S)) = S$ for all $S \in \Omega_{n}$, in order to show 
that $\le \Omega_{n} \ri$ is even it suffices to show that there are 
an even number of $S \in \Omega_{n}$ with the property that 
$\varphi(S) = S$ (let us say such subsets $S$ are {\it 
$\varphi$-invariant}).  The average of the elements of a 
$\varphi$-invariant subset is $(n+1)/2$.  So if $n$ is even, 
$\Omega_{n}$ contains no $\varphi$-invariant members.

Now assume $n$ is odd.  We have a bijection $$\left\{ S \in \Omega_{n} 
\; \left| \;\; \mbox{$S$ is $\varphi$-invariant and 
$\,\ds\frac{n+1}{2} \notin S$}\right.\right\} \longrightarrow \left\{ 
S \in \Omega_{n} \; \left| \;\; \mbox{$S$ is $\varphi$-invariant and 
$\,\ds\frac{n+1}{2} \in S$}\right.\right\}$$
given by $S \mapsto S \cup \left\{(n+1)/2\right\}$.  Thus, 
there are an even number of $\varphi$-invariant members of 
$\Omega_{n}$ if $n$ is odd.

We have shown that (regardless of the parity of $n$) $\Omega_{n}$ 
contains an even number of $\varphi$-invariant members, and therefore 
$T_{n} - n$ is even.

\bigskip

\ni\dotfill

\bigskip

\it
\ni 
{\bf A4.}
In Determinant Tic-Tac-Toe, Player~1 enters a $1$ in an empty $3 
\times 3$ matrix.  Player~0 counters with a $0$ in a vacant position, 
and play continues in turn until the $3 \times 3$ matrix is completed 
with five $1$'s and four $0$'s.  Player~0 wins if the determinant is 
$0$ and Player~1 wins otherwise.  Assuming both players pursue 
optimal strategies, who will win and how?

\rm

\bs

\sol Player~0 has a winning strategy.  Since row and column exchanges 
do not alter whether the determinant is $0$, by performing such 
exchanges we can assume without loss of generality that Player~1's 
first move is in the center position, a $1$ in the $(2,2)$-entry of 
the matrix.  Now Player~0 puts a $0$ in the $(1,1)$-entry of the 
matrix.  Taking transposes does not change determinants, so we can 
assume without loss of generality that Player~1's second move is a $1$ 
in either the $(3,3)$-entry, the $(2,3)$-entry, the $(1,3)$-entry, or 
the $(1,2)$-entry.  In each case, Player~0 has a winning sequence of 
moves, as follows (each of Player~1's moves is forced, since a row or 
column of $0$'s automatically wins for Player~0): 

\bs


\ni (I) $\ds\qq
\begin{array}{c|c|c} 0 &  &  
\\ \hline
  & 1 &   \\ \hline
  &   & 1
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 0 &  &  
\\ \hline
  & 1 &   \\ \hline
0  &   & 1
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 0 &  &  
\\ \hline
 1 & 1 &   \\ \hline
0  &   & 1
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0  & 0  &  \\ \hline
 1 & 1 &   \\ \hline
0  &   & 1
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0  & 0  & 1 \\ \hline
 1 & 1 &   \\ \hline
0  &   & 1
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0  & 0  & 1 \\ \hline
 1 & 1 &   \\ \hline
0  & 0 & 1
\end{array} \;\La\; \mbox{Player~0 wins}$.

\bs

\ni (II) $\ds\qq
\begin{array}{c|c|c} 
0 &   &  \\ \hline
  & 1 &  1 \\ \hline
  &   & 
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 0 &  & 0 
\\ \hline
  & 1 & 1  \\ \hline
  &   & 
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 0 & 1  & 0 
\\ \hline
  & 1 & 1  \\ \hline
  &   & 
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0 & 1  & 0  \\ \hline
  & 1  & 1  \\ \hline
0 &    & 
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0 & 1  & 0  \\ \hline
1 & 1  & 1  \\ \hline
0 &    & 
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0 & 1  & 0  \\ \hline
1 & 1  & 1  \\ \hline
0 &    & 0
\end{array} 
 \;\La\; \mbox{Player~0 wins}$.

\bs

\ni (III) $\ds\qq
\begin{array}{c|c|c} 
0 &   & 1 \\ \hline
  & 1 &    \\ \hline
  &   & 
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0 &   & 1 \\ \hline
  & 1 &    \\ \hline
0 & & \end{array} \;\La\; \mbox{Player~0 wins as in (I)}$.

\bs

\ni (IV) $\ds\qq
\begin{array}{c|c|c} 
0 & 1  &  \\ \hline
  & 1 &    \\ \hline
  &   & 
\end{array} \;\rightsquigarrow\;
\begin{array}{c|c|c} 
0 & 1  &  \\ \hline
  & 1 &    \\ \hline
0 & & \end{array} \;\La\; \mbox{Player~0 wins as in (II)}$.

\bigskip

\ni\dotfill

\bigskip

\it
\ni 
{\bf A5.}
Define a sequence by $a_{0} = 1$, together with the rules $a_{2n+1} = 
a_{n}$ and $a_{2n+2} = a_{n} + a_{n+1}$ for each integer $n \geq 0$.  
Prove that every positive rational number appears in the set $$\left\{ 
\frac{a_{n-1}}{a_{n}} : n \geq 1 \right\} = \left\{ \frac{1}{1}, 
\frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \ldots \right\}.$$

\rm

\bs

\sol Let $S$ denote the set described in the problem, i.e.\ $$S = 
\left\{ \left.\frac{a_{n-1}}{a_{n}} \in \mathbb{Q}
\; \right| \; n \in\mathbb{N} \right\}.$$
We will prove that $S$ contains every positive rational number.  
Suppose this is not the case.  Then we can choose $p, q \in 
\mathbb{N}$ with $p/q \notin S$ and $p+q$ minimal.  Since $1$ is 
visibly in $S$, we know that $p \neq q$.  Thus, either $q>p$ or $q<p$.

\bs

\ni {\it Case 1.} $q>p$.  Since $p+(q-p)<p+q$, we know that 
$p/(q-p)\in S$; say, $p/(q-p) = a_{n}/a_{n+1}$ for some $n$.  But 
$$\frac{p}{q-p} = \frac{a_{n}}{a_{n+1}} \qq\La\qq \frac{p}{q} = 
\frac{a_{n}}{a_{n}+a_{n+1}} = \frac{a_{2n+1}}{a_{2n+2}} \in S,$$ a 
contradiction.

\bs

\ni {\it Case 2.} $q<p$.  Since $(p-q)+q < p+q$, we know that $(p-q)/q 
\in S$; say, $(p-q)/q= a_{n}/a_{n+1}$ for some $n$.  But 
$$\frac{p-q}{q} = \frac{a_{n}}{a_{n+1}} \qq\La\qq \frac{p}{q} = 
\frac{a_{n}+a_{n+1}}{a_{n+1}} = \frac{a_{2n+2}}{a_{2n+3}} \in S,$$ a 
contradiction.


\bigskip

\ni\dotfill

\bigskip

\it \ni {\bf A6.} Fix an integer $b \geq 2$.  Let $f(1)=1$,\, 
$f(2)=2$, and for each $n\geq 3$, define $f(n) = n\, f(d)$, where $d$ 
is the number of base-$b$ digits of $n$.  For which values of $b$ does 
$$\sum_{n=1}^{\infty} \frac{1}{f(n)}$$ converge?

\rm

\bs

\sol Just $b=2$.  
To see this, first assume $b\geq 3$ and suppose for a contradiction that 
$\sum_{n=1}^{\infty} 1/f(n)$ converges.  Then
\begin{eqnarray*}
\sum_{n=1}^{\infty} \frac{1}{f(n)} \= \sum_{d=1}^{\infty} \( 
\sum_{n=b\tothe{1}{d-1}}^{b\tothe{1}{d}-1} \frac{1}{f(n)} \) &=&
\sum_{d=1}^{\infty} \( 
\sum_{n=b\tothe{1}{d-1}}^{b\tothe{1}{d}-1} \frac{1}{n\, f(d)} \) \\
&=& \sum_{d=1}^{\infty} \frac{1}{f(d)} \( 
\sum_{n=b\tothe{1}{d-1}}^{b\tothe{1}{d}-1} \frac{1}{n} \) \\
&>& \sum_{d=1}^{\infty} \frac{1}{f(d)} 
\( \int_{b\tothe{1}{d-1}}^{b\tothe{1}{d}} 
\frac{1}{x}\, dx \) \qq\mbox{(since left-endpoint Riemann sums 
overestimate)}\\
&=& \sum_{d=1}^{\infty} \frac{\ln b}{f(d)}  
\q>\q \sum_{d=1}^{\infty} \frac{\ln e}{f(d)}  
\q=\q \sum_{d=1}^{\infty} \frac{1}{f(d)} \q=\q 
\sum_{n=1}^{\infty} \frac{1}{f(n)},
\end{eqnarray*}
which is absurd.  Thus, if $b\geq 3$ then $\sum_{n=1}^{\infty} 1/f(n) = 
\infty$.

Now assume $b=2$.  We will define a monotonically increasing sequence 
of positive integers $m_{1}, m_{2}, m_{3}, \ldots$ as follows.  Fix 
any real number $L$ in the open interval $(\ln 2,\, 1)$.  Since
$$\lim_{x\to\infty}\ln\!\(\frac{2^{x}-1}{2^{x-1}-1}\) = \ln 2,$$
there exists an integer $m_{1}>2$ with the property that 
$$\ln\!\(\frac{2^{x}-1}{2^{x-1}-1}\)  \leq L \qq\mbox{whenever $x \geq 
m_{1}$.}$$  For all $k\in\mathbb{N}$, define
$$m_{k+1} = 2\tothe{2}{m_{k}-1}.$$  

Now, for any $k \in\mathbb{N}$,
\begin{eqnarray*}
\sum_{n=m_{k+1}}^{m_{k+2}-1} \frac{1}{f(n)} &=&
\sum_{n=2\tothe{2}{m_{k}-1}}^{2\tothe{2}{m_{k+1}-1}-1} 
\frac{1}{f(n)} \\
 &=&
\sum_{d=m_{k}}^{m_{k+1}-1} \( 
\sum_{n=2\tothe{2}{d-1}}^{2\tothe{1}{d}-1} \frac{1}{f(n)} \) \\
&=&
\sum_{d=m_{k}}^{m_{k+1}-1} \( 
\sum_{n=2\tothe{2}{d-1}}^{2\tothe{1}{d}-1} \frac{1}{n\, f(d)} \) \\
 &=&
\sum_{d=m_{k}}^{m_{k+1}-1} \frac{1}{f(d)} \( 
\sum_{n=2\tothe{2}{d-1}}^{2\tothe{1}{d}-1} \frac{1}{n} \) \\
&<& \sum_{d=m_{k}}^{m_{k+1}-1} \frac{1}{f(d)} \( 
\int_{2\tothe{2}{d-1}-1}^{2\tothe{1}{d}-1} \frac{1}{x}\, dx \) 
\qq\mbox{(since right-endpoint Riemann sums underestimate)}\\
&=& \sum_{d=m_{k}}^{m_{k+1}-1} \frac{1}{f(d)} 
\ln\!\(\frac{{2\tothe{1}{d}-1}}{{2\tothe{2}{d-1}-1}}\) \=
\sum_{n=m_{k}}^{m_{k+1}-1} \frac{1}{f(n)} 
\ln\!\(\frac{{2\tothe{1}{n}-1}}{{2\tothe{2}{n-1}-1}}\)
\q\leq\q L \cdot \sum_{n=m_{k}}^{m_{k+1}-1} \frac{1}{f(n)} 
\end{eqnarray*}
(by the choice of $m_{1}$).  This proves that for any 
$i\in\mathbb{N}$, $$\sum_{n=m_{i+1}}^{m_{i+2}-1} \frac{1}{f(n)} \;<\; L 
\cdot \sum_{n=m_{i}}^{m_{i+1}-1} \frac{1}{f(n)} \;<\; L^{2} \cdot 
\sum_{n=m_{i-1}}^{m_{i}-1} \frac{1}{f(n)} \;<\; \cdots \;<\; L^{i} \cdot 
\sum_{n=m_{1}}^{m_{2}-1} \frac{1}{f(n)}.$$  Consequently,
$$\sum_{n=m_{1}}^{m_{i+2}-1} \frac{1}{f(n)} =
\sum_{j=0}^{i} \(\sum_{n=m_{j+1}}^{m_{j+2}-1} \frac{1}{f(n)} \)
< \sum_{j=0}^{i} \(L^{j} \cdot 
\sum_{n=m_{1}}^{m_{2}-1} \frac{1}{f(n)} \) = 
\(\sum_{j=0}^{i} L^{j}\)\! \(
\sum_{n=m_{1}}^{m_{2}-1} \frac{1}{f(n)} \)
< \frac{1}{1-L} \sum_{n=m_{1}}^{m_{2}-1} \frac{1}{f(n)}.$$
Since $\ds\lim_{i\to\infty} m_{i+2}-1 = \infty$,\, this shows that the 
partial sums of the infinite series
\vspace{-6pt}
$$\sum_{n=m_{1}}^{\infty} \frac{1}{f(n)}$$

\vspace{-2pt}
\ni are bounded above by the constant $\ds\,\frac{1}{1-L} 
\sum_{n=m_{1}}^{m_{2}-1} \frac{1}{f(n)}$. \, Therefore
$\ds\sum_{n=m_{1}}^{\infty} \frac{1}{f(n)}$,\, and hence also
$\ds\,\sum_{n=1}^{\infty} \frac{1}{f(n)}$,\,
converges.

\bigskip

\ni\dotfill

\bigskip


\it \ni {\bf B1.} 
Shanille O'Keal shoots free throws on a basketball court.  She hits 
the first and misses the second, and thereafter the probability that 
she hits the next shot is equal to the proportion of shots she has hit 
so far.  What is the probability she hits exactly $50$ of her first 
$100$ shots?

\rm

\bs

\sol The probability is $1/99$.  To see this, let $E_{k,n}$ denote the 
event that she hits exactly $k$ of her first $n$ free throws, defined 
for integers $n\geq 2$ and $1\leq k \leq n-1$.  We will prove that for 
all such $k$ and $n$, 
\begin{equation}
\operatorname{Prob}(E_{k,n}) = 
\frac{1}{n-1}
\label{Putnam2002ProblemB1Eqn1}
\end{equation}
(which of course solves the problem).  
Equation~(\ref{Putnam2002ProblemB1Eqn1}) trivially holds when $n=2$.  
Pick an integer $m\geq 2$, and assume 
Equation~(\ref{Putnam2002ProblemB1Eqn1}) holds for $n=m$.  Then
\begin{eqnarray*}
\operatorname{Prob}(E_{k,m+1}) &=&
\operatorname{Prob}(E_{k,m}) \cdot \frac{m-k}{m} + 
\operatorname{Prob}(E_{k-1,m}) \cdot \frac{k-1}{m} \qq\mbox{(by 
Bayes's Theorem)} \\
&=& \frac{1}{m-1} \cdot \frac{m-k}{m} + 
\frac{1}{m-1} \cdot \frac{k-1}{m} \qq\mbox{(by 
inductive hypothesis)} \\
&=& \frac{1}{m},
\end{eqnarray*}
which shows that Equation~(\ref{Putnam2002ProblemB1Eqn1}) holds for 
$n=m+1$.  This completes the induction, and the proof.

\bigskip

\ni\dotfill

\bigskip


\it \ni {\bf B2.} 
Consider a polyhedron with at least five faces such that exactly 
three edges emerge from each of its vertices.  Two players play the 
following game:
\begin{quote}\ni
Each player, in turn, signs his or her name on a previously unsigned 
face.  The winner is the player who first succeeds in signing three 
faces that share a common vertex.
\end{quote}
Show that the player who signs first will always win by playing as 
well as possible.

\rm

\bs

\sol Note that not all faces of this (convex) polyhedron can be 
triangles, since in that case the number of vertices, $v$, would equal 
the number of faces, $f$, and the number of edges would be $e = 3f/2$, 
but then Euler's formula $v-e+f=2$ would yield $f=4$, contrary to 
hypothesis.

Thus, Player~1 can choose a face $F$ with more than $3$ edges and sign 
on that face as the first move.  Let $F_{1}, \ldots, F_{n}$ be the 
faces of the polyhedron different from $F$ that share an edge with 
$F$.  By the choice of $F$, we know $n\geq 4$.  Reindex so that $F$, 
$F_{i}$, and $F_{j}$ share a vertex whenever $j \equiv i \pm 1$ (where 
we  write these indices, here and in the next paragraph, modulo 
$n$).

If Player~2 now signs on $F_{i}$, or on any face not adjacent to $F$, 
then Player~1 signs on $F_{i+2}$.  Player~1 will then win on the next 
move on either $F_{i+1}$ or $F_{i+3}$.


\bigskip

\ni\dotfill

\bigskip


\it \ni {\bf B3.} 
Show that, for all integers $n>1$, $$\frac{1}{2ne} < \frac{1}{e} - \( 
1 - \frac{1}{n} \)^{\! n} < \frac{1}{ne}.$$

\rm

\bs

\sol
We begin by establishing the following inequality:
\begin{equation}
\frac{1}{x-1} > \ln\!\(\frac{x}{x-1}\) + \frac{1}{2x(x-1)} \qq\mbox{for 
every real number $x > 1$.}
\label{Putnam2002ProblemB3Eqn1}
\end{equation}
To prove this, note that for $t>0$, the graph of $f(t)=1/t$ is concave 
up, so the triangle with vertices $(x-1, 1/[x-1])$, $(x, 1/[x-1])$, 
and $(x, 1/x)$ lies entirely above the graph of $f$, except at the 
triangle's two vertices that lie on the graph.  The rectangle with 
vertices $(x-1, 1/[x-1])$, $(x, 1/[x-1])$, $(x-1, 0)$, and $(x,0)$ 
contains the triangle as well as the area under the graph of $f$ for 
$x-1 \leq t \leq x$.  The left-hand side of 
Equation~(\ref{Putnam2002ProblemB3Eqn1}) is the area of the rectangle, 
and the right-hand side is the sum of the area of the triangle and the 
area under the graph of $f$.

Now we will solve the problem.  Define the function $\ds\,g(x) = 
\frac{2x}{2x-1}\(1- \frac{1}{x}\)^{\!  x}$ for $x>1$.  For every 
$x>1$, $$g'(x) = \frac{2x}{2x-1} \(1- \frac{1}{x}\)^{\!  x} \[ 
\frac{1}{1-x} - \ln\!\(\frac{x}{x-1}\) - \frac{1}{2x^{2}-x}\] > 
\frac{2x}{2x-1} \(1- \frac{1}{x}\)^{\!  x} \[ \frac{1}{1-x} -
\ln\!\(\frac{x}{x-1}\) - \frac{1}{2x^{2}-2x}\] > 0,$$
by Equation~(\ref{Putnam2002ProblemB3Eqn1}).  Thus, $g$ is 
monotonically increasing on the interval $(1,\, \infty)$.  By standard 
calculus techniques, $\lim_{x\to\infty}g(x) = 1/e$.  Consequently, 
$g(x) < 1/e$ for every real number $x> 1$.

Define the function $\ds\, h(x) = \(1- \frac{1}{x}\)^{\!  x-1}$ for 
$x>1$.  For every $x>1$, $$h'(x) =\(1- \frac{1}{x}\)^{\!  x-1} \[ 
\frac{1}{x} -
\ln\!\(\frac{x}{x-1}\) \] < 0,$$
since $$\frac{1}{x} = \int_{x-1}^{x} \frac{1}{x}\, dt < \int_{x-1}^{x} 
\frac{1}{t}\, dt = \ln\!\(\frac{x}{x-1}\).$$
Thus, $h$ is monotonically decreasing on the interval $(1,\, \infty)$.  
Again by standard calculus techniques, $\lim_{x\to\infty}h(x) = 1/e$.  
Thus, $h(x) > 1/e$ for every real number $x> 1$.

For every real number $x > 1$, since $g(x)<1/e$ we have
$$\frac{2x}{2x-1}\(1- \frac{1}{x}\)^{\!  x} < \frac{1}{e} \qq\La\qq
\(1- \frac{1}{x}\)^{\!  x} < \frac{1}{e} \(1-\frac{1}{2x}\) \qq\La\qq
\frac{1}{e} - \(1- \frac{1}{x}\)^{\!  x} > \frac{1}{2ex}.$$
For every real number $x > 1$, since $h(x)>1/e$ we have $$\(1- 
\frac{1}{x}\)^{\!  x-1} > \frac{1}{e} \qq\La\qq \(1- \frac{1}{x}\)^{\!  
x} > \frac{1}{e}\(1-\frac{1}{x}\) \qq\La\qq \frac{1}{e} - \(1- 
\frac{1}{x}\)^{\!  x} < \frac{1}{ex}.$$ This shows that for every real 
number $n>1$ we have $\,\ds\frac{1}{2ne} < \frac{1}{e} - \( 1 - \frac{1}{n} 
\)^{\!  n} < \frac{1}{ne}$.



\bigskip

\ni\dotfill

\bigskip

\it \ni {\bf B4.} 
An integer $n$, unknown to you, has been randomly chosen in the 
interval $[1,\, 2002]$ with uniform probability.  Your objective is to 
select $n$ in an {\bf odd} number of guesses.  After each incorrect 
guess, you are informed whether $n$ is higher or lower, and you {\bf 
must} guess an integer on your next turn among the numbers that are 
still feasibly correct.  Show that you have a strategy so that the 
chance of winning is greater than $2/3$.

\rm

\bs

\sol First, we show that if the number of possible integers is a 
multiple of $3$, we have a way of guessing $n$ in an odd number of 
guesses with probability $2/3$, and we also have a way of guessing $n$ 
in an even number of guesses with probability $2/3$.  Suppose the 
number of possible integers is $3k$ for some $k\in\mathbb{N}$, and 
induct on $k$.  

Let $k=1$; so assume without loss of generality that we are guessing 
$n\in \{1,2,3\}$.  If we want $n$ in an odd number of guesses, first 
guess $n=3$.  We have a $1/3$ chance of finding $n$ on the first 
guess, and a $1/3$ chance of finding $n$ on the third guess.  On the 
other hand, if we want $n$ in an even number of guesses, first guess 
$n=2$.  We have a $2/3$ chance of finding $n$ on the second guess.
This proves that with $2/3$ probability we can find $n$ in a number of 
guesses of whichever parity we desire.

Now (inductively) assume the result for $3k$, and suppose (without 
loss of generality) we are guessing $n\in \{1,2,\ldots,3k+3\}$.  If we 
want $n$ in an odd number of guesses, first guess $n=3k+1$.  We have a 
$1/(3k+3)$ chance of finding $n$ on the first guess, we have a 
$2/(3k+3)$ chance of being told ``higher,'' whereupon we have a $1/2$ 
chance of finding $n$ on the third guess, and we have a $3k/(3k+3)$ 
chance of being told ``lower,'' in which case, by inductive 
hypothesis, we have a $2/3$ chance of finding $n$ in an odd number of 
guesses.  Thus, the probability of finding $n$ in an odd number of 
guesses will be $$\frac{1}{3k+3} + \frac{2}{3k+3} \cdot \frac{1}{2} + 
\frac{3k}{3k+3}\cdot \frac{2}{3} = \frac{2}{3}.$$ On the other hand, 
if we want $n$ in an even number of guesses, first guess $n=3k+2$.  We 
have a $1/(3k+3)$ chance of being told ``higher,'' whereupon we will 
find $n$ on the second guess, and we have a $(3k+1)/(3k+3)$ chance of 
being told ``lower.''  If told ``lower,'' we will guess $n=3k+1$; we 
will then have a $1/(3k+1)$ chance of finding $n$ on the second guess, 
and we will have a $3k/(3k+1)$ chance of being told ``lower,'' in 
which case, by inductive hypothesis, we will have a $2/3$ chance of 
finding $n$ in an even number of guesses.  Thus, the probability of 
finding $n$ in an even number of guesses will be $$\frac{1}{3k+3} + 
\frac{3k+1}{3k+3}\cdot \( \frac{1}{3k+1} + \frac{3k}{3k+1} \cdot
\frac{2}{3}\) = \frac{2}{3}.$$
This proves that, whenever the number of possibilities for $n$ is a 
multiple of $3$, then with $2/3$ probability we can find $n$ in a 
number of guesses of whichever parity we desire.

Now, given $n\in \{1,2,\ldots, 2002\}$, we begin by guessing $n=2002$.  
We have a $1/2002$ chance of finding $n$ on the first guess.  We have 
a $2001/2002$ chance of being told ``lower,'' and then we use our 
``multiple of $3$ in an even number of guesses'' strategy to win with 
probability $2/3$.  With this strategy, our probability of finding $n$ 
in an odd number of guesses is $$\frac{1}{2002} + \frac{2001}{2002} 
\cdot \frac{2}{3} = \frac{2002.5}{2002} \cdot \frac{2}{3} > 
\frac{2}{3}.$$

\bigskip

\ni\dotfill

\bigskip


\it \ni {\bf B5.} 
A palindrome in base $b$ is a positive integer whose base-$b$ digits 
read the same backwards and forwards; for example, $2002$ is a 4-digit 
palindrome in base $10$.  Note that $200$ is not a palindrome in base 
$10$, but it is the 3-digit palindrome $242$ in base $9$, and $404$ in 
base $7$.  Prove that there is an integer which is a 3-digit 
palindrome in base $b$ for at least $2002$ different values of $b$.

\rm

\bs

\sol We will show, more generally, that for any positive integers $k$ 
and $d$, there exists an integer that is a $d$-digit palindrome in 
base $b$ for at least $k$ different values of $b$.  Pick 
$m\in\mathbb{N}$ sufficiently large that 
\begin{equation}
m!  > 2^{d-1} k^{d} + k 
\qq\mbox{and}\qq m > k.
\label{PutnamLXIIIB5Eqn1}
\end{equation}  
Define $$b_{i} = \frac{m!}{i} - 1 \in\mathbb{N}$$ for $i = 1, 2, 
\ldots, k$.  Define $$n = (m!)^{d-1}.$$
Then $n$ is a $d$-digit palindrome in base $b_{i}$ for each $i \in 
\{1,2,\ldots,k\}$, for the following reason.  We have $$n = (m!)^{d-1} 
= (i b_{i}+i)^{d-1} = \sum_{\ell =0}^{d-1} {d-1 \choose \ell } i^{d-1} 
b_{i}^{\ell },$$ and, using Equation~(\ref{PutnamLXIIIB5Eqn1}), we 
find that $$1 \leq {d-1 \choose \ell } i^{d-1} \leq 2^{d-1} i^{d-1} 
\leq (2k)^{d-1}
< \frac{m!}{k}-1 \leq \frac{m!}{i}-1 = b_{i}.$$ 
Thus, $\,\ds {d-1 \choose \ell } i^{d-1}\,$ is the $(d-\ell)$-th 
digit of $n$ in base $b_{i}$.  Since $\,\ds {d-1 \choose \ell } 
i^{d-1} = {d-1 \choose d-1-\ell } i^{d-1}$,\, we conclude that $n$ is 
a palindrome in base $b_{i}$.



\bigskip

\ni\dotfill

\bigskip


\it \ni {\bf B6.} 
Let $p$ be a prime number.  Prove that the determinant of the 
matrix $$\bm x & y & z \\ \noalign{\ms} x^{p} & y^{p} & z^{p} \\ 
\noalign{\ms} x^{p^{2}} & y^{p^{2}} & z^{p^{2}} \em$$
is congruent modulo $p$ to a product of polynomials of the form $ax + 
by + cz$, where $a, b, c$ are integers.  (We say two integer 
polynomials are congruent modulo $p$ if corresponding coefficients are 
congruent modulo $p$.)

\rm

\bs

\def\putnamLXIIIspace{\hspace{-5.84pt}}

\sol More generally, we will show that if $x_{1}, x_{2}, \ldots, 
x_{n}$ are commuting indeterminates over the field $\mathbb{F}_{p}$ of 
integers modulo $p$, then in the polynomial ring 
$\mathbb{F}_{p}[x_{1}, x_{2}, \ldots, x_{n}]$ the determinant $$\Delta 
= \operatorname{det}\!\bm x_{1} & x_{2} & \cdots & x_{n} \\ 
\noalign{\ms} x_{1}^{p} & x_{2}^{p} & \cdots & x_{n}^{p} \\ 
\noalign{\ms} x_{1}^{p^{2}} & x_{2}^{p^{2}} & \cdots & x_{n}^{p^{2}} 
\\ \noalign{\ms} \vdots & \vdots & \vdots & \vdots \\
\noalign{\ms} x_{1}^{p^{n-1}} & x_{2}^{p^{n-1}} & \cdots & 
x_{n}^{p^{n-1}} \em$$ is a product of $\mathbb{F}_{p}$-linear 
combinations of $x_{1}, x_{2}, \ldots, x_{n}$; namely, $\Delta$ equals 
$$\prod_{(a_{1},\ldots,a_{n-1})\in \mathbb{F}_{p}^{n-1}} 
\putnamLXIIIspace 
\(x_{n} + \sum_{i=1}^{n-1} a_{i}x_{i}\) \cdot 
\prod_{(a_{1},\ldots,a_{n-2})\in \mathbb{F}_{p}^{n-2}} 
\putnamLXIIIspace 
\(x_{n-1} + \sum_{i=1}^{n-2} a_{i}x_{i}\) \cdot 
\prod_{(a_{1},\ldots,a_{n-3})\in \mathbb{F}_{p}^{n-3}} 
\putnamLXIIIspace
\(x_{n-2} + \sum_{i=1}^{n-3} a_{i}x_{i}\) \cdots \prod_{a_{1}\in 
\mathbb{F}_{p}}
\putnamLXIIIspace
\(x_{2} + a_{1}x_{1}\) \cdot x_{1}.$$
To see that $\Delta$ is equal to this expression, we first verify that 
each factor $x_{k} + \sum_{i=1}^{k-1} a_{i}x_{i}$ is indeed a divisor of 
$\Delta$.  Performing elementary column operations, we obtain 
\begin{eqnarray*}
\Delta \= 
\operatorname{det}\!\bm x_{1} & \cdots & x_{k} & \cdots & x_{n} \\ 
\noalign{\ms} x_{1}^{p} & \cdots & x_{k}^{p} & \cdots & x_{n}^{p} \\ 
\noalign{\ms} x_{1}^{p^{2}} & \cdots & x_{k}^{p^{2}} & \cdots & 
x_{n}^{p^{2}} \\ \noalign{\ms} \vdots & \vdots & \vdots & \vdots & 
\vdots \\
\noalign{\ms} x_{1}^{p^{n-1}} & \cdots & x_{k}^{p^{n-1}} & \cdots & 
x_{n}^{p^{n-1}} \em &=& \operatorname{det}\!\bm x_{1} & \cdots & x_{k}+ 
\sum_{i=1}^{k-1} a_{i}x_{i} & \cdots & x_{n} \\ \noalign{\ms} x_{1}^{p} 
& \cdots & x_{k}^{p}+ \sum_{i=1}^{k-1} a_{i}x_{i}^{p} & \cdots & 
x_{n}^{p} \\
\noalign{\ms} x_{1}^{p^{2}} & \cdots & x_{k}^{p^{2}}+ \sum_{i=1}^{k-1} 
a_{i}x_{i}^{p^{2}} & \cdots & x_{n}^{p^{2}} \\ \noalign{\ms} \vdots & 
\vdots & \vdots & \vdots & \vdots \\
\noalign{\ms} x_{1}^{p^{n-1}} & \cdots & x_{k}^{p^{n-1}}+ 
\sum_{i=1}^{k-1} a_{i}x_{i}^{p^{n-1}} & \cdots & x_{n}^{p^{n-1}} \em \\ 
\noalign{\bs}
&=& 
\operatorname{det}\!\bm x_{1} & \cdots & x_{k}+ 
\sum_{i=1}^{k-1} a_{i}x_{i} & \cdots & x_{n} \\ \noalign{\ms} x_{1}^{p} 
& \cdots & x_{k}^{p}+ \sum_{i=1}^{k-1} a_{i}^{p}x_{i}^{p} & \cdots & 
x_{n}^{p} \\
\noalign{\ms} x_{1}^{p^{2}} & \cdots & x_{k}^{p^{2}}+ \sum_{i=1}^{k-1} 
a_{i}^{p^{2}}x_{i}^{p^{2}} & \cdots & x_{n}^{p^{2}} \\ \noalign{\ms} 
\vdots & \vdots & \vdots & \vdots & \vdots \\
\noalign{\ms} x_{1}^{p^{n-1}} & \cdots & x_{k}^{p^{n-1}}+ 
\sum_{i=1}^{k-1} a_{i}^{p^{n-1}}x_{i}^{p^{n-1}} & \cdots & 
x_{n}^{p^{n-1}} \em \\ 
\noalign{\bs}
&=& 
\operatorname{det}\!\bm x_{1} & \cdots & x_{k}+ 
\sum_{i=1}^{k-1} a_{i}x_{i} & \cdots & x_{n} \\ \noalign{\ms} x_{1}^{p} 
& \cdots & \(x_{k}+ 
\sum_{i=1}^{k-1} a_{i}x_{i}\)^{ p} & \cdots & 
x_{n}^{p} \\
\noalign{\ms} x_{1}^{p^{2}} & \cdots & \(x_{k}+ \sum_{i=1}^{k-1} 
a_{i}x_{i}\)^{  p^{2}} & \cdots & x_{n}^{p^{2}} \\ \noalign{\ms} 
\vdots & \vdots & \vdots & \vdots & \vdots \\
\noalign{\ms} x_{1}^{p^{n-1}} & \cdots & \(x_{k}+ 
\sum_{i=1}^{k-1} a_{i}x_{i}\)^{ p^{n-1}} & \cdots & 
x_{n}^{p^{n-1}} \em
\end{eqnarray*}
(using the rule for the $p$th power of a sum modulo $p$, and the fact 
that $a_{i}^{p} = a_{i}$ for all $a_{i} \in \mathbb{F}_{p}$).  
Expanding this last determinant along the $k$th column shows that 
$\Delta$ is divisible by $x_{k} + \sum_{i=1}^{k-1} a_{i}x_{i}$ in the 
unique factorization domain $\mathbb{F}_{p}[x_{1}, x_{2}, \ldots, 
x_{n}]$.  Since that is the case for all of the linear polynomials 
$x_{k} + \sum_{i=1}^{k-1} a_{i}x_{i}$, which are clearly pairwise 
coprime, $\Delta$ is divisible by $$\prod_{(a_{1},\ldots,a_{n-1})\in 
\mathbb{F}_{p}^{n-1}} \putnamLXIIIspace \(x_{n} + \sum_{i=1}^{n-1} 
a_{i}x_{i}\) \cdot \prod_{(a_{1},\ldots,a_{n-2})\in 
\mathbb{F}_{p}^{n-2}} \putnamLXIIIspace \(x_{n-1} + \sum_{i=1}^{n-2} 
a_{i}x_{i}\) \cdot \prod_{(a_{1},\ldots,a_{n-3})\in 
\mathbb{F}_{p}^{n-3}} \putnamLXIIIspace \(x_{n-2} + \sum_{i=1}^{n-3} 
a_{i}x_{i}\) \cdots \prod_{a_{1}\in \mathbb{F}_{p}} \putnamLXIIIspace
\(x_{2} + a_{1}x_{1}\) \cdot x_{1}.$$
But $\Delta$ must in fact be a constant multiple of this expression, 
since the expression and $\Delta$ both have the same total degree in 
the $x_{i}$'s, namely, $p^{n-1} + p^{n-2} + p^{n-3} + \cdots + p + 1$.  
The constant by which the expression must be multiplied to yield 
$\Delta$ is the coefficient of $x_{1} x_{2}^{p} 
x_{3}^{p^{2}}\cdots\: x_{n}^{p^{n-1}}$ in $\Delta$; this 
coefficient, corresponding to the product down the main diagonal, is 
$1$.  This proves that $$\operatorname{det}\!\bm x_{1} & x_{2} & 
\cdots & x_{n} \\ \noalign{\ms} x_{1}^{p} & x_{2}^{p} & \cdots & 
x_{n}^{p} \\ \noalign{\ms} x_{1}^{p^{2}} & x_{2}^{p^{2}} & \cdots & 
x_{n}^{p^{2}} \\ \noalign{\ms} \vdots & \vdots & \vdots & \vdots \\
\noalign{\ms} x_{1}^{p^{n-1}} & x_{2}^{p^{n-1}} & \cdots & 
x_{n}^{p^{n-1}} \em \; = \; \hspace{382.15pt}$$
$$\prod_{(a_{1},\ldots,a_{n-1})\in 
\mathbb{F}_{p}^{n-1}} \putnamLXIIIspace \(x_{n} + \sum_{i=1}^{n-1} 
a_{i}x_{i}\) \cdot \prod_{(a_{1},\ldots,a_{n-2})\in 
\mathbb{F}_{p}^{n-2}} \putnamLXIIIspace \(x_{n-1} + \sum_{i=1}^{n-2} 
a_{i}x_{i}\) \cdot \prod_{(a_{1},\ldots,a_{n-3})\in 
\mathbb{F}_{p}^{n-3}} \putnamLXIIIspace \(x_{n-2} + \sum_{i=1}^{n-3} 
a_{i}x_{i}\) \cdots \prod_{a_{1}\in \mathbb{F}_{p}} \putnamLXIIIspace
\(x_{2} + a_{1}x_{1}\) \cdot x_{1}.$$


\end{document}