% Homework 5, CSCE 235, spring 2007
% Assigned 20 March 2007; due 26 March 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=8.5truein
\pdfhorigin=1.5truein \pdfvorigin=1.25truein

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\N{\mathord{\bf N}}  \def\Z{\mathord{\bf Z}}
\def\Q{\mathord{\bf Q}}  \def\R{\mathord{\bf R}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Homework assignment~5} (111~points)}
\centerline{Assigned Tuesday, March~20, 2007}
\centerline{Due Monday, March~26, 2007}

\bigskip

\noindent Justify your answers to the following questions carefully.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) How many strings consist of four upper-case letters and
contain the letter~Q?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) A computer program generates integers at random. How many
integers must be generated in order to guarantee that at least eight of the
integers have the same remainder when divided by~71?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Show that if there are 100~million wage earners in the
United States who earn less than a million dollars, then there are two who
earned exactly the same amount of money, to the penny, last year.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) A distributed computing project consists of a server that
distributes work units to several computers connected to a network. Suppose the
server has five different work units to distribute and there are twelve
available computers. In how many ways can the work units be distributed if no
computer can process more than one work unit?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Norbert and Helga are walking on the beach, collecting
seashells. They come across a pile of ten seashells, all beautiful and all
different. They agree to divide the pile evenly between them. In how many ways
can they do this?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (15~points) The parliament of the small country of Brualdia resolves
to form a new committee. The committee will be made up of seven members, chosen
from the 53~members of parliament. In how many ways can the committee be
formed? Suppose that the oldest member of parliament is guaranteed a position
on the committee; then how many ways can the committee be formed?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (20~points) Let $n$ be a nonnegative integer. Show that
$$2^n\sum_{k=0}^n{n\choose k}=\sum_{k=0}^n3^k{n\choose k}.$$
{\it Hint:\/} One way to do this is to show that the left-hand side and the
right-hand side are both equal to~$4^n$.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) In how many ways can thirty identical trinkets be
distributed among six people? It's fine if some people don't get any trinkets,
and only the number of trinkets each person gets matters. Giving Ralph all
thirty trinkets is different from giving Susan all thirty trinkets, but giving
Ralph the first fifteen trinkets and Susan the last fifteen is the same as
giving Susan the first fifteen and Ralph the last fifteen, because all the
trinkets are identical.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (16~points) How many different strings can be formed by rearranging
the letters in each of the following words?
\smallskip
\item{(a)} ORANGE
\item{(b)} SASSAFRAS
\item{(c)} UNCOPYRIGHTABLE
\item{(d)} EXTRACURRICULAR

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

\bye