% Solutions for the prerequisite test, CSCE 235, spring 2007 % 12 January 2007 \magnification=1200 \pdfpagewidth=8.5truein \pdfpageheight=11truein \hsize=6.5truein \vsize=9truein \pdfhorigin=1truein \pdfvorigin=1truein \headline={\hfil} \footline={\hfil} \long\def\solution#1\endsolution{{\narrower\noindent{\bf Solution.}\quad{#1}\par}} \centerline{CSCE~235: Introduction to Discrete Structures} \centerline{Prerequisite test (solutions)} \centerline{January~12, 2007} \medskip {\parindent=0in Name: [SOLUTIONS] \medskip Have you taken CSCE~155/155H? If so, what was your grade? \medskip Have you taken MATH~106/108H? } % end \parindent=0in \bigskip \noindent This test consists of five questions worth a total of 30~points. You have 20~minutes to complete the test. You must show all steps, including any computations or explanations, that led you to your answers. \bigskip \item{1.} (5~points) Let $\max(a,b)$ be the function that returns the maximum of the two numbers $a$ and~$b$, and let $\min(a,b)$ be the function that returns the minimum of the two numbers $a$ and~$b$. What is the value of $$\max\biggl(a,\min\Bigl(\max\bigl(b,\min(a,b)\bigr),\min\bigl(a,\max(a,b)\bigr)\Bigr)\biggr)?$$ \medskip \solution If $a\le b$, then $\min(a,b)=a$, so $$\max\bigl(b,\min(a,b)\bigr)=\max(b,a)=b.$$ On the other hand, if $a>b$, then $\min(a,b)=b$, so $$\max\bigl(b,\min(a,b)\bigr)=\max(b,b)=b.$$ In either case, then, we see that $$\max\bigl(b,\min(a,b)\bigr)=b.$$ Similar reasoning shows that $$\min\bigl(a,\max(a,b)\bigr)=a$$ and $$\max\bigl(a,\min(b,a)\bigr)=a.$$ Therefore, $$\max\biggl(a,\min\Bigl(\underbrace{\max\bigl(b,\min(a,b)\bigr)}_{\textstyle b}, \underbrace{\min\bigl(a,\max(a,b)\bigr)}_{\textstyle a}\Bigr)\biggr) =\max\bigl(a,\min(b,a)\bigr)=a.$$ \endsolution \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \item{2.} (4~points) In {\it The Hitchhiker's Guide to the Galaxy}, Douglas Adams says that the answer to the Question of Life, the Universe, and Everything is~42. Express the decimal number~42 in \smallskip \itemitem{(a)} binary. \medskip \solution The decimal system is based on powers of~10, so the decimal number~42 means $(4\times10^1)+(2\times10^0)$. The binary system works the same way, but it is based on powers of~2. Just as the digits in the decimal system can range from 0 to~9 (one less than~10), the digits in the binary system can range from 0 to~1 (one less than~2). We want to express~42 as a sum of powers of~2. We can do this as follows: $$\vbox{\offinterlineskip \halign{&\strut\quad\hfil$#$\quad&\vrule#\cr 2^5&&2^4&&2^3&&2^2&&2^1&&2^0\cr 32&&16&&8&&4&&2&&1\cr \omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit\cr \noalign{\hrule} \omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit\cr 1&&0&&1&&0&&1&&0\cr}}$$ since $$(1\times2^5)+(0\times2^4)+(1\times2^3)+(0\times2^2)+(1\times2^1)+(0\times2^0) =32+8+2=42.$$ Therefore, the decimal number~42 is expressed in binary as 101010. \endsolution \medskip \itemitem{(b)} base~5. \medskip \solution In base~5, we express a number as a sum of powers of~5, with digits ranging from 0 to~4 (one less than~5). To express the decimal number~42 in base~5, we find $$\vbox{\offinterlineskip \halign{&\strut\quad\hfil$#$\quad&\vrule#\cr 5^2&&5^1&&5^0\cr 25&&5&&1\cr \omit&height2pt&\omit&&\omit\cr \noalign{\hrule} \omit&height2pt&\omit&&\omit\cr 1&&3&&2\cr}}$$ since $$(1\times5^2)+(3\times5^1)+(2\times5^0)=25+15+2=42.$$ Therefore, the decimal number~42 is expressed in base~5 as~132. \endsolution \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \item{3.} (4~points) \smallskip \itemitem{(a)} A document is enlarged by a factor of~150\% on a photocopier. By what factor must the copy be reduced to produce a copy the same size as the original? \medskip \solution Let $x$ represent the original size of the document. The copy was made by setting the photocopier to~150\%, so the size of the copy is~$1.5x$. We want to find the factor~$y$ at which we should set the photocopier so that the copy of the copy will be the same size as the original document; in other words, we want to find $y$ such that $$(1.5x)y=x.$$ We may make the reasonable assumption that $x\not=0$, so we can divide both sides of this equation by~$x$ to obtain $$1.5y=1.$$ Solving for~$y$, we find that $y=0.666\ldots=2/3$, so the factor by which we must reduce the copy is~$66{2\over3}\%$. \endsolution \medskip \itemitem{(b)} Sam and Kim both started new jobs at the beginning of~2005, with the same starting salary. At the end of~2005, Sam received a 10\%~raise, while Kim's salary was reduced by~5\%. At the end of~2006, however, it was Kim who received the 10\%~raise, and Sam's salary fell by~5\%. After these two sets of salary adjustments, whose salary is larger? \medskip \solution Let $x$ represent the salary at the beginning of~2005, so both Sam and Kim had a salary of~$x$ at the beginning of~2005. At the end of~2005, Sam's salary increases by~10\%, so it becomes 110\% of its original value; therefore, Sam's salary at the beginning of~2006 is~$1.10x$. Similarly, Kim's salary drops by~5\% at the end of~2005, so it becomes 95\% of its original value; therefore, Kim's salary at the beginning of~2006 is~$0.95x$. Now, at the end of~2006, Sam's salary is decreased by~5\%, so its value at the beginning of~2007 is 95\% of its value at the beginning of~2006. Thus, at the beginning of~2007, Sam's salary is~$0.95(1.10x)$. On the other hand, Kim's salary is raised by~10\% at the end of~2006, so its value at the beginning of~2007 is 110\% of its value at the beginning of~2006; hence Kim's salary at the beginning of~2007 is~$1.10(0.95x)$. We are asked to compare the two salaries after these two sets of salary adjustments, that~is, at the beginning of~2007. At this time, Sam's salary is~$0.95(1.10x)$ and Kim's salary is~$1.10(0.95x)$. Since multiplication is commutative, these two quantities are equal. Therefore, Sam and Kim have the same salary after these two sets of salary adjustments. \endsolution \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \item{4.} (8~points) What is the output of the following pseudocode? {\narrower\narrower\medskip\parindent=0in $n:=13$ {\bf while} $n>1$ {\bf do} \qquad{\bf output} $n$ \qquad{\bf if} $n$ is even {\bf then} \qquad\qquad$n:=n/2$ \qquad{\bf else} \qquad\qquad$n:=3n+1$ \qquad{\bf end} {\bf end} \medskip} \solution The first line initializes the variable~$n$ to the value~13. The program then enters a loop, in which it will remain as long as the value of~$n$ is greater than~1. This condition is initially satisfied, since $13>1$, so program begins executing the statements inside the loop. The first statement in the loop causes the program to output the value of~$n$, which at this point is~13. Next, a conditional statement is reached, which tests whether the value of~$n$ is even. Currently the value of~$n$ is~13, which is odd, so the statement following the keyword~{\bf else} is executed, which computes the value $3n+1=3\times13+1=40$ and stores this value in the variable~$n$. Now control jumps back to the loop condition again, and the program tests whether the value of~$n$ is greater than~1. It is, since $40>1$, so the program executes the statements inside the loop again. First, the value of~$n$ is output; currently this value is~40. Then the evenness of~$n$ is tested. This condition is now true, so the program computes the value $n/2=40/2=20$ and stores this value in the variable~$n$. Again, control jumps back to the loop condition. This process continues for as long as the value in~$n$ is greater than~1. Therefore, we see that the output of the program will be the list of numbers $$\hbox{13, 40, 20, 10, 5, 16, 8, 4, 2.}$$ It is important to note that the value~1 will not be output, because when the value of~$n$ is~1, the loop condition is false (as $1\not>1$), and so the statements inside the loop will not be executed. \endsolution \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \item{5.} (9~points) An economist predicts, ``If the United States does not reduce its trade deficit, then the country will fall into a recession.'' \smallskip \itemitem{(a)} Based on this prediction, is it reasonable to conclude that ``if the United States falls into a recession, it must be because the trade deficit was not reduced''? Why or why not? \medskip \solution No. The country may fall into a recession for some other reason. This statement is the {\it converse\/} of the original prediction. \endsolution \medskip \itemitem{(b)} Based on this prediction, is it reasonable to conclude that ``if the United States does not fall into a recession, then the trade deficit must have been reduced''? Why or why not? \medskip \solution Yes. The only way the United States can avoid falling into a recession is by reducing its trade deficit. (Reducing the trade deficit is not sufficient to guarantee that the country will not experience a recession, but it is necessary.) If the trade deficit had not been reduced, then according to the economist's prediction the United States would have fallen into a recession. The statement in part~(b) is the {\it contrapositive\/} of the original prediction. \endsolution \medskip \itemitem{(c)} Based on this prediction, is it reasonable to conclude that ``if the United States reduces its trade deficit, then the country will not fall into a recession''? Why or why not? \medskip \solution No. Some other crisis may plunge the country into a recession. This statement is the {\it inverse\/} of the original prediction, and as such it is logically equivalent to the statement in part~(a). \endsolution %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye