MAT 135 Homework 1

# MAT 135 Homework 1 *This paper is written using latex in the [Hackmd](#) Platform.* **I acknowledge that the entire work is mine and did not copy and paste from other courses**. ## **Problem 1.** In a classroom there are 20 cats and 20 people. Each person has one cat as a pet. - **(1)** If people are told to be paired with a cat at random, what is the probability that each person will be paired with their cat? Pairing any one person and one cat from each group produces 20 possible collection of the pairs, giving us $20!$ possible pairing collections. Of those, there is only one collection that is specifically arranged in a way that each pair has $(owner, pet)$ for all pets in that collection. Thus the good outcome is 1. Given this information, the probability that each person will be pair with their cat for all people in our group is $$ \frac{1}{20!} $$ - **(2)** We now pick 10 of the 20 cats at random, and 10 people out of the 20 at random, and then pair them at random, what is the probability that Didac (one of the persons) will be paired with his cat (Roo). We first define the number of arrangements we have when choosing 10 people from $P, \text{ group of people }$, and choosing 10 cats from $C, \text {group of cats}$. This gives us the collection of possible arrangements for choosing any 10 people from $P$ and 10 cats from $C$, where the length (cardinality) of this collection is defined as ${20 \choose 10}^{2}$. Once we have that, now there are $10!$ ways to arrange all the collections we sampled by randomly choosing 10 from each set $P$ and $C$. Thus, we have ${20 \choose 10}^{2}*10!$ ways of arrangement for the total outcome. Given this information, we can now assume that one specific person, say *Didac*, is chosen **AND** paired up with his cat, *Roo*. This also means that the cat *Roo* is also sampled and paired out with *Didac*. Thus, for the group $P$ we popped out *Didac* and $C$ we popped out *Roo*. Now the new $P_{new}$ has cardinality of 19 which is also the case for $C_{new}$. But we still need to arrange the remaining 9 selections and pairings from $P_{new}$ and $C_{new}$. Thus, this gives us ${19 \choose 9}^{2}$ ways to select 9 people and 9 cats from each group. Once we have the selection group we will have $9!$ possible ways to arrange the chosen group to pair. This gives us the good outcome of ${19 \choose 9}^{2}*9!$ Therefore, $$ P(E = \text{(Didac, Roo)} \in Sample) = \frac{{19 \choose 9}^{2}*9!}{{20 \choose 10}^{2} * 10!} $$ ## **Problem 2.** In a 8 by 6 grid (8 squares horizontally by 6 squares vertically), squares are labelled starting at the lower bottom corner with (0, 0), and increasing in the first coordinate as we move up, and in the second coordinate as we move to the right. For example, right above (0, 0) we have (0, 1), and to the right of (0, 0) we have (1, 0). Suppose that we start moving from (0, 0), and that, at each move, we can move either up or to the right. - **(1)** How many paths are there (sequences of up and right moves), that start at (0, 0) and terminate at (7, 5)? Our goal is to get to $(7, 5)$ from $(0, 0)$, **given** that we can only move up $(i, j) \rightarrow (i+1, j)$ or move right $(i, j) \rightarrow (i, j+ 1)$ per movement. Also, note that since we can only move up or right once per movement, it is linearly expanding our path from the previous path to the next path, which means that the total movement steps are fixed to $7 + 5 = 12$ steps regardless of the path we take. **More interestingly**, it is also fixed *how many up step* and *how many right step* we take. In our case, we will take $7$ right steps $5$ up steps while getting to $(7, 5)$, *again regardless of the path we take*. Given this information, it is clear that **we must track** either *7 right steps* or *5 up steps* we take, **BUT** not both since tracking one authomatically infers the other. Therefore we will choose to track **5 up steps** out of the total **12 steps** and compute all possible ways of taking 5 up steps. This should give us the number of ways to get to $(7, 5)$ from $(0,0)$ $$ {12 \choose 5} = \frac{12!}{5!*7!} = 792 $$ - **(2)** What is the probability that one of those paths goes through (2, 3)? If we had to expand our path towards $(7, 5)$ with a fixed point $(n, k) \text{ where } n \leq 7 \text{ and } m \leq 5$ in a map, this means that we can partition the entire map into two sub-maps in the following way $$ M1(n, k): (0, 0) \rightarrow (n, k) \\ M2(n, k): (n, k) \rightarrow (7, 5) $$ From partitioning, we can further note that the possible ways to get to the destination $(7, 5)$ from $(0, 0)$ that goes through the intersection of $Int(M1,M2) = (n, k)$ is $$ Ways = |Paths[M1(n, k)]| * |Paths[M2(n, k)] $$ where $Path[T_i \rightarrow T_f]$ represents the collection of all paths from the point $T_i$ to $T_f$. Since we know how to get the collection of paths from one point to the other, *as shown in (1)*, we can proceed with finding the cardinality (number) of all paths from $(0, 0)$ to $(2, 3)$ and the cardinality of all paths from $(2, 3)$ to $(7, 5)$. That will give all the possible combinations of paths to get the $(7, 5)$ from $(0, 0)$ through $(2, 3)$. $$ Paths[M1(2, 3)] = {5 \choose 2} = \frac{5!}{2!*3!} = 10 \\ Paths[M2(2, 3)] = {(12 - 5) \choose (5 - 2)} = {7 \choose 3} = \frac{7!}{3! * 4!} = 70 $$ This gives the number of ways as $$ Ways = 10 * 70 = 700 $$ ## **Problem 3.** Given 10 people, how many possible selections are there of - **(1)** A committee of size 5 and a chairperson for that committee? Since we have to **choose** any 5 from 10, we have ${10 \choose 5}$ ways to select a committee size of 5. On top of this, for each selection possibility, we have 5 ways to choose a chairperson. Thus we have the toal number of selections to chosoe a commitee size of 5 with a chairperson as $$ {10 \choose 5} * 5 $$ - **(2)** A committee of any size and a chair person for the committee? Because we have to account for all possible sizes, we can partition the selection group by each size such that $$ |Selection_{size=i}| = {10 \choose i} * i $$ Also, we want to get all possible selections which means we want to sum all selections with all possible sizes. $$ |Selection_{size=1}| + |Selection_{size=2}| + ... + |Selection_{size=10}| \\ = \sum_{i = 1}^{10}{|Selection_{size=i}|} \\ = \sum_{i = 1}^{10}{10 \choose i}*i $$ ## **Problem 4.** How many 3 digit numbers (in base 10) have? - **(1)** at least 2 of their digits equal. To get **at least 2 of 3 digits equal** is equivalent to saying $C_2 =$ **exactly two digits equal** $+$ $C_3 =$ **all 3 digits equal**. For $C_2$, we have the number of way to have exactly two digits equal as the unions of. $$ C_2 = C_{2_{1, 1}} \cup C_{2_{1, 3}} \cup C_{2_{2, 3}} \text { where x,y represents the index of the number to be equal.} $$ For $C_{2_{1, 2}}$, we have the first digit equal to the last digit, *XXx* $$ |C_{2_{1, 2}}| = 9*9 $$ For $C_{2_{1, 3}}$, we have the first digit equal to the last digit, *XxX* $$ |C_{2_{1, 3}}| = 9*9 $$ For $C_{2_{2, 3}}$, we have the first digit equal to the last digit, *xXX* $$ |C_{2_{2, 3}}| = 9*9 $$ For $C_3$, there is exctly $9$ ways that all three digits are equal, $\{111, 222, ..., 999\}$ Adding $|C_2|$ and $|C_3|$, we get the total number of ways to have at least 2 of 3 digits equal. $$ 3*9^2 + 9 = 243 + 9 = 252 $$ - **(2)** How many have exactly 2 equal digits? From **part (1)**, we already obtained the number of ways that **two digits equal** noted as $|C_2|$ $$ 243 $$ ## **Problem 5.** A large company with $n$ employees has a scheme according to which each employee buys a Christmas gift and the gifts are then distributeed at random to the employees. What is the probability that at least one of the employees gets their own gift? To proceed with computing the answer, we should note that the statement **at least one of the employees get their own present** is equivalent to **all possible ways to fairly distribute gifts - no employees get their own present**. Since we have $n$ employees who will each buy a present to distribute $n$ presents, this means that **everyone** will get a present if distributed fairly (one per person). Thus it is **always the case** that every employee will receive one present. Therefore, $$P(E = \text{ everyone gets a present}) = 1 \text{ with } n! \text { ways to distribute the presents}$$ Now, we need to find $P(E = \text{ no employee gets their own present})$ from the total probability $1$. For all the possible distribution ways $n!$, there can only be **one** way where each present that each employee receives **IS NOT** their own present. Therefore $$ P(E = \text {no employee gets their own present }) = \frac{1}{n!} $$ This means, we have the probability of the case where at least one employee receieves their own present is computed as, $$ P(E) = 1 - \frac{1}{n!} = \frac{n! - 1}{n!} $$