1 files changed, 236 insertions, 0 deletions
diff --git a/howard/hw11.tex b/howard/hw11.tex
new file mode 100644
index 0000000..ec30878
--- /dev/null
+++ b/howard/hw11.tex
@@ -0,0 +1,236 @@
+\input tikz
+
+\newfam\bbold
+\def\bb#1{{\fam\bbold #1}}
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+
+\newcount\indentlevel
+\newcount\itno
+\def\reset{\itno=1}\reset
+\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
+\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
+\aftergroup\afterstartlist}
+\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
+    i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
+    s\or t\or u\or v\or w\or x\or y\or z\fi}
+\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
+                                  \alph\itno)\else
+                                  (\number\itno)\fi
+                           }%
+         #1\smallskip\advance\itno by 1\relax}
+\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}}
+\let\endul\egroup
+\def\hline{\noalign{\hrule}}
+\let\impl\rightarrow
+\newskip\tableskip
+\tableskip=10pt plus 10pt
+\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt
+depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}}
+\def\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+
+\li How many numbers must be selected from the set
+$\{1,4,6,8,9,13,14,16,18,21\}$ to guarantee that at least one pair of
+these numbers adds up to exactly 22? Simplify your answer to an integer.
+
+6 numbers must be selected. This set has five pairs that sum to 22, so
+we're putting 6 pigeons into 5 holes, which guarantees one pair is
+completed, and we get a sum to 22.
+
+\li How many different combinations of pennies, nickels, dimes, and
+quarters can a piggy bank contain if it has 29 coins in it? Simplify
+your answer to an integer.
+
+This is 29 coins into 4 categories, so
+$${29+4-1\choose 3} = 4960$$
+different possibilities for the coins in this piggy bank.
+
+\li How many different ways are there to choose 13 donuts if the shop
+offers 19 different varieties to choose from? Simplify your answer to an
+integer.
+
+This is equivalent to putting 13 indistinct balls into 19 urns, which by
+stars and bars is
+$${19+13-1\choose 13-1} = 141,\!120,\!525$$
+different choices.
+
+\li Imagine you are drawing cards from a standard deck of 52 cards. For
+each of the following, determine the minimum number of cards you must
+draw from the deck to guarantee that those cards have been drawn.
+Simplify all your answers to integers.
+
+{\startlist
+\li A Straight (5 cards of sequential rank). Hint: when considering the
+Ace, a straight could be A, 2, 3, 4, 5 or 10, J, Q, K, A, but no other
+wrap around is allowed.
+
+We must eliminate the 5 and the 10 to prevent us from getting a
+straight, so the highest number we can get before we get a straight is
+$(13-2)\cdot 4 = 44$ and we need 45 cards to guarantee us a straight.
+
+\li A Flush (5 cards of the same suit)
+
+We have 4 holes and we want to guarantee 5 cards in a hole, so by
+generalized pigeonhole, we need $4\cdot 4+1 = 17$ cards.
+
+\li A Full House (3 cards of 1 rank and 2 from a different rank)
+
+We have thirteen holes (ranks) and we want 3 pigeons in a hole, so
+generalized pigeonhole gives us $13\cdot 2 + 1 = 27$ cards.
+
+\li A Straight Flush (5 cards of sequential rank from the same suit)
+
+Once we are guaranteed a straight by part (a), we must have a straight
+flush since we already have most of the other cards in the same suit.
+Therefore, 45 cards guarantees us a straight flush.
+}
+
+\li How many integers between 1 and 1000 meet the criteria below.
+Simplify your answer to an integer.
+
+\ul
+
+\li the digits are distinct
+
+\li the digits are odd
+
+\li the digits are in ascending order
+
+\endul
+
+We start from the set of odd digits $\{1,3,5,7,9\},$ complete the
+picking process for one-, two-, and three-digits, and then reorder in
+ascending order.
+This gives us
+${5\choose 3} + {5\choose 2} + {5\choose 1} = 25$
+different numbers.
+
+\li How many teenagers (people from age 13--19) must you select to
+ensure that 4 of theme were born on the exact same date (mm/dd/yyyy)?
+Simplify your answer to an integer.
+
+We will use the generalized pigeonhole principle.
+This 7 year period includes either one or two leap years.
+If it includes one leap year, this is $7\cdot 365 + 1$ days and we will
+need $3\cdot(7\cdot 365 + 1) + 1$ teenagers to ensure 4 with the same
+birth date.
+
+\li A coin is flipped 10 times. Simplify your answers to integers.
+
+{\startlist
+
+\li How many possible outcomes are there?
+
+$$2^{10} = 1024.$$
+
+\li How many possible outcomes are there where the coin lands on heads
+at most 3 times?
+
+We treat the 0 heads, 1 head, 2 heads, and 3 heads cases:
+$${10\choose 0} + {10\choose 1} + {10\choose 2} + {10\choose 3} = 176.$$
+
+\li How many possible outcomes are there where the coin lands on heads
+more than it lands on tails?
+
+We treat the 0 tails, 1 tails, 2 tails, 3 tails, and 4 tails cases:
+$${10\choose 0} + {10\choose 1} + {10\choose 2} + {10\choose 3} +
+{10\choose 4} = 386.$$
+
+\li How many possible outcomes are there where the coin lands on heads
+and tails an equal number of times?
+
+$${10\choose 5} = 252.$$
+
+}
+
+\li How many solutions are there to the following equations? Simplify
+your answer to an integer.
+
+{\startlist
+
+\li $a_1 + a_2 + a_3 + a_4 = 100$
+
+where $a_1,$ $a_2,$ $a_3,$ and $a_4$ are positive integers?
+
+We can compute this using stars and bars, giving 99 spots and 3 bars or
+$${99\choose 3} = 156,\!849$$
+solutions to the equation.
+
+\li $a_1 + a_2 + a_3 + a_4 + a_5 = 100$
+
+where $a_1,$ $a_2,$ $a_3,$ $a_4,$ and $a_5$ are non-negative integers,
+and $a_1 > 5.$
+
+First we subtract 5 from both sides and then add 4 to both sides to
+change the bounds on all of our numbers to $a_k > 0.$
+We would then have $\sum = 101.$
+Using stars and bars, we will obtain
+$${100\choose 4} = 3,\!921,\!225$$
+solutions to this equation.
+
+\li $a_1 + a_2 + a_3 = 100$
+
+where $a_1,$ $a_2,$ and $a_3$ are non-negative integers, and $a_3\leq
+10.$
+
+Computing ignoring the restriction, we get ${102\choose 2}$ solutions.
+Then we consider the ones that violate the restriction ($a_3\geq11$) as
+${91\choose 2}$ solutions.
+The number of solutions following the restriction is
+$${102\choose 2} - {91\choose 2} = 1056.$$
+
+}
+
+\li How many different strings can be created by rearranging the letters
+in ``addressee''? Simplify your answer to an integer.
+
+There are
+$${9\choose 1,2,3,2,1} = 15,\!120$$
+strings (random permutation of 9 characters and then discount the
+positioning of the 2 d's, the 3 e's, and the 2 s's)
+
+\li Let a class consist of 8 CS major students and 8 CM major students.
+Each student is either a CS major or a CM major, but not both. How many
+distinct ways are there to arrange the students in a line such that no
+student stands next to someone in the same major as themselves? Simplify
+your answer to an integer.
+
+There are two ways to do this (assuming indistinct students), either
+starting with a CS or CM major.
+Then the internal order of each major is $8!,$ giving us, for distinct
+students,
+$$2\cdot 8! \cdot 8! = 3,\!251,\!404,\!800$$
+ways to arrange them.
+
+\li Three pairs of twins are sharing a bucket of 24 chicken wings from
+Olive Oyl's. Through the magic of twinship, each person always eats
+exactly as many chicken wings as their twin. If each person eats at
+least one chicken wing, how many ways can the chicken wings be
+distributed amongst the people? For the purposes of this problem,
+chicken wings are indistinguishable, and every chicken wing is eaten.
+Simplify your answer to an integer.
+
+This is equivalent to three people sharing a bucket of 12 chicken wings.
+Using stars and bars, we get
+$${11\choose 2} = 55$$
+ways to eat the chicken wings.
+
+\li CS 2050 has 10 recitation sections. 7 of the recitation sections are
+led by a pair of TAs, and 3 recitation sections are led by a trio of
+TAs. How many ways are there to line up the TAs such that each TA is
+standing next to their recitation partner(s)? Simplify your answer to an
+integer.
+
+First, we consider how many ways we can arrange the recitation sections
+($10!$).
+Then we determine how many ways each recitation can be internally
+arranged in the line ($(3!)^3\cdot(2!)^7$)
+This computes to
+$$10!\cdot(3!)^3\cdot(2!)^7 = 100,\!329,\!062,\!400$$
+ways to arrange the TAs.
+
+\bye