% Homework 5 solutions, 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|} % 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}} \centerline{CSCE~235: Introduction to Discrete Structures} \centerline{{\bf Homework assignment~5} (solutions)} \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? \solution First we count the total number of strings consisting of four upper-case letters. There are 26~choices for the first letter, 26~choices for the second letter, 26~choices for the third letter, and 26~choices for the fourth letter. By the product rule, then, there are a total of $26^4=456\,976$~strings consisting of four upper-case letters. We now count the number of these strings that do {\it not\/} contain the letter~Q. If we leave out the letter~Q, there are 25~choices for each position, for a total of $25^4=390\,625$~four-letter strings that do not contain the letter~Q. The number of strings that consist of four upper-case letters and {\it do\/} contain the letter~Q must therefore be $456\,976-390\,625=66\,351$. \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? \solution There are 71~possible remainders when an integer is divided by~71 (namely, 0,~1, 2, \dots,~70). Suppose that 498~integers are generated. Consider these integers to be objects, each of which is placed into one of 71~boxes representing its remainder when divided by~71. By the generalized pigeonhole principle, at least one of these boxes must contain at least $\lceil498/71\rceil=8$~objects, that~is, at least eight of the 498~integers must have the same remainder when divided by~71. Therefore generating 498~integers is sufficient. To show that 497~integers are not sufficient, we observe that if 497~objects are placed into 71~boxes, it is possible that each of the 71~boxes (the possible remainders) will contain exactly seven objects; in other words, if we generate 497~integers, we are not guaranteed that eight of them will have the same remainder when divided by~71. Therefore 498 is the minimum number of integers that 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. \solution We begin by counting the number of possible wages less than one million dollars. To generate such a wage, we must place a digit from 0 through~9 in the hundred-thousand-dollars' place, another digit from 0 through~9 in the ten-thousand-dollars' place, and so on, finishing by placing a digit from 0 through~9 in the cents' place. There are a total of eight positions that must be filled with a digit, and each position can take any of ten values, so there are $10^8=100$~million possible wages less than one million dollars. However, this count includes a wage of zero dollars; since a person who earns zero dollars is not a wage earner, we remove this possibility from consideration, and are left with $99\,999\,999$~different non-zero wages less than one million dollars. Imagine the 100~million wage earners in the United States as objects that are being placed into boxes according to the wage they earned last year. We have just seen that there are $99\,999\,999$~possible wages, so we are placing 100~million objects into $99\,999\,999$~boxes. By the pigeonhole principle, at least one of these boxes must contain at least two objects, which is to say that at least two wage earners in the United States earned exactly the same amount of money 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? \solution The first work unit can be given to any of the twelve available computers. After the first work unit has been assigned, the second work unit can be given to any of the eleven remaining available computers. Then the third work unit can be given to any of the ten computers left, the fourth can be given to any of nine computers, and the fifth must go to one of the eight remaining computers. Therefore there are a total of $12\times11\times10\times9\times8=95\,040$~ways in which the five work units can be distributed. Alternatively, we observe that the number of ways to distribute the work units is the number of 5-permutations of a set with 12~elements, which is $$P(12,5)={12!\over(12-5)!}=95\,040.$$ \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? \solution Norbert must select five of the ten shells to claim as his own, and then the remaining five will go to Helga. The number of ways to do this is the number of 5-combinations of a set with 10~elements, which is $$C(10,5)={10\choose5}={10!\over5!(10-5)!}=252.$$ We are counting combinations here, not permutations, because the {\it order\/} in which Norbert chooses his five shells does not matter. \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? \solution In the first case, we are choosing seven members out of a pool of~53; the number of ways to do this is the number of 7-combinations of a set with 53~elements, which is $$C(53,7)={53\choose7}={53!\over7!(53-7)!}= {53\times52\times\cdots\times47\over7!}=154\,143\,080.$$ We are counting combinations, not permutations, because we are assuming that the order in which the members are chosen does not matter. If the oldest member of parliament is guaranteed a position on the committee, then we have six remaining positions on the committee that must be filled from a pool of 52~people. The number of ways to choose six people from~52 is the number of 6-combinations of a set with 52~elements, which is $$C(52,6)={52\choose6}={52!\over6!(52-6)!}= {52\times51\times\cdots\times47\over6!}=20\,358\,520.$$ \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$. \solution Using the binomial theorem with $x=2$ and $y=2$, we see that $$4^n=(2+2)^n=\sum_{k=0}^n{n\choose k}2^{n-k}2^k=\sum_{k=0}^n{n\choose k}2^n =2^n\sum_{k=0}^n{n\choose k}.$$ Therefore, the left-hand side is equal to~$4^n$. Another way to see this is to use Corollary~1 from Section~5.4 of the book directly: $$4^n=2^n2^n=2^n\sum_{k=0}^n{n\choose k}.$$ For the right-hand side, we use the binomial theorem with $x=1$ and $y=3$ to get $$4^n=(1+3)^n=\sum_{k=0}^n{n\choose k}1^{n-k}3^k=\sum_{k=0}^n3^k{n\choose k}.$$ Hence the right-hand side is also equal to~$4^n$. Since both sides of the formula are equal to~$4^n$, they must be equal to each other, so $$2^n\sum_{k=0}^n{n\choose k}=\sum_{k=0}^n3^k{n\choose k}.\eqno\hbox{\qed}$$ \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. { \def\star{{\,{*}\,}} \def\bar{{\,{|}\,}} \solution Imagine the six people being six boxes into which we are going to place the thirty trinkets. We can set this problem up using the stars-and-bars technique, with five bars separating thirty stars, representing the distribution of the thirty trinkets among the six people. For example, if all thirty trinkets are given to the first person, we can write $$\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\star\bar\bar\bar\bar\bar;$$ if the trinkets are distributed evenly, we can write $$\star\star\star\star\star\bar\star\star\star\star\star\bar\star\star\star\star\star\bar\star\star\star\star\star\bar\star\star\star\star\star\bar\star\star\star\star\star;$$ and a random distribution might look like $$\star\star\star\star\star\star\star\star\bar\star\star\star\bar\star\star\star\star\star\bar\star\star\star\star\star\star\star\star\star\bar\star\bar\star\star\star\star.$$ Each such string consists of a total of 35~symbols, five of which are bars. Therefore, the total number of possible strings is the number of ways to choose which five of the 35~symbols are to be bars, i.e., the number of 5-combinations of a set with 35~elements, which is $$C(35,5)={35\choose5}={35!\over5!(35-5)!}= {35\times34\times33\times32\times31\over5\times4\times3\times2\times1}=324\,632.$$ Thus there are $324\,632$~different ways in which the thirty trinkets can be distributed among the six people. } % end \def\star, \def\bar \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 \solution \part{(a)} All of the letters of ORANGE are distinct, so we are counting the number of permutations of a set with six elements, which is $6!=120$. So there are 120~different strings that may be formed by rearranging the letters in ORANGE. \part{(b)} SASSAFRAS contains nine letters: four~{\it S\/}s, three~{\it A\/}s, one~{\it F}, and one~{\it R}. Therefore the number of different ways to rearrange the letters of SASSAFRAS is $${9!\over4!3!1!1!}=2520.$$ \part{(c)} As in part~(a), we notice that all of the letters of UNCOPYRIGHTABLE are distinct (this is actually one of the two longest words in the English language having this property, the other word being DERMATOGLYPHICS). Therefore the number of different ways to rearrange the letters of UNCOPYRIGHTABLE, which has 15~letters, is the number of permutations of a set with 15~elements, which is $15!=1\,307\,674\,368\,000$. \part{(d)} The word EXTRACURRICULAR has 15~letters: one~{\it E}, one~{\it X}, one~{\it T}, four~{\it R\/}s, two~{\it A\/}s, two~{\it C\/}s, two~{\it U\/}s, one~{\it I}, and one~{\it L}. Hence the number of different strings that can be formed by rearranging the letters of EXTRACURRICULAR is $${15!\over1!1!1!4!2!2!2!1!1!}=6\,810\,804\,000.$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye