\documentclass[letterpaper,12pt]{article}
\usepackage{amsmath,  hyperref, graphicx,color,enumitem,icomma,ifsym,epsdice}
\usepackage[letterpaper]{geometry}
\def\begen{\begin{enumerate}[align=left,leftmargin=*]}
\def\begena{\begin{enumerate}[align=left,leftmargin=*,label=(\alph*)]}
 \def\enden{\end{enumerate}}
\def\ss{ }
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\qed{\quad{$\square$}\smallskip}
\usepackage{mathrsfs}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\def\eps{\varepsilon}
\parindent0pt
\parskip5pt
\def\ds{\displaystyle}
  \def\jmp{\medskip\hrule\medskip}
    \def\jmpr{\medskip\hrule\medskip\hrule\medskip\hrule\medskip}

\pagenumbering{gobble} 
 
\def\crz{\cr\noalign{\ss}}
\def\ds{\displaystyle}
\usepackage{fancyhdr}
\def\scr{$\underline{\hskip1in}$}
\def\scrr{$\underline{\hskip1.2in}$}

\def\ans#1{$\underline{\hskip.3in\color{red}#1\color{black}\hskip.3in}$}
\pagestyle{fancy}
\textheight=9in
  \headsep=10pt

\begin{document}

\lhead{Math  2001--004:  Introduction to Discrete Mathematics}
\chead{} \rhead{Fall 2024}
 

\centerline{\bf Solutions to Selected Exercises, HW \#6
}

Assignment:

\begin{itemize}
   \setlength{\itemsep}{1pt}
    \setlength{\parskip}{0pt}
    \setlength{\parsep}{0pt}
\item BOP Section 3.2, page 73: Exercises 1, 2, 5, 6, 7.

\item BOP  Section 3.3, page 77: Exercises  3, 4, 5, 6, 8, 11, 12.

\item BOP Section 3.4, page 84: Exercises  3,   7, 8,  16.

\item BOP Section 3.7, page 95: Exercises  3, 4ab, 10, 11.
 \end{itemize}

  {\large\bf\color{red} BOP, Section 3.2}
  
{\bf\color{red} Exercise 2. }  Airports are identified with 3-letter codes. For example, Richmond, Virginia has
the code $RIC$, and Memphis, Tennessee has $MEM$. How many different 3-letter
codes are possible?

{\bf\color{red} Solution. }  $26^3=17,576$.\jmp

{\bf\color{red}  Exercise 6. } You toss a coin, then roll a die, and then draw a card from a 52-card deck. How
many different outcomes are there? How many outcomes are there in which the
die lands on $\epsdice{3}$? How many outcomes are there in which the die lands on an
odd number? How many outcomes are there in which the die lands on an odd
number and the card is a King?

{\bf\color{red} Solution. }  $2\cdot 6\cdot 52=624$ outcomes.  $2\cdot1\cdot 52=104$ ways in which the die lands on $\epsdice{3}$. $2\cdot3\cdot 52=312$  ways in which the die lands on an odd number. $2\cdot3\cdot 4=24$ ways in which the die lands on an odd number and the card is a King.
 
\jmpr

  {\large\bf\color{red} BOP, Section 3.3}
  
  {\bf\color{red} Exercise 4. } Five cards are dealt off of a standard 52-card deck and lined up in a row. How
many such lineups are there in which exactly one of the 5 cards is a queen?

{\bf\color{red} Solution. }  $5\cdot(4\cdot 48\cdot 47\cdot 46\cdot 45)=93,398,400$.

\jmp

 {\bf\color{red} Exercise 6. } Consider lists made from the symbols $A, B, C, D, E$, with repetition allowed.
 
 {\bf\color{red}(a)} How many such length-5 lists have at least one letter repeated?
 
 {\bf\color{red} Solution. } The number with at least one letter repeated is the total number of length-5 lists minus the number with no letters repeated, which is 
 
 $$5^5-5\cdot4\cdot3\cdot2\cdot1=3,005.$$

 {\bf\color{red}(b)} How many such length-6 lists have at least one letter repeated?
 
 {\bf\color{red} Solution. } There are only five letters, so any 6-letter list must have a repeat, so there are $5^6=15,625$ 6-letter lists (with at least one repeat).
 
 \jmp
 
  {\bf\color{red} Exercise 8. } This problem concerns lists made from the letters $A, B, C, D, E,$ $ F, G, H, I, J$.
  
  
 {\bf\color{red}(a)} How many length-5 lists can be made from these letters if repetition is
not allowed and the list must begin with a vowel?

 {\bf\color{red} Solution. } $3\cdot 9\cdot8\cdot7\cdot6=9,072$.
 
 {\bf\color{red}
 (b)} How many length-5 lists can be made from these letters if repetition is
not allowed and the list must begin and end with a vowel?

 {\bf\color{red} Solution. } $3\cdot 8\cdot7\cdot6\cdot2=2,016$.
 
 {\bf\color{red}(c)} How many length-5 lists can be made from these letters if repetition is
not allowed and the list must contain exactly one A?

 {\bf\color{red} Solution. }
 $5\cdot(1\cdot9\cdot8\cdot7\cdot6)=15,120$.
 
 \jmp
 
  {\bf\color{red} Exercise 12. }   Six math books, four physics books and three chemistry books are arranged on a shelf. How many arrangements are possible if all books of the same subject are grouped together?
  
   {\bf\color{red} Solution. } There are $6!$ arrangements of the math books, $4!$ of the physics books, and $3!$ of the chemistry books.  Once all subjects are arranged, there are $3!$ ways to arrange the three subjects.  This yields
   
   $$6!\cdot 4!\cdot 3!\cdot 3!=622,080$$total arrangements.
 
 \jmpr
 
 
  {\large\bf\color{red} BOP, Section 3.4 }
     
      {\bf\color{red} Exercise 8. } Compute how many 7-digit numbers can be made from the digits $1, 2, 3, 4, 5, 6, 7$
if there is no repetition and the odd digits must appear in an unbroken sequence.
(Examples: 3571264 or 2413576 or 2467531, etc., but not 7234615.)

  {\bf\color{red} Solution. }  There are 4 odd digits in this set of integers, so the number of unbroken sequences of these 4  odd digits is $4!$.  Such an unbroken sequence can occur as the first four digits in the 7-digit number, or as digits 2 through 5, or digits 3 though 6, or digits 4 through 7.  For each of these four choices of where to put the odd digits, the number of ways that the remaining three spaces can be filled in with the remaining 3 even digits is $3!=6$.  So the total number of 7-digit numbers with   no repetition and with the odd digits  appearing in an unbroken sequence is
  
  $$4!\cdot 4\cdot 3!=576.$$
          \jmp
 
      {\bf\color{red} Exercise 16. } How many 4-permutations are there of the set $\{A,B,C,D,E,F\}$
if whenever $A$
appears in the permutation, it is followed by $E$?

  {\bf\color{red} Solution. } Since any $A$ must be followed by an $E$, an $A$ can only appear in the first, second, or third place (it can't appear in the fourth, since then the $E$ would have to be fifth, but there are only four places). Or an $A$ might not appear at all.
  
   The number of sequences starting with $AE$ is $1\cdot1\cdot 4\cdot3=12$, as is the number with $AE$ in the second and third slots, as is the number with $AE$ in the third and fourth slots.  The number with no $A$ is $5\cdot4\cdot3\cdot2$.  So the total number where any  $A$
is followed by $E$ is

$$  12+ 12+12+5\cdot4\cdot3\cdot2=156.$$

\jmpr


  {\large\bf\color{red} BOP, Section 3.7}
  
    {\bf\color{red} Exercise 4. } This problem involves lists made from the letters $T, H, E, O, R, Y$, with repetition
allowed.

  {\bf\color{red}(a)} How many 4-letter lists are there that don’t begin with $T$, or don’t end in $Y$?
  
    {\bf\color{red} Solution. } 
  The total number of 4-letter lists is $6^4$.  The number that begin with $T$ {\it and} end in $Y$ is $1\cdot 6\cdot 6\cdot1=36$.  So the number that don’t begin with $T$ {\it or} don’t end in $Y$ is
    $$6^4-36=1,260.$$
    
  {\bf\color{red}(b)} How many 4-letter lists are there in which the sequence of letters $T$, $H$, $E$
appears consecutively (in that order)?

    {\bf\color{red} Solution. } Such a list is either of the form $THE*$, where the ``$*$'' means ``any one of the 6 letters,'' or of the form $*THE$.  So there are $6+6=12$ such lists.
\jmp

    {\bf\color{red} Exercise 10. }  How many 6-digit numbers are even or are divisible by 5?
    
        {\bf\color{red} Solution. } An even number is one whose last digit is 0,2,4,6,8, and a number divisible by 5 is one whose last digit is either 0 or 5.
        
        The number of 6-digit numbers that end in 0,2,4,6, or 8 is $9\cdot 10^4\cdot 5$. (There are 9 choices for the first digit, since the first digit can't be 0, then 10 choices for digits 2 through 5, then 5 choices for the last digit.). The number of 6-digit numbers that end in 0 or 5 is $9\cdot 10^4\cdot 2.$ The number that are even {\it and} divisible by 5 are exactly those whose last digit is 0;  There are $9\cdot 10^4\cdot 1$ of these.  Sothe number that  are even {\it or} are divisible by 5 is
        $$9\cdot 10^4\cdot 5+9\cdot 10^4\cdot 2-9\cdot 10^4\cdot 1=540,000.$$
        Here's another method:  to say a 6-digit numbers is even or is divisible by 5 is to say it ends in 0,2,4,5,6, or 8.  There are 
        $$9\cdot 10^4\cdot 6=540,000$$such numbers.
        
        \jmpr
\end{document}
 



