Good luck on the final!

Here are the review problems from Thursday’s class. Very brief hints/answers/solution sketches are below the cut:

1. $\exists p_3~ \big[ M(p_1,p_3) \wedge \big( M(p_3,p_2) \vee F(p_3,p_2) \big) \big]$
2. Make a truth table to show that $((p\to r)\wedge(q\to r)\wedge(p\vee q))\to r$ is a tautology. This rule of inference is the basis for proof by cases.
3. See “Why Mathematical Induction is Valid”, p. 314 in the book.
4. \begin{align*} |{\mathcal P}(A)\cup {\mathcal P}(B)| &= |{\mathcal P}(A)|+|{\mathcal P}(B)|-|{\mathcal P}(A)\cap{\mathcal P}(B)| \\ &= |{\mathcal P}(A)|+|{\mathcal P}(B)|-|{\mathcal P}(A\cap B)| \\ &= 2^5+2^4-2^2 \\ &=44 \end{align*}
5. $f$ is not an injection (ex: $f(1,0)=f(0,1)$). But $f$ is a surjection, because for all real $z$ we have $f(z,0)=z$.
6. For example, the set of integers has the same cardinality as the set of even integers (there is a bijection mapping $n$ to $2n$).
7. Let $S=\{a_1,a_2,a_3,\ldots\}$. Then we can arrange all the finite subsets of $S$ into sequential order: $$\varnothing,\{a_1\},\{a_2\},\{a_1,a_2\},\{a_3\},\{a_1,a_3\},\{a_2,a_3\},\{a_1,a_2,a_3\},\{a_4\},\ldots$$ (it is left to the reader to work out the details of this ordering). Because the elements of ${\mathcal P}^*(S)$ can be arranged as a sequence, ${\mathcal P}^*(S)$ is countable.
8. Refer to Theorem 5 on p. 242 of the book.
9. Refer to Lemma 1 on p. 268.
10. For example, $n=60$ works. Note that $143=11\cdot 13$. By FLT, $2^{10}\equiv 1\pmod{11}$ and $2^{12}\equiv 1\pmod{13}$. Thus $2^{10k}\equiv 1\pmod{11}$ and $2^{12\ell}\equiv 1\pmod{13}$ for all integers $k,\ell$. In particular, $2^{60}\equiv 1\pmod{11}$ and $2^{60}\equiv 1\pmod{13}$. By CRT, $2^{60}\equiv 1\pmod{143}$.
11. Refer to Example 2 on p. 336.
12. Check base cases $n=2,3$ and use strong induction.
13. (a) $k^n$, (b) $P(k,n)$, (c) $n(n-3)/2$ or $\binom n2-n$, (d) $\binom{m+n}m$
14. Eleven. Pigeonholes are the ten congruence classes modulo 10.
15. Seven. Pigeonholes are {0}, {1,9}, {2,8}, {3,7}, {4,6}, {5}, where an integer is placed in the pigeonhole corresponding to its units digit. Two integers in the same pigeonhole have either difference or sum divisible by 10.
16. Refer to Theorem 2 on p. 418.
17. (a) $\binom{6+4-1}{4-1}$, (b) $\binom{52}{5,5,5,5,32}$, (c) $\binom 7{3,2,1,1}-\binom 7{3,1,1,1}$, (d) $4\cdot 3!=24$ because there are 4 ways to place the E’s
18. Cody’s expected score is $(10)(0.8)=8$. Her probability of scoring exactly 8 is $\binom{10}8(0.8)^8(1-0.8)^2$. (See binomial distribution.)
19. Expected value: $np$, variance: $n(p-p^2)$
20. (a) $(0.6)(0.6)+(0.4)(0.2)=0.44$, (b) $\frac{(0.6)(0.6)}{(0.6)(0.6)+(0.4)(0.2)}=\frac 9{11}$ (Bayes FTW)
21. There are 12 positions where two 0′s can be adjacent. The probability of this occurring in each position is $\frac 12\cdot\frac 12$. By linearity of expectation, the expected number of occurrences is $12\cdot\frac 12\cdot\frac 12=3$.
22. Without the upper bound on $x_i$, there would be $\binom{10+4-1}{4-1}=\binom{13}3$ solutions. We want to exclude those for which one or more $x_i$ is greater than or equal to 5. For a given $i$, the number of solutions such that $x_i\ge 5$ is $\binom{5+4-1}{4-1}=\binom 83$. For given $i$ and $j$, the number of solutions such that $x_i\ge 5$ and $x_j\ge 5$ is $\binom 33=1$. Thus, by PIE, the number of solutions such that $x_i\le 4$ for every $i$ is $$\binom{13}3-\binom 41\binom 83+\binom 42\binom 33.$$
23. $(1+x+x^2+x^3+\cdots)(1+x^5+x^{10}+x^{15}+\cdots)(1+x^{10}+x^{20}+x^{30}+\cdots)$ or $\frac 1{(1-x)(1-x^5)(1-x^{10})}$
24. Each term in the expansion is of the form $x^{a_1}x^{a_2}\cdots x^{a_k}$, where $a_1,a_2,\ldots,a_k\in\mathbb N$. Thus we get one term of the form $x^n$ for each solution to the equation $a_1+a_2+\cdots+a_k=n$ (in natural numbers). The number of solutions, and thus the coefficient of $x^n$, is $\binom{n+k-1}{k-1}$ (see section 6.5 of the book).
25. $a_n = \frac 23(2^n)-\frac 13(-1)^n$
26. This problem and its solution were on one of Prof. Haiman’s tests (posted a few days ago).
27. We must show that every pair of distinct vertices is adjacent. Let $u,v$ be distinct vertices. Since $G$ is connected, there is a path $u\to v_1\to v_2\to \cdots\to v_{n-1}\to v_n$, where $v_n=v$. Assume WLOG that this is the shortest such path and assume, aiming for a contradiction, that $n\ge 2$. Since $u~R~v_1$ and $v_1~R~v_2$, we have $u~R~v_2$ by transitivity. Thus we can shorten our path by replacing the first two edges with $u\to v_2$. That contradicts our choice of the shortest path. Thus the shortest path cannot have length 2 or greater; it must have length 1, meaning $u$ and $v$ are adjacent. Since every pair of vertices is adjacent, $G=K_n$.
28. (a) $2^n$ vertices, $n\cdot 2^{n-1}$ edges. (b) $n!$ paths (we have to flip each bit once along a path, but we decide what order to flip them).
29. Done in class earlier this week; check your notes.
30. Note that $K_n$ has $\binom n2$ vertices, so $G,G’$ are each missing only one edge from $K_n$. Let the missing edge be $\{v_1,v_2\}$ in $G$ and let the missing edge be $\{v’_1,v’_2\}$ in $G’$. Then consider the bijection on vertices mapping $v_1$ to $v’_1$ and $v_2$ to $v’_2$ and mapping the remaining vertices however we want. This is an isomorphism.