COMP 2711 HW 2

1

a

Countably infinite

$A=\{1,2\}$
$B=\{3,4\}$
$\mathbb{N}=\{0,1,2,\dots \}$

$A\times B=\left\{\left\{1,3\right\}\left\{1,4\right\},\left\{2,3\right\},\left\{2,4\right\}\right\}$

Label them as $E_1,E_2,E_3,E_4$

$A\times B\times \mathbb{N}=\left\{\left\{0,1,3\right\},\left\{0,1,4\right\},\left\{0,2,3\right\},\left\{0,2,4\right\},\left\{1,1,3\right\},\dots \right\}$

Which can be labelled as $E_{11},E_{12},E_{13},E_{14},E_{21},\dots$

A one-to-one correspondence to ${\mathbb{Z}}^{+}$ can be produced as follows

$$\begin{array}{rlrlrlrlrlrl}& E_{11}& & E_{12}& & E_{13}& & E_{14}& & E_{21}& & \dots \\ & 1& & 2& & 3& & 4& & 5& & \dots \end{array}$$

b

Countably infinite

A one-to-one correspondence to ${\mathbb{Z}}^{+}$ can be produced by mapping n-lengthed bit string to n

$$\begin{array}{rlrlrlrlrlrl}& 0& & 00& & 000& & 0000& & 00000& & \dots \\ & 1& & 2& & 3& & 4& & 5& & \dots \end{array}$$

c

Countably infinite

A one-to-one correspondence to ${\mathbb{Z}}^{+}$can be produced by mapping the binary representation of the bit string + 1 to ${\mathbb{Z}}^{+}$

$$\begin{array}{rlrlrlrlrlrl}& 0& & 1& & 01& & 10& & 11& & \dots \\ & 1& & 2& & 3& & 4& & 5& & \dots \end{array}$$

d

Uncountable

A new bit string can always be created by taking the diagonal of the existing bit strings and applying the below formula

