\documentclass[12pt]{article}
\usepackage[margin=0.7in]{geometry}
\usepackage[%pdftex,
urlcolor=rltblue]{hyperref}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\usepackage{fancyhdr}
% lastpage may not be part of your installation; it's a somewhat
% nonstandard package that determines the page number of the last page
% of your document, and allows you to refer to it with
% \pageref{LastPage}. If you don't have it, it can be worked around.
\usepackage{lastpage}
% Uncomment the following line and actually put your name into the
% second pair of braces. This will make LaTeX resolve \studentname
% throughout the document as whatever you put in the braces. Note that
% if you don't uncomment this line, your source will not compile!
\newcommand{\studentname}{}
\pagestyle{fancy}
\lhead{MATH 311-02}
\chead{Problem Set \#6 Solutions}
% This next line will fail to compile unless you uncomment the
% \newcommand up above!
\rhead{\studentname}
\lfoot{}
% If you're not using lastpage, then comment this command out and use
% the simpler version which is commented out below.
\cfoot{Page \thepage\ of \pageref{LastPage}}
%\cfoot{Page \thepage}
\rfoot{April 8, 2011}
\begin{document}
\begin{enumerate}
\item \textbf{(6 points)} \emph{In power-of-3 nim, the game state is a
single non-negative integer (i.e., a stack of coins), such that
each move consists of subtracting some power of 3 (i.e., removing
a number of objects which is a power of 3). For instance, in a
game with initial state 200, the first player could reduce the
state to 199, 197, 191, 173, or 119. The game is won by whoever
reduces the state to zero (i.e. removes the last coin).}
\begin{enumerate}
\item \textbf{(3 points)} \emph{Show that with an initial state of
$200$ and rational play by the second player, the first player
will lose.}
This result is in fact deferred to the second problem, which shows
a much stronger statement.
\item \textbf{(3 points)} \emph{Show that with an initial state of
$200$, the first player will lose regardless of how the second
player plays.}
We may observe (and prove by induction) that at the end of the
first player's $n$th turn, regardless of how each player plays,
the game state will be odd.
\begin{proof}
We prove this by induction; in the base case $n=1$, the state
is, as seen, one of $199$, $197$, $191$, $173$, or $119$, each
of which is an odd number.
For the inductive step, let us assume the result above to be
shown for a specific value $k$; that is, after the first
player's $k$th turn, the state is an odd number. Now the second
player makes a move; regardless of what this move is, it will
decrement the game state by an odd number (since all powers of 3
are odd), so after the second player's move, the game state will
be even. Then the first player's $(k+1)$th move will decrement
the even game state by an odd number, yielding an odd number, so
the game state after the first player's $(k+1)$th move is odd,
regardless of what strategy either player uses.
\end{proof}
Since 0 is even, it is thus impossible for the first player to
reduce the game state to zero and thus win.
\end{enumerate}
\item \textbf{(10 points)} \emph{2-or-3 nim is played with again a
game state consisting of a single integer (i.e. a stack of coins),
and moves consisting of subtracting 2 or 3 from the game state
(i.e. removing 2 or 3 coins). The game is won by whichever player
reduces the stack to either 1 or 0 coins (i.e. when their opponent
cannot move). Experiment with this game to determine which states
are winning and losing; then form and prove a conjecture about
which states are winning and which are losing.}
We start with exploratory results: $0$ and $1$ are definitionally
losing states (since no move can be made at this point). $2$, $3$,
and $4$ will be winning states, since from each of these states, the
move $2$, either move, and the move $3$ will respectively confront
the opponent with a losing state. $5$ and $6$ are losing states,
since decrementing either of them by either 2 or 3 provides the
opponent with one of the winning states $2$, $3$, or $4$. Now $7$,
$8$, and $9$ are again winning states, since taking away two, taking
away either two or three, and taking away three are respectively
moves which confront the opponent with one of the losing states $5$
or $6$. At this point we observe a pattern, and are comfortable
making the following statement, which turns out to completely
describe the victory conditions for this game.
\begin{proposition}
The current player can win the 2-or-3 nim game if and only if the
game state $n$ is congruent to 2, 3, or 4 modulo 5.
\end{proposition}
\begin{proof}
We prove this by induction: the base cases $n=0$ and $n=1$ are
trivially losing.
For our inductive step, let us assume the proposition has already
been shown for all game states up to some value $k$. Now we
consider the winning prospects for game state $k+1$, divided up
into cases based on the five potential congruence classes modulo 5:
\textbf{Case I: $k+1\equiv 0\pmod 5$.} The game states reachable
via a single move are $(k+1)-2=k-1$ and $(k+1)-3=k-2$. Since both
of these values are less than $k+1$, whether they are winning or
losing states are, by our inductive hypothesis, already known to
be determined by their congruence classes modulo 5. Since
$k+1\equiv 0\pmod 5$, it follows that $k-1\equiv -2\equiv 3\pmod
5$ and $k-2\equiv -3\equiv 2\pmod 5$, which our inductive
hypothesis guarantees are both winning states. Since every move
provides the opponent with a winning state, we may conclude that
$k+1$ is in fact a losing state when $k+1\equiv 0\pmod 5$.
\textbf{Case II: $k+1\equiv 1\pmod 5$.} The game states reachable
via a single move are $(k+1)-2=k-1$ and $(k+1)-3=k-2$. We proceed
as above: since $k+1\equiv 1\pmod 5$, it follows that $k-1\equiv
-1\equiv 4\pmod 5$ and $k-2\equiv -2\equiv 3\pmod 5$, which our
inductive hypothesis guarantees are both winning states. Since
every move provides the opponent with a winning state, we may
conclude that $k+1$ is in fact a losing state when $k+1\equiv
1\pmod 5$.
\textbf{Case III: $k+1\equiv 2\pmod 5$.} The game state
$(k+1)-2=k-1$ is reachable via a single move (i.e., subtraction of
two). As above, since this value is less than $k+1$, we may rely
on the inductive hypothesis. Since $k+1\equiv 2\pmod 5$, it
follows that $k-1\equiv 0\pmod 5$, which our inductive hypothesis
guarantees is a losing state. Since there is a move which provides
the opponent with a losing state, we may conclude that $k+1$ is in
fact a winning state when $k+1\equiv 2\pmod 5$.
\textbf{Case IV: $k+1\equiv 3\pmod 5$.} The game state
$(k+1)-2=k-1$ is reachable via a single move (i.e., subtraction of
two). We proceed as above: since $k+1\equiv 3\pmod 5$, it
follows that $k-1\equiv 1\pmod 5$, which our inductive hypothesis
guarantees is a losing state. Since there is a move which provides
the opponent with a losing state, we may conclude that $k+1$ is in
fact a winning state when $k+1\equiv 3\pmod 5$.
\textbf{Case V: $k+1\equiv 4\pmod 5$.} The game state
$(k+1)-3=k-2$ is reachable via a single move (i.e., subtraction of
two). We proceed as above: since $k+1\equiv 4\pmod 5$, it
follows that $k-2\equiv 1\pmod 5$, which our inductive hypothesis
guarantees is a losing state. Since there is a move which provides
the opponent with a losing state, we may conclude that $k+1$ is in
fact a winning state when $k+1\equiv 4\pmod 5$.
Note that judicious use of similarity-of-argumentation might serve
to reduce this argument to only 2 cases.
\end{proof}
\item \textbf{(13 points)} \emph{We shall inspect the false statement:
``For a set $A$ and function $f:A\rightarrow A$, the function $f$
is inejctive if and only if it is bijective.}
\begin{enumerate}
\item \textbf{(3 points)} \emph{Demonstrate a set $A$ and function
$f:A\rightarrow A$ which is injective but not surjective.}
A simple example is the function $f:\mathbb N\rightarrow\mathbb N$
given by $f(n)=n+1$. This is indeed injective: if $n\neq m$,
surely $n+1\neq m+1$. It is not, however, surjective: there is no
natural number $n$ such that $f(n)=0$.
Many other examples are possible.
\item \textbf{(4 points)} \emph{Demonstrate a set $A$ and function
$f:A\rightarrow A$ which is surjective but not injective.}
One good example is $f:\mathbb N\rightarrow\mathbb N$ given by
$f(n)=\left\lfloor\frac n2\right\rfloor$ (i.e., the integer part
of $\frac n2$). This is surjective, since for evern $n\in\mathbb
N$, $f(2n)=n$, so every element of the codomain is achieved;
however, it is not injective, since, for instance, $f(5)=f(4)=2$
(in fact, for eveny $n$, $f(2n+1)=f(2n)=n$).
Many other examples are possible.
\item \textbf{(6 points)} \emph{Find as unrestrictive a condition on
$A$ as possible to make the statement ``A function $f:A\rightarrow
A$ is injective if and only if it is surjective'' true. Prove your
result.}
This statement will be true when $A$ is finite.
\begin{proposition}
If a set $A$ is finite, then $f:A\rightarrow A$ is injective if
and only if $f$ is surjective.
\end{proposition}
\begin{proof}
Let us denote $n$ as the size of $A$, and explicitly label its
elements as $A=\{a_1,a_2,a_3,\ldots,a_n\}$. Now suppose $f$ is
injective. Thus, $f(a_1),f(a_2),f(a_3),\ldots,f(a_n)$ must all
be distinct, so the image of $f$, which is
$\{f(a_1),f(a_2),\ldots,f(a_n)\}$, consists of $n$ distinct
elements, and is thus a set of size $n$. Since the image, shown
above to have size $n$, is a subset of the codomain $A$, which
definitionally has size $n$, the image is identical to the
codomain and thus the function is surjective.
On the other hand, suppose $f$ were not injective. Then there is
some $a_i\neq a_j$ such that $f(a_i)=f(a_j)$ (i.e., a
``collision''), so that $f(a_1),f(a_2),f(a_3),\ldots,f(a_n)$ are
\emph{not} all distinct, and thus the image of $f$, which is
$\{f(a_1),f(a_2),\ldots,f(a_n)\}$, actually contains fewer than
$n$ distinct elements, and is thus a set of size less than
$n$. Since the image has size less than $n$ and the codomain $A$
has size $n$, the image must not be identical to the codomain
and thus the function is not surjective.
\end{proof}
\end{enumerate}
\item \textbf{(11 points)} \emph{The following questions relate to
function composition.}
\begin{enumerate}
\item \textbf{(6 points)} \emph{Prove or disprove: for any sets $A$,
$B$, and $C$, with functions $f:A\rightarrow B$ and
$g:B\rightarrow C$, if $f$ is bijective and
$g\circ f$ is surjective, then $g$ is surjective.}
\begin{proof}
Since $g\circ f$ is surjective, we know that for every $c\in C$,
there is an $a\in A$ such that $g(f(a))=c$; from this we know
that $b=f(a)$ is an element of $B$ such that $g(b)=c$. Since we
know that for every $c\in C$ there is a $b\in B$ such that
$g(b)=c$, we can conclude that $g$ is surjective.
\end{proof}
\item \textbf{(5 points)} \emph{Prove or disprove: for any sets $A$,
$B$, and $C$, with functions $f:A\rightarrow B$ and
$g:B\rightarrow C$, if $g$ is injective and
$g\circ f$ is injective, then $f$ is injective.}
It is easiest to prove this by the contrapositive, so we might
consider $f$ {\em not} injective, and show that either $g$ is
noninjective or $g\circ f$ is noninjective.
\begin{proof}
Suppose $f$ is noninjective, so there are some $x,y\in A$ such
that $x\neq y$ and $f(x)=f(y)$. Then, $g(f(x))=g(f(y))$, so
$g\circ f(x)=g\circ f(y)$, and thus $g\circ f$ is noninjective.
\end{proof}
\end{enumerate}
% You only need to do the following if you want to -- which is why
% it's commented out in the basic template, so that it doesn't show
% up unless you uncomment it and work on it.
\item \textbf{(4 point bonus)} \emph{We craft a collection of
sequences by the following procedure: we let $A_1=(1)$, and then
for each $A_{i+1}$ henceforth, we read $A_i$ left-to-right,
counting the number of occurrences of each number, and then
writing the numbers spoken as our new sequence. So, we would read
$A_1$ as ``one 1'', and write out $A_2=(1,1)$. Then we read out
$A_2$ as ``two 1s'', and write out $A_3=(2,1)$; reading out $A_3$
as ``one 2, one 1'' gives us $A_4=(1,2,1,1)$.}
\emph{Prove that the number $4$ does not appear in any sequence
$A_i$.}
We can prove this statement by induction.
\begin{proposition}
For $A_i$ defined as above, each sequence $A_i$ does not contain a
$4$.
\end{proposition}
\begin{proof}
We shall prove this by induction; the base cases $A_1=(1)$ and
$A_2=(1,1)$ clearly do not contain 4s.
For our inductive hypothesis, let us suppose a specific $A_k$ is a
sequence without a 4 in it. Now, we wish to show that $A_{k+1}$
also does not contain a 4. By construction, it is each {\em pair}
of terms from $A_{k+1}$ that describes terms in $A_k$, with the
odd terms counting quantities, and with the even terms identical
to terms from $A_k$, so by our inductive hypothesis none of the
even-index terms of $A_{k+1}$ are 4. Thus, in order for $A_{k+1}$
to contain a 4, it must be a quantity-measurement.
We shall demonstrate the impossibility of such an occurrence by
contradiction. Let us suppose that $A_{k+1}$ does contain the pair
$4, r$ for some number $r$. This would occur only if $A_k$
contains 4 consecutive instances of the number $r$. There are two
possible ways such a sequence could occur: they could be two
``pairs'' from $A_{k-1}$, in which case the description is ``$r$
copies of $r$, followed by $r$ copies of $r$'', which would not
actually result in $A_{k-1}$ containing the substring $r,r,r,r$,
but instead $2r,r$, since such a sequence in $A_{k-1}$ would be
more succinctly considered as ``$2r$ copies of
$r$''. Alternatively, the subsequence $r,r,r,r$ might be crossing
pair-boundaires, so that the first $r$ is the second half of a
pair with some $a$, the middle two copies of $r$ form a pair, and
the last $r$ is the first half of a pair with some $b$. This would
be produced from some $A_{k-1}$ containing a section which would
be described as ``$a$ copies of $r$, followed by $r$ copies of
$r$, followed by $r$ copies of $b$''. Again, however, this
description would not be used, since the standard description of
that structure would result not in the substring $a,r,r,r,r,b$,
but $(a+r),r,r,b$, since ``$a$ copies of $r$, followed by $r$
copies of $r$'' would be read off as ``$(a+r)$ copies of $r$''.
Thus, since the substring $r,r,r,r$ cannot appear in $A_k$, the
substring $4,r$ would not appear in $A_{k+1}$.
\end{proof}
The above sequence is often used in brain-teasers --- usually
without telling the victim the rule. Showing that it contains no 4
is a bit beyond everyday brainteasers and into the realm of
mathematical brainteasers.
Despite the fact that this sequence's construction seems very
beer-and-pretzels, it's spurred some awfully sophisticated
math. John Conway showed that the sequence's length grows with each
iteration by a factor of approximately 1.30358 (the exact factor is
the unique positive root of a 71st-degree polynomial).
For future research: this process is commonly known as the ``Look
and Say'' sequence; Conway calls it the ``audioactive'' sequence. It
appears in the Online Encyclopedia of Integer Sequences as
\href{http://oeis.org/A005150}{A005150}.
\end{enumerate}
\vfill
\begin{center}
\fbox{
\begin{minipage}{6in}
\noindent Problems worthy\\
\phantom{--- ---} of attack\\
prove their worth\\
\phantom{--- ---} by hitting back.
\hfill ---Piet Hein, ``Problems''
\end{minipage}
}
\end{center}
\end{document}