\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 $qp$. Since $p+(q-p)& \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$pbe 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 modulop$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 thep$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}