%  Homework assignment 5
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Monday, March 15, 2010. Due: Wednesday, March 24, 2010.
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=9truein
\pdfhorigin=1.25truein \pdfvorigin=1truein

\font\titlefont=cmbx12
\font\smfont=cmr8

\headline={\hfil}
\footline={\hfil}
\topskip=20pt plus2pt

\newcount\pno  \pno=0
\def\problem{\goodbreak\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\goodbreak\noindent{\bf Problem~\hbox{#1}.} }
\def\noskiphint#1\par{\nobreak{\hyphenpenalty=10000\noindent{\it Hint:\/}\enspace#1\par}}
\def\hint#1\par{\nobreak\medskip\noskiphint#1\par}
\def\itemhint#1\par{\nobreak\smallskip\item{}{\it Hint:\/}\enspace#1\par}
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\goodbreak\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\firstpart#1{\nobreak\medskip\indent\llap{#1\enspace}\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\def\ipmod#1{\;({\rm mod}\,\,#1)}  % looks better inline than \pmod does

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Homework assignment~5}
\smallskip
\centerline{Assigned Monday, March~15, 2010. Due Wednesday, March~24, 2010.}

\bigskip

\noindent Work at least {\bf FOUR} of the following problems, at least one of
which must be from Part~B. All problems are of equal weight. If you submit
solutions for more than four problems, you will get credit for your best four
(with the proviso that you will get credit for at most three problems from
Part~A).

You are welcome to work with other students, but the solutions you hand~in
should be written in your own words. You are not allowed to see the paper
another student is going to hand~in. If you do collaborate with other students,
list their names. If you use other sources, cite them. Give credit where credit
is due. See the syllabus for more information about academic integrity.

Hints are encrypted with a {\it Caesar cipher}, in which each letter is
replaced by the letter three places ahead in the alphabet, wrapping around to
the beginning if necessary. For example, the letter~{\it A\/} is encrypted
as~{\it D}, and {\it Y\/}~is encrypted as~{\it B}. To decrypt the hints, move
each letter backward three places.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf--- Part~A ---}

\nobreak\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Make an addition table and a multiplication table for the integers
modulo~7 (in other words, for remainders after division by~7).

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem The country of Euclidia has an awkward currency system. The basic unit
of currency there is called the yakblat. There are only two kinds of coins: the
pizpaz, which is worth 24~yakblats, and the burbox, which is worth 57~yakblats.
(In particular, there is no such thing as a one-yakblat coin.)

When I visited Euclidia, I went into a shop to buy a piece of bubble gum, which
cost 15~yakblats. Paying for such an item in Euclidia requires the making of
change: I significantly overpaid when I handed the cashier my coins, and then
the cashier handed me the proper amount of change so that my net purchase came
out to 15~yakblats. Fortunately the cashier and I both had big buckets of
coins, so we had as many pizpazzes and burboxes as we required.

Your goal is to find a way to pay exactly 15~yakblats in such a transaction.

\nobreak\smallskip

\item{(a)} Write a linear Diophantine equation representing this situation. You
will need to introduce appropriate variables. Explain, carefully and precisely,
what quantities your variables represent.

\nobreak\smallskip

\item{(b)} Find a solution to the linear Diophantine equation you wrote in
part~(a). You might use the extended Euclidean algorithm described on the
handout given in class, or the method described on pages~127--137 of
{\it Problem Solving Through Recreational Mathematics}. Or you can use a
different method.

\nobreak\smallskip

\item{(c)} Interpret your solution from part~(b). In other words, what coins
should I hand the cashier, and what coins should the cashier give me as change?

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Let
$$\eqalign{
	A&=\{1,2,3,4,5\},\cr
	B&=\{\,x\mid\hbox{$x$ is even}\,\},\cr
	C&=\{\,x\mid\hbox{$x$ is a multiple of~3}\,\},\hbox{ and}\cr
	D&=\{\,x\mid\hbox{$x$ is prime}\,\},\cr
}$$
where the universal set is the set of all positive integers no greater than~20.

\nobreak\smallskip

\item{(a)} What is $A\cup C$? What is the cardinality of~$A\cup C$?

\nobreak\smallskip

\item{(b)} What is $B\cap C$? What is the cardinality of~$B\cap C$?

\nobreak\smallskip

\item{(c)} What are $A\setminus D$ and $D\setminus A$? What are the
cardinalities of these sets?

\nobreak\smallskip

\item{(d)} What is $\overline A$? What is the cardinality of~$\overline A$?

\nobreak\smallskip

\item{(e)} What is $(B\cup D)\cap\overline A$? What is the cardinality of this
set?

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Let $A=\{1,2\}$, $B=\{1,3\}$, $C=\{3\}$, and $D=\{1,2,3\}$.

\nobreak\smallskip

\item{(a)} Use set-builder notation to describe~$D$.

\nobreak\smallskip

\item{(b)} Which of these sets are subsets of which other of these sets? In
other words, list all true statements of the form $X\subseteq Y$, where $X$
and~$Y$ are to be replaced with $A$,~$B$, $C$, or~$D$.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf--- Part~B ---}

