\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{xcolor}

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
21-128 problem sheet 4
}

Solutions to starred (*) exercises are due at the beginning of recitation on

\textbf{Thursday 8th October 2015}

Please submit answers to separate questions on separate sheets of paper.

\end{center}

\subsubsection*{Problem 1 --- 4.1}
Let $120102_{(3)}$ and $110222_{(3)}$ be ternary representations of two natural numbers. Use base $3$ arithmetic to add them. Check the answer by converting each to base $10$, adding, and converting back to base $3$.

\subsubsection*{Problem 2 --- 4.2}
Which integer is bigger, $333_{(12)}$ or $3333_{(5)}$?

\subsubsection*{Problem 3 --- 4.3 *}
Note that $15^2 = 225$, $25^2 = 625$, $35^2 = 1225$. For $n \in \mathbb{N}$, prove that the square of the number given by appending $5$ to the base $10$ representation of $n$ is the number given by appending $25$ to the base $10$ representation of $n(n+1)$.

\subsubsection*{Problem 4 --- 4.6}
Let $A$ be the set of days in the week. Let $f$ assign to each day the number of letters in its English name. Does $f$ define an injection from $A$ to $\mathbb{N}$?

\subsubsection*{Problem 5 --- 4.8}
Let $f$ and $g$ be polynomials defined by $f(x)=x-1$ and $g(x)=x^2-1$ for all $x \in \mathbb{R}$. Find formulae for $f \circ g$ and $g \circ f$.

\subsubsection*{Problem 6 --- 4.10 *}
Let $a,b,c,d \in \mathbb{R}$ be constants with $a \ne 0$ and $c \ne 0$. Suppose that $f,g : \mathbb{R} \to \mathbb{R}$ with $f(x)=ax+b$ and $g(x)=cx+d$ for all $x \in \mathbb{R}$. Prove that $f$ and $g$ are injective and surjective, but that the function $h : \mathbb{R} \to \mathbb{R}$ defined by $h = g \circ f - f \circ g$ is neither injective nor surjective.

\subsubsection*{Problem 7 --- 4.13 *}
Given a three-digit decimal number $n$, written as $\alpha \beta \gamma$ in base $10$, the \textit{reverse} of $n$ is the number written as $\gamma \beta \alpha$ in base $10$. (For example, the reverse of $235$ is $532$, and the reverse of $3$ is $300$.)

Let $n$ be an integer between $1$ and $999$ written as $abc$ in base $10$. Suppose $a \ne c$. Let $x$ be the (positive) difference between $n$ and its reverse. Prove that the sum of $x$ and its reverse is $1089$.

\subsubsection*{Problem 8 --- 4.15 *}
Consider a balance scale plus $k$ objects of known weights $1,3,\dots,3^{k-1}$. Prove by induction on $k$ that every unknown weight in the set $\left\{ 1, 2, \dots, \frac{3^k-1}{2} \right\}$ can be balanced.

\subsubsection*{Problem 9 --- 4.17 *}
A position in the game of \textit{Nim} consists of some piles of coins. Two players alternate, with each move removing a portion of one pile. The winner is the player who takes the last coin.

Suppose that the starting piles have sizes $n_1, \dots, n_k$. Prove that Player 2 has a winning strategy if and only if, for every $j$, an even number of $n_1, \dots, n_k$ have a $1$ in position $j$ in their binary representation. For example, when the sizes are $1,2,3$, the binary representations are $1,10,11$, and the condition holds.

\subsubsection*{Problem 10 --- 4.24 *}
Let $f$ and $g$ be surjections from $\mathbb{Z}$ to $\mathbb{Z}$, and let $h=fg$ be their product (see Definition 1.25 in the book). Must $h$ also be surjective? Give a proof or a counterexample.

\subsubsection*{Problem 11 --- 4.25 *}
Determine which formulae below define surjections from $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$.
\begin{enumerate}[(a)]
\item $f(a,b)=a+b$;
\item $f(a,b)=ab$;
\item $f(a,b) = \frac{ab(b+1)}{2}$;
\item $f(a,b) = \frac{(a+1)a(b+1)}{2}$;
\item $f(a,b) = \frac{ab(a+b)}{2}$.
\end{enumerate}

\end{document}
