From 8dafd8aec819e85fd36cbd1d6231aad24e62c31b Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Tue, 16 Aug 2022 18:21:57 -0400 Subject: Finished work from last semester --- howard/hw11.tex | 236 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 236 insertions(+) create mode 100644 howard/hw11.tex (limited to 'howard/hw11.tex') 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 -- cgit