$$\begin{array}{rl}& \text{Bit string 1}=e_{11}{e}_{12}{e}_{13}\dots \\ & \text{Bit string 2}=e_{21}{e}_{22}{e}_{23}\dots \\ & \text{Bit string 3}=e_{31}{e}_{32}{e}_{33}\dots \\ & ⋮\end{array}$$ $$\text{New bit string}=e_{11}{e}_{22}{e}_{33}\dots$$ $$\{\begin{array}{l}1\text{if eii is 0}\\ 0\text{if eii is 1}\end{array}$$

e

Uncountable

Even if the number of 1s is finite, the number of (0, 2, 3, …, 9) is still be infinite

Let $r_{ij}$ be the decimal digit of a real number

$$\begin{array}{rl}& r_{11}{r}_{12}{r}_{13}\dots \\ & r_{21}{r}_{22}{r}_{23}\dots \\ & r_{31}{r}_{32}{r}_{33}\dots \end{array}$$

We could always construct a new real number with the diagonal by applying the blow formula

$$\{\begin{array}{l}5\text{if }{r}_{ii}\ne 5\\ 6\text{if }{r}_{ii}=5\end{array}$$

f

Countably infinite

The follows are all real numbers containing only 1s in their decimal representation

$$\begin{array}{rlrlrlrl}& 1& & 1.1& & 1.11& & \dots \\ & 11& & 11.1& & 11.11& & \dots \\ & 111& & 111.1& & 111.11& & \dots \\ & ⋮& & & & & & \end{array}$$

Take the number of 1s before the decimal point and after the decimal point and order them as an tuple

$$\begin{array}{rlrlrlrl}& (1,0)& & (1,1)& & (1,2)& & \dots \\ & (2,0)& & (2,1)& & (2,2)& & \dots \\ & (3,0)& & (3,1)& & (3,2)& & \dots \\ & ⋮& & & & & & \end{array}$$

Then a one-to-one correspondence to ${\mathbb{Z}}^{+}$can be produced as follows

$$\begin{array}{rlrlrlrlrlrl}& (1,0)& & (1,1)& & \dots & & (2,0)& & (2,1)& & \dots \\ & 1& & 2& & \dots & & k& & k+1& & \dots \end{array}$$

g

Uncountable

Suppose each disk has a center coordinate of $(x,y)$ and radii $r$

Since the center could be any real number pairs on a plane, and the set of real numbers is uncountable, there should be infinitely many disks

2

a

The worst case is that all the balls representing the other lakes are picked first, then we have to pick $6\times 4+3=27$ balls to ensure there are at least 3 balls representing Lake Motosu

b

The worst case is that only 2 balls with the same color for each lake is picked first

$$5\times 2+1=11$$

c

1. Pick sauce $C$ for Nadeshiko (6 choices)
   1. Rin have $6\times 2=12$ choices
   2. Aoi have $6\times 2=12$ choices
   3. Chiaki have $6\times 4=24$ choices
2. Pick sauce $C$ for Chiaki (6 choices)
   1. Rin have $6\times 2=12$ choices
   2. Aoi have $6\times 2=12$ choices
   3. Nadeshiko have $6\times 4=24$ choices (cannot choose $C$ since the case is covered above)

By sum rule, the answer is

$$(6\times 12\times 12\times 24)+(6\times 12\times 12\times 24)=41472$$

d

The sequence is as follows for 23 layers

top → meat → cheese → (meat/tomato → cheese) x 8 → tomato → top

Since we have 2 choices at cheese, the answer is

$$2^8=256$$

e

The number of non-negative integer solutions for

$$x_1+x_2+x_3<50$$

is the same as the number of non-negative integer solutions for

$$x_1+x_2+x_3+c=49$$

Hence, 49 stars, $4-1=3$ bars

$$\left(\genfrac{}{}{0ex}{}{49+3}{3}\right)=\left(\genfrac{}{}{0ex}{}{52}{3}\right)=22100$$

f

If $x_2$ and $x_3$ are only even numbers, we have 27 stars and 3 bars

$$\begin{array}{rl}2x_1+2x_2^{\prime }+2x_3^{\prime }+2x_4& =54\\ x_1+x_2^{\prime }+x_3^{\prime }+x_4& =27\end{array}$$

If $x_2$ and $x_3$ are only odd numbers, we have 26 stars and 3 bars

$$\begin{array}{rl}2x_1+(2x_2^{\prime }+1)+(2x_3^{\prime }+1)+2x_4& =54\\ x_1+x_2^{\prime }+x_3^{\prime }+x_4& =26\end{array}$$

By sum rule,

$$\left(\genfrac{}{}{0ex}{}{27+3}{3}\right)+\left(\genfrac{}{}{0ex}{}{26+3}{3}\right)=7714$$

g

Let $S(x)$ be the number of ways to reach position $n$ from position $x$

$$S(x)=1+S(x+1)+S(x+2)+\cdots +S(n-1)$$

The formula is created considering we can directly jump to position $n$ for 1 step, or jump to any position in the range of $[x+1,n-1]$

Considering the base case

$$\begin{array}{rl}& S(n-1)=1\\ & S(n-2)=1+1=2\\ & S(n-3)=1+2+1=4\\ & S(n-4)=1+4+2+1=8\\ & ⋮\\ & S(n-k)=2^{k-1}\end{array}$$

Considering $S(1)$

$$\begin{array}{rl}n-k& =1\\ k& =n-1\\ & \\ S(1)& =S(n-(n-1))=2^{(n-1)-1}=2^{n-2}\end{array}$$

Therefore, the number of ways to reach position $n$ from position 1 is $S(1)=2^{n-2}$

3

a

For students in L3, let $A$ be students who take COMP2011, $B$ be students who take MATH1012, $C$ be students who take COMP1021

$$\begin{array}{rl}|A\cup B\cup C|& =|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\\ 95-25& =37+42+31-25-0-|B\cap C|+0\\ |B\cap C|& =15\end{array}$$

b

$$\left(\genfrac{}{}{0ex}{}{82}{4}\right)\left(\genfrac{}{}{0ex}{}{93}{7}\right)\left(\genfrac{}{}{0ex}{}{95}{6}\right)$$

c

1. Choose 1 student from each lecture section
2. Choose the remaining $100-3$ students

$$\left(\genfrac{}{}{0ex}{}{83}{1}\right)\left(\genfrac{}{}{0ex}{}{93}{1}\right)\left(\genfrac{}{}{0ex}{}{95}{1}\right)\left(\genfrac{}{}{0ex}{}{83+93+95-3}{100-3}\right)$$

d

1. Choose 3 for their original task
2. Dearrange the remaining

$$\left(\genfrac{}{}{0ex}{}{8}{3}\right)D_{8-3}=\left(\genfrac{}{}{0ex}{}{8}{3}\right)D_5$$

4

a

The LHS can be interpreted as follows:

1. Choose $r$ elements from $n$ items
2. Choose $a$ elements from $r$ items

The RHS can be interpreted as follows:

1. Choose $a$ elements from $n$ items
2. From the complement of $a$ in $n$, i.e. $n-a$, choose from the complement of $a$ in $r$, i.e. $r-a$
3. By the product rule, this would be identical to the LHS

b

$$\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$$ $$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{n}{r}\right)\left(\genfrac{}{}{0ex}{}{r}{a}\right)& =\frac{n!}{r!(n-r)!}\frac{r!}{a!(r-a)!}\\ & =\frac{n!}{a!(n-r)!(r-a)!}\\ & =\frac{n!}{a!(n-r)!(r-a)!}\frac{(n-a)!}{(n-a)!}\\ & =\frac{n!}{a!(n-a)!}\frac{(n-a)!}{(n-r)!(r-a)!}\\ & =\frac{n!}{a!(n-a)!}\frac{(n-a)!}{(n-r-a+a)!(r-a)!}\\ & =\frac{n!}{a!(n-a)!}\frac{(n-a)!}{(n-a-(r-a))!(r-a)!}\\ & =\left(\genfrac{}{}{0ex}{}{n}{a}\right)\left(\genfrac{}{}{0ex}{}{n-a}{r-a}\right)\end{array}$$

5

a

$$\sum _{i=1}^n{i}^2=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+2\cdot \left(\genfrac{}{}{0ex}{}{n+1}{3}\right)$$

Consider we are choosing an ordered-triplets $(a,b,c)$ such that $0\le a\le n$, $0\le b<c$ and $0\le c\le n$

The LHS can be interpreted as follows

1. For each value of $i$ in the range of $[1,n]$, choose $a,b$ in the range of $[0,i-1]$

The RHS can be interpreted as follows

1. For the case if $a$ and $b$ are equal, we only need to choose 2 numbers in the range $[0,n]$ since $a=b$
2. For the case if $a$ and $b$ are different, we choose $a,b,c$ in the range of $[0,n]$, and there are 2 ways for doing so, i.e. $a<b$ and $a>b$
3. Summing these 2 terms would be identical to the LHS

b

$$\sum _{k=1}^n{k}^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\cdot (n-1)\cdot 2^{n-2}+n\cdot 2^{n-1}$$

The LHS can be interpreted as follows

1. $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ means choose $k$ element from a set of $n$ element
2. $k^2$ means choose 2 elements from $k$ choices (repetition allowed)
3. The summation of these 2 terms is the total number of combinations for $k$ in the range of $[1,n]$

The RHS can be interpreted as follows

1. $n\cdot (n-1)\cdot 2^{n-2}$ means choose 1 element from $n$ choices, then choose another element from $n-1$ choices, then the number of ways to group the remaining element would be $2^{n-2}$, this is the case when the 2 element chosen is different
2. $n\cdot 2^{n-1}$ means choose 1 element from $n$ choices, then group it with the remaining possible $2^{n-1}$ combinations, this is the case when the 2 elements chosen are the same
3. Summing these two terms would produce the same result as the LHS, therefore they are identical

6

1. All combinations of putting on socks and shoes, i.e. $16!$
2. For each leg, half of the combinations would be wrong, so divide by $2^8$ in total

$$\frac{16!}{2^8}$$