\documentclass[12pt]{article}
\usepackage[margin=0.7in]{geometry}
\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}
% If you don't have this package, comment this line out and uncomment
% the following lines. It's more convenient with the actual spacing,
% however; that way, I can insert corrections more legibly.
\usepackage{setspace}
%\newcommand{\singlespacing}{}
%\newcommand{\onehalfspacing}{}
% 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}{Your name here}
\pagestyle{fancy}
\lhead{MATH 311-02}
\chead{Problem Set \#6}
% 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{\bf due April 8}
\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.}
\onehalfspacing
\singlespacing
\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.}
\onehalfspacing
\singlespacing
\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.}
\onehalfspacing
\singlespacing
\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.}
\onehalfspacing
\singlespacing
\item \textbf{(4 points)} \emph{Demonstrate a set $A$ and function
$f:A\rightarrow A$ which is surjective but not injective.}
\onehalfspacing
\singlespacing
\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.}
\onehalfspacing
\singlespacing
\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.}
\onehalfspacing
\singlespacing
\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.}
\onehalfspacing
\singlespacing
\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$.}
% \onehalfspacing
\end{enumerate}
\end{document}