%  Homework assignment 4
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Friday, February 19, 2010. Due: Friday, February 26, 2010.
%  Brian Kell <bkell@cmu.edu>

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

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\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\lcm{\mathop{\rm lcm}}  \def\gcd{\mathop{\rm gcd}}

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

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Homework assignment~4}
\smallskip
\centerline{Assigned Friday, February~19, 2010. Due Friday, February~26, 2010.}

\bigskip

\noindent Work at least {\bf FOUR} of the following problems. All problems are
of equal weight. If you submit solutions for more than four problems, you will
get credit for your best four.

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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Recall that $n!$, read ``$n$~factorial,'' is the number
$n\times(n-1)\times(n-2)\times\cdots\times3\times2\times1$. For example,
$5!=5\times4\times3\times2\times1=120$. The number~$110!$~ends with a bunch of
zeroes. How many?

\hint Wklqn derxw idfwruv. Zkdw zloo fdxvh d chur dw wkh hqg? Zkdw zloo fdxvh
wzr churhv dw wkh hqg?

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

\problem What is the remainder when $3^{21,110}$ is divided by~7?

\hint Ilqg d sdwwhuq.

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

\problem In class we showed that the least common multiple of 10 and~12 is
$\lcm(10,12)=60$ and the greatest common divisor of 10 and~12 is
$\gcd(10,12)=2$. We then observed that $10\times12=120$ and $60\times2=120$.
Does this always happen? In other words, is it true that for {\it every\/}
possible pair of positive integers $a$ and~$b$,
$$a\cdot b=\lcm(a,b)\cdot\gcd(a,b)?$$
If so, explain why. If not, give a counterexample (that~is, give two positive
integers $a$ and~$b$ for which this statement is false).

\hint Frqvlghu krz wr ilqg wkh ofp dqg wkh jfg iurp wkh sulph idfwrulcdwlrqv ri
$d$ dqg~$e$.

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

\problem A long hallway has 100~light bulbs, numbered 1 through~100. Each light
bulb has a pull string; when the string is pulled, the light bulb turns on if
it was off, and turns off if it was on. All of the light bulbs are initially
off.

One person walks into the hall, pulls every string, and walks out. Then a
second person enters, pulls the strings of light bulbs 2,~4, 6, 8, and so on,
and leaves. Next, a third person comes in, pulls strings 3,~6, 9, 12, and so
on, and exits. This pattern continues until 100~people have walked in, pulled
some of the strings, and walked out. (Note that the 100th person will pull only
string~100.)

After all 100~people have done this, which light bulbs are on? More
importantly, why?

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

\problem Consider the polynomial function $f(x)=x^2+x+41$. Compute the values
$f(0)$,~$f(1)$, $f(2)$, $f(3)$, \dots,~$f(20)$. What can you say about the
{\it primality\/} of these numbers? (That~is, are they prime numbers or not?)
Does this pattern continue forever? Why or why not?

\nobreak\medskip

\noindent[This interesting property of this polynomial was discovered by the
Swiss mathematician Leonhard Euler (pronounced ``Oiler'') in~1772.]

\hint Li brx duh jrlqj wr suryh wkdw wkh sdwwhuq frqwlqxhv iruhyhu, brx qhhg wr
hasodlq zkb $i(a)$ pxvw eh sulph iru hyhub qrqqhjdwlyh lqwhjhu~$a$. Li brx duh
jrlqj wr suryh wkdw wkh sdwwhuq grhv qrw frqwlqxh iruhyhu, brx qhhg wr ilqg d
vlqjoh ydoxh ri~$a$ wkdw euhdnv wkh sdwwhuq.

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

\problem Use the definition of divisibility to prove the following statement
about integers $a$,~$b$, $c$, $x$, and~$y$, where $a\not=0$: If $a\mid b$ and
$a\mid c$, then $a\mid(bx+cy)$.

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

\problem (``The Cashier's Error,'' from {\it The Moscow Puzzles\/} by Boris~A.
Kordemsky, edited by Martin Gardner.)\enspace The customer said to the
cashier: ``I have 2~packages of lard at 9~cents; 2~cakes of soap at 27~cents;
and 3~packages of sugar and 6~pastries, but I don't remember the prices of the
sugar and pastries.''

``That will be \$2.92.''

The customer said: ``You have made a mistake.''

The cashier checked again and agreed.

How did the customer spot the error?

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

\problem Use the Euclidean algorithm to find the greatest common divisor of
11,238,781 and 8,476,873.

\hint Brx fdq fkhfn brxu dqvzhu eb pdnlqj vxuh lw glylghv erwk ri wkh wzr jlyhq
qxpehuv.

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

\problem Investigate the powers of~2 (1,~2, 4, 8, 16,~$\dots$) and classify
them as abundant, deficient, or perfect. Can you make a conjecture about these
numbers? (Make your conjecture as specific as you can.)

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

\problem (From {\it Mathematical Recreations and Essays\/} by W.\thinspace W.
Rouse Ball and H.\thinspace S.\thinspace M. Coxeter.)\enspace Prove that every
sum of two consecutive odd primes is the product of three integers all greater
than~1. For example, $7+11=2\times3\times3$, and $11+13=2\times3\times4$.

\nobreak\medskip

\noindent[This is not as difficult as it sounds. Start with what you know and
see where you can go from there.]

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem An eccentric sheep farmer has built an enclosure with four separate
pens, as shown below. In the center of the enclosure is a rather unusual
four-sided gate. Whenever three sheep enter the gate from three different
sides, the fourth side of the gate opens and all three sheep enter the fourth
pen.

If there are initially 24,~28, 32, and 36 sheep in the four pens, respectively,
is it possible that after some time has passed there will be an equal number of
sheep in each pen? What if there are initially 12,~14, 16, and 18 sheep in the
four pens, respectively? In each case justify your answer by demonstrating how
it can be done or by proving that it is impossible.

\hint Brx pdb ilqg lw xvhixo wr zrun edfnzdugv. Frqvlghu krz wkh jdwh fkdqjhv
wkh qxpehu ri vkhhs lq hdfk shq. Lw pdb eh khosixo wr wklqn derxw uhpdlqghuv
zkhq fhuwdlq qxpehuv duh glylghg eb irxu.

$$\fig{homework-4-sheep-pen.mps}$$

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

\bye
