sudo # COT 3100 - Homework 5 *Michael Akinyemi* *Tue/Thu 9:00 AM* > Notes: > - Can provide large answers in factorial/choice notations ## Problem 1: Counting Small Monster Collections (25) *A Small Monster collector is visiting the Knightrola region, bringing 30 Small Monster Containment Devices with them. The devices are highly reliable and can effectively be assumed to always work.  How many different combinations of types of Small Monsters can the collector capture under the following conditions?* > Notes: > - Combinations problem > - Repetition/”with replacement” is allowed > - # of combinations should decrease as more restrictions are introduced > - D & E likely involve finding the complement and subtracting it out > - how will we ensure that there isn’t any overlap between the complements of parts D & E so that we don’t subtract multiple times? (add back something) *A. (5) The collector has access to **Grass, Space, Electric Scooter, Mask, Citrus, and Rubber Duck** type Small Monsters (**6 Options**)* ${30+6-1 \choose 30} = {35 \choose 30} = 324,632$ *B. (5) The above, and intends to capture **at least** one of each of those types* 5 catches must be set in stone and can be subtracted from value of $n$: ${24+6-1 \choose 24} = {29 \choose 24}=118,755$ *C. (5) Both of the above, and intends to capture **at least** five Space types* One space type is already guaranteed from part B, so only 4 catches need to be removed: ${20+6-1 \choose 20} = {25 \choose 20}=53,130$ *D. (5) All of the above, and intends to capture **at most** four Electric Scooter types* Subtract out combinations where more than four ES types are captured: ${25\choose 20}-{21\choose16}=32,781$ *E. (5) All of the above, and intends to capture **at most** three Rubber Duck types* Subtract out combinations where more than three RD types are captured but add back combinations where criteria of parts D & E are met simultaneously to avoid double-subtraction: ${25 \choose 20}-{21 \choose 16}-{22 \choose 17}+{18 \choose 13}=15,015$ ## Problem 2: Counting Small Monster Taxonomies (20) *A. (5) Taking into account identical letters, how many ways can the researcher arrange the word CALLITRICHIDAE?* > Notes: > - Permutation problem > - For part B, I’m struggling to think of how we’d account for one of the vowels with repetition being used - 14 letters total - 4 cases of repetition - C, L, A (2) - I (3) $\frac{14!}{2!2!3!2!}=1,816,214,400$ --- *B. (10) Taking into account identical letters, how many ways can the researcher arrange the word CALLITRICHIDAE that start or end with vowels?* ` V __ __ __ __ __ __ __ __ __ __ __ __ V` ` 1 2 3 4 5 6 7 8 9 10 11 12 13 14` Vowels: A I I I A E (6 Total) Consonants: C L L T R C H D (8 Total) > Notes: > - In terms of the combinations it shouldn’t matter whether the vowel is at the start/end position > - Should be a smaller # than part A > - We have several different components: > - Possibe permutations for start/end vowel positions (picking from set of vowels) > - Possible permutations for central letters (picking from set of consonants + leftover vowels) > - The difficult part is handling certain vowels being picked which impacts the number of duplicate elements within the set of leftovers (just going to brute force it with multiple cases) > - Numerator always remains the same, only factor changing is how many duplicate elements there are **Start Vowels:** A + E + I $\frac{13!}{3!2!2!}+\frac{13!}{3!2!2!2!}+\frac{13!}{2!2!2!2!}=1,556,755,200$ **Start & End Vowels:** `A _ _ _ _ _ _ _ _ _ _ _ _ A` → $\frac{12!}{3!2!2!}=19,958,400$ `A _ _ _ _ _ _ _ _ _ _ _ _ E` → $\frac{12!}{3!2!2!}=19,958,400$ `A _ _ _ _ _ _ _ _ _ _ _ _ I` → $\frac{12!}{2!2!2!}=59,875,200$ `E _ _ _ _ _ _ _ _ _ _ _ _ A` → $\frac{12!}{3!2!2!}=19,958,400$ `E _ _ _ _ _ _ _ _ _ _ _ _ I` → $\frac{12!}{2!2!2!2!}=29,937,600$ `I _ _ _ _ _ _ _ _ _ _ _ _ A` → $\frac{12!}{2!2!2!}==59,875,200$ `I _ _ _ _ _ _ _ _ _ _ _ _ E` → $\frac{12!}{2!2!2!2!}=29,937,600$ `I _ _ _ _ _ _ _ _ _ _ _ _ I` → $\frac{12!}{2!2!2!}==59,875,200$ $1,556,755,200 - 3(19,958,400) - 2(29,937,600) - 3(59,875,200)=$ $1,257,379,200$ --- *C. (5) Taking into account identical letters, how many ways can the researcher arrange the word CALLITRICHIDAE that contain the substring LITERAL?* > Notes: > - The string “literal” must exist somewhere in the sequence and can begin anywhere between the 1st spot and the 8th spot (after that it would be cut off) > - Just realized 8 * 7! is just 8! and that it can be treated as its own letter > - We then have to find what letters remained after we use some to create the word “literal": CICHIDA ` L I T E R A L __ __ __ __ __ __ __` ` 1 2 3 4 5 6 7 8 9 10 11 12 13 14` $\frac{8!}{2!2!} =10,080$ ## Problem 3: Counting Small Monster Tangents (10) *Taking into account identical letters, how many ways are there to arrange the letters in the word ANTIDISESTABLISHMENTARIANISM?* - A A A A (4) - N N N (3) - T T T (3) - I I I I I (5) - D (1) - S S S S (4) - E E (2) - B (1) - L (1) - H (1) - M M (2) - R (1) $n=28$ $\frac{28!}{4!3!3!5!4!2!2!} = 3.063e22$ ## Problem 4: Counting in Small Monster Politics (15) *The Greater Knightrola Small Monster Association has four chartered positions: President, Vice President, Treasurer and Secretary; it also has 12 officers chosen at large. All of these seats must be filled by members of GKSMA, of which there are 50. No member may hold more than 1 position.* *How many different ways are there to fill the positions?* $(50)(49)(48)(47){46 \choose 12}=5527200 \cdot \frac{46!}{12!(46-12)!}=2.15e17$ ## Problem 5: Counting in Small Monster Sports (10) *A small monster athletic tournament has n teams, ranked 1 to n.* - *In the first match, the nth ranked team plays the (n-1)th ranked team. The loser of that match finishes in last place.* - *The winner of the first match plays the (n-2)th ranked team. The loser of that match finishes in second to last place.* - *The winner of the second match goes on to play the (n-3)th ranked team, and so on.* - *The last match will pit the previous match winner against the first-ranked team. The winner of this last match wins the tournament, and the loser of this last match places second in the tournament.* *In how many different orders can the n teams finish?* > Notes: > - related to space/time complexity of algorithm analysis > - how does output change as the input (n) grows ## Problem 6: Counting Something That Isn't Small Monsters (20) *While the Small Monster collector, researcher, ecclesiastical historian and tournament spectator was busy with marmosets, we showed in class that we can an assign an integer order to the members of an infinite two-dimensional array; and thus, that infinite two-dimensional arrays are countable, and can be re-ordered as infinite one-dimensional arrays.  Using that result, prove by induction that for any positive integer n, an infinite n-dimensional array is countable.* > Notes: > - The base case was done in class, we can just reference that > - The inductive hypothesis is hinted at within the question > - If more than a paragraph you are doing too much > - Apply the inductive principle abstractly, rather than to an equation (achieve domino effect) **Base Case:** **Inductive Hypothesis:** Accept that **Induction:** ## Problem 7: Rolling the Dice (50) *A. (10) Rolling two four-sided dice, what’s the likelihood of getting the same sum twice in a row?* > Notes: > - Definitely didn’t misread as “same roll” twice in a row… > - Still similar method of squaring probability, just for sums now rather than individual rolls > - Need to use addition rule (“either A or B”) to link together probabilities of different sums | Sum | Probability | | ---- | ---- | | 2 | 1/16 | | 3 | 1/8 | | 4 | 3/16 | | 5 | 1/4 | | 6 | 3/16 | | 7 | 1/8 | | 8 | 1/16 | $2(\frac{1}{16})^2 + 2(\frac{1}{8})^2 + 2(\frac{3}{16})^2 + (\frac{1}{4})^2 =$ $\frac{2}{256} + \frac{2}{64} + \frac{18}{256} + \frac{1}{16} =$ $\frac{2}{256} + \frac{8}{256} + \frac{18}{256} + \frac{16}{256} =\frac{44}{256}=\frac{11}{64}$ *B. (15) Rolling three four-sided dice, what is the probability of totaling at least 9?* > Notes: > - Order doesn’t matter for combinations > - Total # of possibilities is $4^3$ > - Can tackle by first separating into cases | D2/D1 | 1 | 2 | 3 | 4 | | ---- | ---- | ---- | ---- | ---- | | 1 | 2 | 3 | 4 | *5* | | 2 | 3 | 4 | *5* | *6* | | 3 | 4 | *5* | *6* | *7* | | 4 | *5* | *6* | *7* | *8* | Sum of first two dice must be >5 (occurs $\frac{10}{16}$ times), otherwise largest sum is ≤8 | D3/(D2+D1) | 5 | 6 | 7 | 8 | | ---- | ---- | ---- | ---- | ---- | | 1 | 6 | 7 | 8 | **9** | | 2 | 7 | 8 | **9** | **10** | | 3 | 8 | **9** | **10** | **11** | | 4 | **9** | **10** | **11** | **12** | $\frac{10}{32}=\frac{5}{16}=0.3125$ *C. (15) Rolling three four-sided dice twice, what is the probability of the second total being larger than the first?* Three possible cases: - First Roll > Second Sum - First Roll < Second Sum - First Roll = Second Sum *D. (10) Two six-sided dice are rolled – one fair one, and unfair one. For the unfair die, the probability of landing on the side with k dots is (k/21). What is the probability of rolling a sum of 9?* ## Problem 8: Birthday Ice Cream (20) *The Tauroto region contains 31 different species of IceCream-type small monsters. Each capture of an IceCream-type small monster has an equal chance of being any of the 31 species.* *A. (10) If a collector captures five of these small monsters, what is the probability that they have captured at least two small monsters of the same species?* > Notes: > - Can solve by calculating the probability of all 5 catches being unique and subtracting from 1 $1-\frac{(31)(30)(29)(28)(27)}{31^5}=1-0.712=0.288$ $28.8\%$ --- *B. (10) What is the lowest number of IceCream-type small monsters that a collector must capture to make capturing at least two of the same species more likely than not?* $1-\frac{(31)(30)(29)(28)(27)(26)(25)}{31^7}=1-0.482=0.518$ The collector must capture **at least 7** small monsters to have a >50% chance of capturing at least two of the same species ## Problem 9: Expecting to Lose (15) *The Knightrola Lottery has been updated to allow choosing 6 numbers out of 63 on a $1 ticket.* - *Choosing 3 numbers correctly gives a $10 prize.* - *Choosing 4 numbers correctly gives a $50 prize.* - *Choosing 5 numbers correctly gives a $5,000 prize.* *If the Lottery expects to **precisely break even**, how much is its prize for getting all 6 numbers correct?* > Notes: > - We can calculate the probability of each prize tier and multiply it by the $ amount to determine the total amount that could be won through the lottery > - The full prize pool must be the sum of all rewards, we already know this is the same as the sample space (${63 \choose 6} = 67,945,521$) since each ticket only costs $1 > - Subtracting the rewards of the lower prizes from the total pull would leave the grand prize amount for getting all 6 numbers correct (never knew thats how lotteries worked) $[10{6 \choose 3}{57 \choose 3}]+[50{6 \choose 4}{57 \choose 2}]+[5000{6 \choose 5}{57 \choose 1}]+X ={63 \choose 6}$ $5,852,000+1,197,000+1,710,000+X=67,945,521$ $X=\$ 59,186,521$ ## Problem 10: Figuring Out the Method (15) *A. (5) A box contains 5 apples and 6 oranges. Four children each receive a fruit from the box, one after the other, randomly chosen, without replacement. What is the probability that all four children receive the same fruit?* If apples: $\frac{5}{11}\cdot\frac{4}{10}\cdot\frac{3}{9}\cdot\frac{2}{8}=\frac{1}{66}$ If oranges: $\frac{6}{11}\cdot\frac{5}{10}\cdot\frac{4}{9}\cdot\frac{3}{8}=\frac{3}{66}$ Probability that all four receive same fruit: $\frac{1}{66} + \frac{3}{66} = \frac{4}{66}=0.0606$ $6.06\%$ *B. (10) An **unfair** coin, when tossed 7 times, has the same probability of obtaining 2 heads out of 7 as it does of obtaining 3 heads out of the 7 tosses. What is the probability the coin lands heads on a single toss?* > Notes: > - Uses binomial probability formula? > - $n=7$ & $r=3,2$ ${7\choose 3}P^3(1-P)^4={7\choose2}P^2(1-P)^5$ $\frac{7}{3!4!}\cdot P^3(1-P)^4=\frac{7!}{2!5!}P^2(1-P)^5$ $\frac{7!}{3!4!}\cdot P=\frac{7!}{2!5!}(1-P)$ $\frac{7!}{3!4!}\cdot \frac{2!5!}{7!}(P)=1-P$ $\frac{5}{3}\cdot P + P=1$ $P(\frac{5}{3} +1)=1$ $P=\frac{3}{8}=0.375$ $37.5\%$