\newpage\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 and 15-151 problem sheet 4}
Solutions to the following seven exercises and optional bonus problem are to be submitted through
blackboard by 8:30AM on
\textbf{Thursday 6th October 2016.}
There are also some practice problems, not to be turned in, for those seeking more practice
and also for review prior to the exam.
\end{center}
\subsubsection*{Problem 1}
For each pair below, use the Euclidean algorithm to compute the greatest common divisor, and express the greatest
common divisor as an integer combination of the two numbers:
\begin{enumerate}[(a)]
\item $126$ and $224$;
\item $221$ and $299$.
\end{enumerate}
\subsubsection*{Problem 2}
A cash register contains the same number of dimes and quarters, in total a nonzero whole number of dollars.
What is the minimum number of coins?
\subsubsection*{Problem 3}
Prove that $\mathrm{gcd}(a+b,a-b) = \mathrm{gcd}(2a,a-b) = \mathrm{gcd}(a+b, 2b)$, for all $a,b \in \mathbb{Z}$.
\subsubsection*{Problem 4}
Prove that $(2n)!/(2^n n!)$ is an odd integer for every natural number $n$.
\subsubsection*{Problem 5}
A treasury has 500 7-ounce weights, 500 11-ounce weights, and a balance.
A foreign dignitary arrives with a gold bar, claiming it to weigh 500 ounces.
Can the treasury determine whether the dignitary is telling the truth? If so, how?
\subsubsection*{Problem 6}
A positive integer is {\it perfect} if it is the sum of positive integers less than it which divide it.
For example, $6 = 1 + 2 + 3$ and $28 = 1 + 2 + 4 + 7 + 14$ are perfect. Prove that if $2^n - 1$ is prime,
then $2^{n-1} (2^n - 1)$ is perfect. (Hint: What are the divisors? You can use geometric series to sum them.)
\subsubsection*{Problem 7}
Five suspicious sailors spend the day gathering a pile of coconuts. Exhausted, they postpone dividing it until the
next morning. Suspicious, each decides to take his share during the night. The first sailor divides the pile into
five equal portions plus one extra coconut, which he gives to a monkey. He takes one pile and leaves the rest in
a single pile. The second sailor later does the same; again the monkey receives one leftover coconut. The third,
fourth and fifth sailors all do this; each time, a remainder of one goes to the monkey. In the morning, they split
the remaining coconuts into five equal piles, and each sailor gets his ``share''. (Each knows some were taken, but
none complains, since each is guilty!) What is the smallest number of coconuts in the original pile?
\subsubsection*{Bonus Problem (2 points)}
Tanvi has two jars of jelly beans, one with $x$ beans and the other with $y$ beans. Each jar has a lever.
When a jar has at least 2 beans, pressing its lever will give Tanvi one bean from it and move one bean from
it to the other jar (if there are 1 or 0 beans in the jar, then pressing the lever has no effect). Determine
necessary and sufficient conditions on $x$ and $y$, so that Tanvi can extract all but one of the jelly beans.
\subsubsection*{Extra Problem 1}
Find all integer solutions $x,y$ to the equation $\frac{1}{60} = \frac{x}{5} + \frac{y}{12}$.
\subsubsection*{Extra Problem 2}
Find every integer $k \ge 3$ such that $k-2$ divides $2k$.
\subsubsection*{Extra Problem 3}
Suppose that $\mathrm{gcd}(a,b)=1$. Prove that $\mathrm{gcd}(na,nb)=n$.
\end{document}