\nobreak\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Write a short story that explains or demonstrates the ideas of modular
arithmetic (in particular, how addition and multiplication work). Ideally, this
should be a story that could be illustrated and made into a children's book. Be
creative.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Prove that the Diophantine equation $n^2=3k+2$ has no integer
solutions.

\hint Wklqn derxw wkh srvvleoh uhpdlqghuv zkhq $q$~lv glylghg eb wkuhh.
Frqvlghu hdfk ri wkh wkuhh srvvlelolwlhv vhsdudwhob. Zkdw grhv wkh uljkw-kdqg
vlgh ri wkh htxdwlrq lpsob?

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Let $d$ be a fixed positive integer, with $d\ge2$. We saw in class
that remainders after division by~$d$ can be added, subtracted, and multiplied;
in other words, arithmetic modulo~$d$ makes sense. Mathematicians use the word
{\it ring\/} to describe a ``place'' where we can add, subtract, and multiply.
So another way to express the fact that remainders after division by~$d$ can be
added, subtracted, and multiplied is to say that the integers modulo~$d$ form a
ring.

What about division? A ring in which division also makes sense (except division
by zero) is called a {\it field}. Does it make sense to divide remainders after
division by~$d$? In other words, do the integers modulo~$d$ form a field? This
is the question we will explore in this problem.

What does division mean, anyway? Division should be the opposite of
multiplication, so the division problem $a\div b\equiv c\ipmod d$ should mean
that $b\times c\equiv a\ipmod d$. This is how you should think about division
for the purposes of this problem.

\nobreak\smallskip

\item{(a)} Part of Problem~1 is to make a multiplication table for the integers
modulo~7. (If you haven't done Problem~1 yet, it is probably worthwhile to do
it now.) Let's consider the division problem~$a\div b$, where $a$ and~$b$ are
integers modulo~7 and $b\not=0$. (Division by zero is always bad.) If $a\div b$
is to make sense, there should be some value for~$c$ (an integer modulo~7) such
that $b\times c\equiv a\ipmod7$. Using the multiplication table from Problem~1,
show that, no matter which values are chosen for $a$ and~$b$ (as long as
$b\not=0$), there is exactly one value for~$c$ such that
$b\times c\equiv a\ipmod7$. Explain why this means that division makes sense
modulo~7.

\itemhint Orrn dw wkh urzv dqg wkh froxpqv ri wkh pxowlsolfdwlrq wdeoh.

\nobreak\smallskip

\item{(b)} What is $3\div5\ipmod7$?

\itemhint Xvh wkh pxowlsolfdwlrq wdeoh.

\nobreak\smallskip

\item{(c)} Now make a multiplication table for the integers modulo~6. Show that
there is no value for~$c$ such that $3\times c\equiv5\ipmod6$, and explain why
this means that the division problem $3\div5\ipmod6$ does not have an answer.

\nobreak\smallskip

\noindent These examples show that the integers modulo~$d$ form a field for
{\it some\/} values of~$d$, but not all. In fact, it turns out that the
integers modulo~$d$ form a field if and only~if the number~$d$ is prime.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Let $A$,~$B$, and~$C$ be sets.

\nobreak\smallskip

\item{(a)} Write an expression for~$A\cap B$ without using the $\cap$~symbol.
(You can use unions, complements, set differences, and parentheses. Be sure
to use parentheses if you need them to avoid ambiguity.)

\nobreak\smallskip

\item{(b)} Write an expression for $A\cap B\cap C$ without using the
$\cap$~symbol.

\hint Xvh Yhqq gldjudpv.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
