path: root/howard/hw11.tex

\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