Discrete Mathematics

1. The objects being counted are people, which are distinct and separate entities.
2. The number of people must be an integer; you cannot have 2.5 people on a committee.
3. This is a counting problem involving combinations.

Answer: Discrete

1. The districts can be represented as vertices in a graph.
2. The bridges can be represented as edges connecting those vertices.
3. Finding the shortest path in a network of vertices and edges is a core problem of graph theory.

Answer: Graph Theory

1. Between any two real numbers, there is always another real number.
2. There are no 'gaps' or 'steps' in the set of real numbers.
3. This property defines a continuous interval.

Answer: Continuous

1. Step 1: List combinations of $p$ and $q$: $(T,T), (T,F), (F,T), (F,F)$.
2. Step 2: Evaluate $p \lor q$: $T, T, T, F$.
3. Step 3: Evaluate $p \land q$: $T, F, F, F$.
4. Step 4: Evaluate the implication $(p \lor q) \rightarrow (p \land q)$.
5. Row 1: $T \rightarrow T$ is $T$. Row 2: $T \rightarrow F$ is $F$. Row 3: $T \rightarrow F$ is $F$. Row 4: $F \rightarrow F$ is $T$.

Answer: The result is $T, F, F, T$, so it is a contingency.

1. Step 1: Evaluate $p \rightarrow q$: $T, F, T, T$.
2. Step 2: Negate the result $\neg(p \rightarrow q)$: $F, T, F, F$.
3. Step 3: Evaluate $\neg q$: $F, T, F, T$.
4. Step 4: Evaluate $p \land \neg q$: $T \land F = F$, $T \land T = T$, $F \land F = F$, $F \land T = F$.
5. Step 5: Compare the columns from Step 2 and Step 4.

Answer: Both columns are $F, T, F, F$, so they are logically equivalent.

1. Step 1: Evaluate $p \rightarrow q$: $T, F, T, T$.
2. Step 2: Evaluate $p \land (p \rightarrow q)$: $T \land T = T$, $T \land F = F$, $F \land T = F$, $F \land T = F$.
3. Step 3: Evaluate the final implication $(p \land (p \rightarrow q)) \rightarrow q$.
4. Row 1: $T \rightarrow T$ is $T$. Row 2: $F \rightarrow F$ is $T$. Row 3: $F \rightarrow T$ is $T$. Row 4: $F \rightarrow F$ is $T$.

Answer: The result is $T, T, T, T$, so it is a tautology.

1. Step 1: Use the implication law to rewrite $p \rightarrow q$ as $\neg p \lor q$.
2. Step 2: The expression becomes $\neg(\neg p \lor q)$.
3. Step 3: Apply De Morgan's Law to distribute the negation, changing $\lor$ to $\land$.
4. Step 4: This gives $\neg(\neg p) \land \neg q$.
5. Step 5: Use Double Negation to simplify $\neg(\neg p)$ to $p$.

Answer: $p \land \neg q$

1. Step 1: Create columns for $p$ and $q$.
2. Step 2: Create a column for $p \land q$.
3. Step 3: Evaluate the implication $(p \land q) \rightarrow p$.
4. Step 4: Observe that in all four rows (TT, TF, FT, FF), the result is True.

Answer: Tautology

1. Step 1: Apply De Morgan's to $\neg(\neg p \land q)$, resulting in $\neg(\neg p) \lor \neg q$.
2. Step 2: Simplify to $p \lor \neg q$.
3. Step 3: The expression is now $(p \lor \neg q) \land (p \lor q)$.
4. Step 4: Use the Distributive Law in reverse to factor out $p \lor$.
5. Step 5: This gives $p \lor (\neg q \land q)$.
6. Step 6: Since $\neg q \land q$ is always False, we have $p \lor \text{False}$.
7. Step 7: By Identity Law, this simplifies to $p$.

Answer: $p$

1. The NAND gate output is $\overline{p \cdot q}$.
2. The NOT gate negates this output: $\overline{(\overline{p \cdot q})}$.
3. Using the double negation law, $\overline{\overline{A}} = A$.
4. The expression simplifies to $p \cdot q$.

Answer: $p \cdot q$

1. Exactly one is 1 means: ($p$ is 1 AND $q$ is 0) OR ($p$ is 0 AND $q$ is 1).
2. Translate this to boolean algebra: $(p \cdot \overline{q}) + (\overline{p} \cdot q)$.
3. This uses two NOT gates, two AND gates, and one OR gate.

Answer: $(p \cdot \overline{q}) + (\overline{p} \cdot q)$

1. The condition 'either door or window' is $D + W$.
2. The master switch condition is $S \cdot (D + W)$.
3. Substitute the values: $1 \cdot (0 + 1)$.
4. Evaluate the parentheses: $1 \cdot 1 = 1$.

Answer: $A = S \cdot (D + W)$; Output is 1

1. Identify rows where $f=1$: these are $(0,1)$ and $(1,0)$.
2. Create minterm for $(0,1)$: since $x=0$ and $y=1$, the minterm is $\neg x \land y$.
3. Create minterm for $(1,0)$: since $x=1$ and $y=0$, the minterm is $x \land \neg y$.
4. Combine with OR: $f = (\neg x \land y) \lor (x \land \neg y)$.

Answer: f = (\neg x \land y) \lor (x \land \neg y)

1. Construct truth table: $f(0,0)=0$ (because $x \lor y$ is 0), $f(0,1)=1$, $f(1,0)=1$, $f(1,1)=0$ (because $\neg x \lor \neg y$ is 0).
2. Identify true rows: $(0,1)$ and $(1,0)$.
3. Write minterms: $\neg x \land y$ and $x \land \neg y$.
4. Combine: $f = (\neg x \land y) \lor (x \land \neg y)$.

Answer: f = (\neg x \land y) \lor (x \land \neg y)

1. Recall De Morgan's law: $x \lor y = \neg(\neg x \land \neg y)$.
2. Step 1: Compute $\neg x$ using $\text{NAND}(x, x)$.
3. Step 2: Compute $\neg y$ using $\text{NAND}(y, y)$.
4. Step 3: Compute the NAND of these two results: $\text{NAND}(\neg x, \neg y)$.
5. This result is $\neg(\neg x \land \neg y)$, which is $x \lor y$.

Answer: \text{NAND}(\text{NAND}(x, x), \text{NAND}(y, y))

1. Identify the predicate: $P(n, m)$ is '$m$ is the successor of $n$', which can be written as $m = n + 1$.
2. The statement says 'for every integer $n$', so we start with $\forall n \in \mathbb{Z}$.
3. It then says 'there exists a successor $m$', so we add $\exists m \in \mathbb{Z}$.
4. Combine these with the predicate.

Answer: $\forall n \in \mathbb{Z}, \exists m \in \mathbb{Z}, m = n + 1$

1. Analyze $\forall x \exists y L(x, y)$: For every person $x$, there is some person $y$ whom $x$ loves. This means everyone loves at least one person (but not necessarily the same person).
2. Analyze $\exists y \forall x L(x, y)$: There is one specific person $y$ such that every person $x$ loves that person $y$. This means there is one person who is loved by everyone.

Answer: The first means everyone loves someone; the second means there is one person loved by everyone.

1. Apply the negation rule to the first quantifier: $\neg \forall x$ becomes $\exists x$.
2. Apply the negation rule to the second quantifier: $\neg \exists y$ becomes $\forall y$.
3. Negate the inner predicate: $x^2 + y^2 = 0$ becomes $x^2 + y^2 \neq 0$.
4. Combine the results.

Answer: $\exists x \in \mathbb{R}, \forall y \in \mathbb{R}, x^2 + y^2 \neq 0$

1. Assume $n$ and $m$ are odd, so $n = 2k+1$ and $m = 2j+1$ for some integers $k, j$.
2. Sum them: $n+m = (2k+1) + (2j+1) = 2k + 2j + 2$.
3. Factor out a 2: $n+m = 2(k+j+1)$.
4. Since $k+j+1$ is an integer, $n+m$ is even by definition.

Answer: The sum is $2(k+j+1)$, which is even.

1. State the contrapositive: If $n$ is not odd (even), then $n^2$ is not odd (even).
2. Assume $n$ is even, so $n = 2k$.
3. Square $n$: $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$.
4. Since $2k^2$ is an integer, $n^2$ is even.
5. The contrapositive is true, so the original statement is true.

Answer: The contrapositive 'if $n$ is even, then $n^2$ is even' is true, proving the claim.

1. Base case $n=1$: $1^2 = 1$ and $\frac{1(2)(3)}{6} = 1$. True.
2. Inductive step: Assume $S_k = \frac{k(k+1)(2k+1)}{6}$.
3. Add $(k+1)^2$: $S_{k+1} = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$.
4. Factor out $(k+1)$: $\frac{k+1}{6} [k(2k+1) + 6(k+1)] = \frac{k+1}{6} [2k^2 + 7k + 6]$.
5. Factor the quadratic: $2k^2 + 7k + 6 = (k+2)(2k+3)$.
6. Result: $S_{k+1} = \frac{(k+1)(k+2)(2(k+1)+1)}{6}$. True.

Answer: The formula holds for $n=1$ and the inductive step is verified.

1. Identify the holes as the days of the month, so $n = 31$.
2. We want at least one hole to have 2 items, so we need $k > n$.
3. The smallest integer $k$ such that $k > 31$ is 32.

Answer: 32

1. Identify the holes as the colors: red, blue, and green, so $n = 3$.
2. We want $\lceil k/n \rceil = 4$.
3. The worst-case scenario is having 3 of each color, which is $3 \times 3 = 9$ marbles.
4. The 10th marble must create a group of 4.

Answer: 10

1. Two integers have a difference divisible by 10 if and only if they have the same remainder when divided by 10.
2. The possible remainders modulo 10 are $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$.
3. There are $n = 10$ possible remainders (holes).
4. We have $k = 11$ integers (pigeons).
5. By the Pigeonhole Principle, at least two integers must share the same remainder.
6. Therefore, their difference is a multiple of 10.

Answer: By the Pigeonhole Principle, 11 integers distributed into 10 remainder classes must result in a collision.

1. Consider the remainders of the 10 integers modulo 17. The possible remainders are $0, 1, \dots, 16$.
2. Group these remainders into 9 holes: $H_0 = \{0\}$, $H_1 = \{1, 16\}$, $H_2 = \{2, 15\}$, $H_3 = \{3, 14\}$, $H_4 = \{4, 13\}$, $H_5 = \{5, 12\}$, $H_6 = \{6, 11\}$, $H_7 = \{7, 10\}$, $H_8 = \{8, 9\}$.
3. Since there are 10 integers and only 9 holes, at least two integers must fall into the same hole by the pigeonhole principle.
4. If two integers are in $H_0$, their difference is $0-0=0 \pmod{17}$.
5. If two integers are in $H_k$ for $k > 0$, they are either the same remainder (difference is $0 \pmod{17}$) or they are the two different values in the set (sum is $k + (17-k) = 17 \equiv 0 \pmod{17}$).

Answer: By grouping remainders into pairs that sum to 17, 10 integers must occupy at least one of the 9 holes, forcing a sum or difference divisible by 17.

1. Let the $n+1$ integers be the pigeons.
2. Let the possible remainders modulo $n$ be the holes. There are exactly $n$ such remainders: $0, 1, \dots, n-1$.
3. By the pigeonhole principle, since there are $n+1$ integers and $n$ remainders, at least two integers $x$ and $y$ must have the same remainder $r$ modulo $n$.
4. Thus, $x = q_1 n + r$ and $y = q_2 n + r$.
5. The difference $x-y = (q_1 - q_2)n$, which is clearly divisible by $n$.

Answer: Two integers with the same remainder modulo $n$ have a difference divisible by $n$.

1. Define the prefix sums $S_k = a_1 + a_2 + \dots + a_k$ for $k = 1, \dots, n$.
2. Consider these $n$ sums modulo $n$.
3. If any $S_k \equiv 0 \pmod n$, then the subsequence from $a_1$ to $a_k$ is divisible by $n$.
4. If no $S_k \equiv 0 \pmod n$, then the $n$ sums must take values from the set $\{1, 2, \dots, n-1\}$.
5. Since there are $n$ sums and only $n-1$ possible values, two sums must be congruent: $S_i \equiv S_j \pmod n$ for some $i < j$.
6. Then $S_j - S_i = a_{i+1} + \dots + a_j \equiv 0 \pmod n$.

Answer: Either a prefix sum is $0 \pmod n$ or two prefix sums are equal $\pmod n$, ensuring a contiguous sum divisible by $n$.

1. Pick one person, A. There are 5 other people.
2. By the pigeonhole principle, A must either know at least 3 people or not know at least 3 people.
3. Case 1: A knows B, C, and D. If any two of B, C, D know each other, we have a group of 3 friends. If none of them know each other, B, C, and D are 3 strangers.
4. Case 2: A does not know B, C, and D. If any two of B, C, D are strangers, we have a group of 3 strangers. If all of them know each other, B, C, and D are 3 friends.

Answer: By the pigeonhole principle and case analysis, a group of 6 always contains a 3-clique or a 3-independent set.

1. Use the distributive law in reverse: $(P \lor Q) \land (P \lor \neg Q) \equiv P \lor (Q \land \neg Q)$.
2. Recognize that $Q \land \neg Q$ is a contradiction, which is always False.
3. The expression becomes $P \lor \text{False}$.
4. Any statement OR False is simply the statement itself.

Answer: P

1. Base case: For $n=1$, $1 = \frac{1(1+1)}{2} = 1$. True.
2. Inductive step: Assume $S_k = \frac{k(k+1)}{2}$.
3. For $n=k+1$, $S_{k+1} = S_k + (k+1) = \frac{k(k+1)}{2} + (k+1)$.
4. Factor out $(k+1)$: $(k+1)(\frac{k}{2} + 1) = (k+1)(\frac{k+2}{2}) = \frac{(k+1)(k+2)}{2}$.
5. This matches the formula for $n=k+1$.

Answer: \frac{n(n+1)}{2}

1. Assume $x \in A \cap (B \cap C)$. Then $x \in A$ and $x \in (B \cap C)$.
2. Since $x \in B \cap C$, then $x \in B$ and $x \in C$.
3. Thus $x \in A$, $x \in B$, and $x \in C$. This implies $x \in (A \cap B)$ and $x \in C$, so $x \in (A \cap B) \cap C$.
4. Now assume $x \in (A \cap B) \cap C$. Then $x \in (A \cap B)$ and $x \in C$.
5. Since $x \in A \cap B$, then $x \in A$ and $x \in B$.
6. Thus $x \in A$ and $x \in (B \cap C)$, so $x \in A \cap (B \cap C)$.

Answer: The sets are equal by double-inclusion.

1. The size is $2^4 = 16$.
2. Subsets of size 0: $\emptyset$.
3. Subsets of size 1: $\{1\}, \{2\}, \{3\}, \{4\}$.
4. Subsets of size 2: $\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}$.
5. Subsets of size 3: $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
6. Subsets of size 4: $\{1,2,3,4\}$.

Answer: 16 subsets.

1. Apply De Morgan's law to $(A^c \cup B)^c$: it becomes $(A^c)^c \cap B^c$.
2. Simplify the double complement: $A \cap B^c$.
3. The expression is now $(A \cap B^c) \cup (A \cap B^c)$.
4. By the idempotent law, $X \cup X = X$.
5. The result is $A \cap B^c$.

Answer: $A \cap B^c$

1. Step 1: List all pairs in $A \times B$. These are $(1, 3), (1, 4), (2, 3), (2, 4)$.
2. Step 2: Check the sum for each pair. $1+3=4$ (even), $1+4=5$ (odd), $2+3=5$ (odd), $2+4=6$ (even).
3. Step 3: Collect the pairs with even sums.

Answer: A \times B = \{ (1, 3), (1, 4), (2, 3), (2, 4) \}, R = \{ (1, 3), (2, 4) \}

1. Step 1: Check all pairs $(a, b)$ where $a, b \in \{1, 2, 3\}$.
2. Step 2: $1 \le 1, 1 \le 2, 1 \le 3$ are all true.
3. Step 3: $2 \le 2, 2 \le 3$ are true; $2 \le 1$ is false.
4. Step 4: $3 \le 3$ is true; $3 \le 1, 3 \le 2$ are false.

Answer: R = \{ (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) \}

1. Step 1: Find the size of the Cartesian product $A \times B$. $|A \times B| = 5 \times 4 = 20$.
2. Step 2: A relation is any subset of $A \times B$.
3. Step 3: The number of subsets of a set with $n$ elements is $2^n$.
4. Step 4: Substitute $n = 20$.

Answer: 2^{20} = 1,048,576

1. Check reflexivity: $(1,1), (2,2), (3,3)$ are all in $R$. Reflexive.
2. Check symmetry: $(1,2) \in R$ and $(2,1) \in R$; $(2,3) \in R$ and $(3,2) \in R$. Symmetric.
3. Check transitivity: $(1,2) \in R$ and $(2,3) \in R$, but $(1,3) \notin R$.
4. Since transitivity fails, it is not an equivalence relation.

Answer: No, it is not an equivalence relation because it is not transitive.

1. Elements in the same subset are related. For $\{1, 3, 5\}$, we have $(1,1), (3,3), (5,5), (1,3), (3,1), (1,5), (5,1), (3,5), (5,3)$.
2. For $\{2, 4\}$, we have $(2,2), (4,4), (2,4), (4,2)$.
3. For $\{6\}$, we have $(6,6)$.
4. The relation $R$ is the union of all these pairs.

Answer: $R = \{(1,1), (3,3), (5,5), (1,3), (3,1), (1,5), (5,1), (3,5), (5,3), (2,2), (4,4), (2,4), (4,2), (6,6)\}$

1. Reflexivity: $a - a = 0$. Since $n \cdot 0 = 0$, $n$ divides $a - a$, so $a \equiv a \pmod{n}$.
2. Symmetry: If $a \equiv b \pmod{n}$, then $a - b = kn$ for some integer $k$. Then $b - a = (-k)n$. Since $-k$ is an integer, $n$ divides $b - a$, so $b \equiv a \pmod{n}$.
3. Transitivity: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a - b = kn$ and $b - c = mn$. Adding these gives $(a - b) + (b - c) = kn + mn$, so $a - c = (k + m)n$. Since $k + m$ is an integer, $n$ divides $a - c$, so $a \equiv c \pmod{n}$.

Answer: The relation is reflexive, symmetric, and transitive, therefore it is an equivalence relation.

1. Check reflexivity: Every set is a subset of itself, so $A \subseteq A$ holds.
2. Check antisymmetry: If $A \subseteq B$ and $B \subseteq A$, then $A = B$ by the definition of set equality.
3. Check transitivity: If $A \subseteq B$ and $B \subseteq C$, then every element of $A$ is in $B$, and thus in $C$, so $A \subseteq C$.
4. The relation is a partial order. The power set has $2^3 = 8$ elements. The middle level consists of subsets with size 1 or 2. Specifically, the subsets of size 1 are the first level above the empty set, and subsets of size 2 are the next level. There are $\binom{3}{1} = 3$ and $\binom{3}{2} = 3$ such sets.

Answer: Yes, it is a poset; there are 3 elements in the level of singletons and 3 in the level of pairs.

1. Check all pairs $(a, b)$ where $a \neq b$.
2. Pairs like $(2, 3)$ are incomparable because $2 \nmid 3$ and $3 \nmid 2$.
3. Pairs like $(2, 5)$, $(3, 4)$, $(3, 5)$, $(4, 5)$, $(4, 6)$, $(5, 6)$ are also incomparable.
4. Pairs like $(2, 4)$ are comparable because $2 \mid 4$.

Answer: \{(2, 3), (2, 5), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6)\}

1. Check reflexivity: $a \mid a$ is true for all $a \neq 0$. For $a=0$, $0 \mid 0$ is usually defined as true in this context.
2. Check antisymmetry: For a partial order, $a R b$ and $b R a$ must imply $a = b$.
3. Consider $a = 1$ and $b = -1$. $1$ divides $-1$ (since $-1 = 1 \cdot -1$) and $-1$ divides $1$ (since $1 = -1 \cdot -1$).
4. However, $1 \neq -1$. Therefore, the relation is not antisymmetric.

Answer: No, it is not a partial order because it fails antisymmetry.

1. The total number of functions is $m^n$, where $m=5$ and $n=3$.
2. Calculation: $5^3 = 125$.
3. The number of injections is $P(m, n) = \frac{m!}{(m-n)!}$.
4. Calculation: $\frac{5!}{(5-3)!} = \frac{120}{2} = 60$.

Answer: 125 total functions, 60 injections

1. Use the surjection formula: $\sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^n$ with $m=2, n=4$.
2. For $k=0$: $\binom{2}{0}(2-0)^4 = 1 \cdot 16 = 16$.
3. For $k=1$: $\binom{2}{1}(2-1)^4 = 2 \cdot 1 = 2$.
4. For $k=2$: $\binom{2}{2}(2-2)^4 = 1 \cdot 0 = 0$.
5. Total: $16 - 2 + 0 = 14$.

Answer: 14 surjections

1. The number of injections is $P(n, n) = n!$.
2. The number of surjections is $\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)^n$.
3. From the theory of bijections, if $|A|=|B|$, any injection is automatically a surjection.
4. Therefore, the set of injections and the set of surjections are the same set (the set of bijections).
5. Both counts must equal $n!$.

Answer: Both equal $n!$

1. Calculate individual sets: $|A| = \lfloor 500/3 \rfloor = 166$, $|B| = \lfloor 500/7 \rfloor = 71$, $|C| = \lfloor 500/11 \rfloor = 45$.
2. Calculate pairs: $|A \cap B| = \lfloor 500/21 \rfloor = 23$, $|A \cap C| = \lfloor 500/33 \rfloor = 15$, $|B \cap C| = \lfloor 500/77 \rfloor = 6$.
3. Calculate triple: $|A \cap B \cap C| = \lfloor 500/231 \rfloor = 2$.
4. Apply formula: $(166 + 71 + 45) - (23 + 15 + 6) + 2 = 282 - 44 + 2 = 240$.

Answer: 240

1. Find the union: $|S \cup F \cup G| = (60 + 40 + 30) - (20 + 15 + 10) + 5$.
2. Compute: $130 - 45 + 5 = 90$.
3. Subtract from total: $100 - 90 = 10$.

Answer: 10

1. Singles: $\binom{5}{1} \times 20 = 100$.
2. Pairs: $\binom{5}{2} \times 5 = 10 \times 5 = 50$.
3. Triples: $\binom{5}{3} \times 2 = 10 \times 2 = 20$.
4. Quadruples: $\binom{5}{4} \times 1 = 5 \times 1 = 5$.
5. Quintuples: $\binom{5}{5} \times 0 = 0$.
6. Union: $100 - 50 + 20 - 5 + 0 = 65$.

Answer: 65

1. Step 1: Compute $7! = 5040$.
2. Step 2: Use the nearest integer formula $D(7) \approx 5040 / e$.
3. Step 3: $5040 / 2.7182818 \approx 1854.11$.
4. Step 4: Round to the nearest integer.

Answer: 1854

1. Step 1: Choose which 2 students get their own essays: $\binom{5}{2} = 10$.
2. Step 2: The remaining 3 students must receive a derangement of their essays: $D(3) = 2$.
3. Step 3: Multiply the choices: $10 \times 2 = 20$.

Answer: 20

1. Step 1: $D(4) = 4! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} \right)$.
2. Step 2: $D(4) = 24 \left( 1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} \right)$.
3. Step 3: $D(4) = 12 - 4 + 1 = 9$.

Answer: 9

1. Define a function $f: \mathbb{N} \to S$.
2. Let $f(n) = 3n$.
3. Check for injection: if $3n_1 = 3n_2$, then $n_1 = n_2$.
4. Check for surjection: for any $m \in S$, $m$ is a multiple of 3, so $m = 3k$ for some $k \in \mathbb{N}$. Thus $f(k) = m$.
5. Since $f$ is a bijection, the sets have the same cardinality.

Answer: $|S| = |\mathbb{N}|$

1. The current guests move from $n \to 2n$.
2. The set of occupied rooms becomes the set of even numbers: $\{2, 4, 6, \dots\}$.
3. The set of empty rooms is the set of odd numbers: $\{1, 3, 5, \dots\}$.
4. The set of odd numbers is countably infinite, so it can accommodate the $\aleph_0$ new guests.

Answer: The odd-numbered rooms become available.

1. Represent the pairs $(i, j)$ as a 2D grid.
2. Order the pairs by the sum of their components $s = i + j$.
3. For a fixed sum $s$, there are only finitely many pairs $(i, j)$.
4. List pairs with $s=2$, then $s=3$, then $s=4$, and so on.
5. This creates a sequence that includes every pair exactly once, establishing a bijection with $\mathbb{N}$.

Answer: $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$

1. Identify parameters: $n=7$ (indistinguishable balls), $k=4$ (distinguishable boxes).
2. Constraint: Surjective (no chest empty).
3. Use the formula $\binom{n-1}{k-1}$.
4. Compute $\binom{7-1}{4-1} = \binom{6}{3}$.
5. $\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$.

Answer: 20

1. Identify parameters: $n=4$ (distinguishable balls), $k=3$ (indistinguishable boxes).
2. Constraint: Surjective (no room empty).
3. This is the definition of the Stirling number of the second kind $S(4, 3)$.
4. The only partition of $4$ into $3$ non-empty sets is sizes $2, 1, 1$.
5. Number of ways to choose the pair is $\binom{4}{2} = 6$.

Answer: 6

1. Identify parameters: $n=5$ (indistinguishable balls), $k=3$ (distinguishable boxes).
2. Constraint: None.
3. Use the stars and bars formula $\binom{n+k-1}{k-1}$.
4. Compute $\binom{5+3-1}{3-1} = \binom{7}{2}$.
5. $\binom{7}{2} = \frac{7 \times 6}{2 \times 1} = 21$.

Answer: 21

1. Total arrangements of 5 books is $5! = 120$.
2. Treat books A and B as a single block. There are now 4 items to arrange: $(AB), C, D, E$.
3. Ways to arrange these 4 items is $4! = 24$.
4. Within the block, A and B can be arranged in $2! = 2$ ways: $(AB)$ or $(BA)$.
5. Total arrangements where A and B are adjacent is $24 \times 2 = 48$.
6. Subtract adjacent cases from total: $120 - 48 = 72$.

Answer: 72

1. Reflexivity: $a$ divides $a$ for all $a \in S$. (True)
2. Antisymmetry: If $a$ divides $b$ and $b$ divides $a$, then $a = b$ for positive integers. (True)
3. Transitivity: If $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$. (True)
4. Since it is reflexive, antisymmetric, and transitive, it is a partial order.

Answer: Partial order

1. This is a stars and bars problem with the constraint that each box must have at least one ball.
2. We use the formula $\binom{n-1}{k-1}$ where $n=6$ and $k=3$.
3. Calculation: $\binom{6-1}{3-1} = \binom{5}{2}$.
4. $\binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$.

Answer: 10

1. Divide $1024$ by $37$ using long division or estimation.
2. Calculate $1024 / 37 \approx 27.67$, so the quotient $q$ is $27$.
3. Multiply $27 \times 37 = 999$.
4. Subtract this from the original number: $1024 - 999 = 25$.
5. Verify that $0 \le 25 < 37$.

Answer: q = 27, r = 25

1. By definition of divisibility, $d \mid a$ means $a = dk$ for some integer $k$.
2. Similarly, $d \mid b$ means $b = dm$ for some integer $m$.
3. The sum $a + b = dk + dm$.
4. Factor out $d$ to get $a + b = d(k + m)$.
5. Since $k + m$ is an integer, $d$ divides $a + b$ by definition.

Answer: The sum is $d(k+m)$, which satisfies the definition of divisibility.

1. Factor the expression as $n(n + 1)$.
2. Consider two cases: $n$ is even or $n$ is odd.
3. If $n$ is even, $n = 2k$, so $n(n + 1) = 2k(2k + 1)$, which is a multiple of $2$.
4. If $n$ is odd, $n = 2k + 1$, so $n + 1 = 2k + 2 = 2(k + 1)$.
5. Then $n(n + 1) = (2k + 1) \cdot 2(k + 1)$, which is also a multiple of $2$.
6. In both cases, the expression is divisible by $2$.

Answer: The product of two consecutive integers is always even.

1. Divide $108$ by $30$: $108 = 3 \cdot 30 + 18$.
2. Divide $30$ by $18$: $30 = 1 \cdot 18 + 12$.
3. Divide $18$ by $12$: $18 = 1 \cdot 12 + 6$.
4. Divide $12$ by $6$: $12 = 2 \cdot 6 + 0$.
5. The last non-zero remainder is $6$.

Answer: 6

1. Divide $143$ by $25$: $143 = 5 \cdot 25 + 18$.
2. Divide $25$ by $18$: $25 = 1 \cdot 18 + 7$.
3. Divide $18$ by $7$: $18 = 2 \cdot 7 + 4$.
4. Divide $7$ by $4$: $7 = 1 \cdot 4 + 3$.
5. Divide $4$ by $3$: $4 = 1 \cdot 3 + 1$.
6. Divide $3$ by $1$: $3 = 3 \cdot 1 + 0$.
7. The GCD is $1$.

Answer: Yes, they are relatively prime because \gcd(143, 25) = 1.

1. Divide $1234$ by $56$: $1234 = 22 \cdot 56 + 2$.
2. Divide $56$ by $2$: $56 = 28 \cdot 2 + 0$.
3. The last non-zero remainder is $2$.

Answer: 2

1. Step 1: $120 = 2 \cdot 48 + 24$
2. Step 2: $48 = 2 \cdot 24 + 0$. The GCD is $24$.
3. Step 3: From the first equation, $24 = 1 \cdot 120 - 2 \cdot 48$.
4. Step 4: Thus, $x = 1$ and $y = -2$.

Answer: x = 1, y = -2

1. Step 1: $81 = 1 \cdot 57 + 24$
2. Step 2: $57 = 2 \cdot 24 + 9$
3. Step 3: $24 = 2 \cdot 9 + 6$
4. Step 4: $9 = 1 \cdot 6 + 3$
5. Step 5: $6 = 2 \cdot 3 + 0$. The GCD is $3$.
6. Step 6: $3 = 9 - 1 \cdot 6$
7. Step 7: $3 = 9 - 1(24 - 2 \cdot 9) = 3 \cdot 9 - 1 \cdot 24$
8. Step 8: $3 = 3(57 - 2 \cdot 24) - 1 \cdot 24 = 3 \cdot 57 - 7 \cdot 24$
9. Step 9: $3 = 3 \cdot 57 - 7(81 - 1 \cdot 57) = 10 \cdot 57 - 7 \cdot 81$.

Answer: 3 = (-7) \cdot 81 + 10 \cdot 57

1. Step 1: $17 = 1 \cdot 13 + 4$
2. Step 2: $13 = 3 \cdot 4 + 1$
3. Step 3: $4 = 4 \cdot 1 + 0$. The GCD is $1$.
4. Step 4: $1 = 13 - 3 \cdot 4$
5. Step 5: $1 = 13 - 3(17 - 1 \cdot 13) = 4 \cdot 13 - 3 \cdot 17$.

Answer: x = -3, y = 4

1. Divide by 2: $1260 = 2 \times 630$
2. Divide by 2 again: $630 = 2 \times 315$, so $1260 = 2^2 \times 315$
3. Divide by 3: $315 = 3 \times 105$, so $1260 = 2^2 \times 3 \times 105$
4. Divide by 3 again: $105 = 3 \times 35$, so $1260 = 2^2 \times 3^2 \times 35$
5. Divide by 5: $35 = 5 \times 7$, so $1260 = 2^2 \times 3^2 \times 5 \times 7$

Answer: 2^2 \times 3^2 \times 5^1 \times 7^1

1. Factor 420: $420 = 2 \times 210 = 2^2 \times 105 = 2^2 \times 3 \times 35 = 2^2 \times 3 \times 5 \times 7$
2. Factor 546: $546 = 2 \times 273 = 2 \times 3 \times 91 = 2 \times 3 \times 7 \times 13$
3. Identify common primes with minimum exponents: $2^1$, $3^1$, and $7^1$
4. Compute GCD: $2 \times 3 \times 7 = 42$

Answer: 42

1. Assume for contradiction that $n$ is composite.
2. Then $n = a \times b$ for some integers $1 < a \le b < n$.
3. If $a > \sqrt{n}$, then $b \ge a > \sqrt{n}$, which implies $a \times b > \sqrt{n} \times \sqrt{n} = n$.
4. This contradicts $a \times b = n$, so we must have $a \le \sqrt{n}$.
5. Since $a > 1$, $a$ must have at least one prime factor $p$.
6. Since $p \le a \le \sqrt{n}$, $n$ is divisible by a prime $p \le \sqrt{n}$, which contradicts the hypothesis.

Answer: n is prime

1. Since $2 \notin S$, every prime $p_i$ in $S$ must be an odd prime.
2. The product of any number of odd integers is always odd.
3. Therefore, the product $p_1 \cdot p_2 \cdot \dots \cdot p_n$ is odd.
4. Adding $1$ to an odd number results in an even number.
5. Since $P$ is even, it is divisible by $2$.

Answer: P is even, so $2 \mid P$.

1. Let $n = 10$.
2. Consider the number $Q = 10! + 1$.
3. By the Fundamental Theorem of Arithmetic, $Q$ must have at least one prime factor $p$.
4. If $p \le 10$, then $p$ would divide $10!$.
5. If $p$ divides both $Q$ and $10!$, it must divide their difference: $Q - 10! = 1$.
6. No prime divides $1$, so $p$ must be strictly greater than $10$.
7. Since $p$ is a factor of $Q$, $p \le Q = 10! + 1$.

Answer: Any prime factor of $10! + 1$ satisfies the condition.

1. The term $2^{2^n}$ is a power of $2$ with a positive exponent $2^n$.
2. Any positive power of $2$ is an even integer.
3. Adding $1$ to an even integer always results in an odd integer.
4. Therefore, $F_n$ is odd for all $n \ge 1$.

Answer: F_n = \text{even} + 1 = \text{odd}.

1. Simplify the bases first: $17 \equiv 2 \equiv -1 \pmod{3}$, $11 \equiv 2 \equiv -1 \pmod{3}$, and $5 \equiv 2 \equiv -1 \pmod{3}$.
2. Substitute these into the expression: $(-1)^2 + (-1) \cdot (-1) \pmod{3}$.
3. Calculate the result: $1 + 1 = 2$.
4. The residue is $2$.

Answer: 2

1. Use the property of powers: $3^2 = 9 \equiv 2 \pmod{7}$.
2. Then $3^4 = (3^2)^2 \equiv 2^2 = 4 \pmod{7}$.
3. Then $3^8 = (3^4)^2 \equiv 4^2 = 16 \equiv 2 \pmod{7}$.
4. Finally, $3^{10} = 3^8 \cdot 3^2 \equiv 2 \cdot 2 = 4 \pmod{7}$.

Answer: 4

1. Simplify each number modulo 7 first.
2. $123 = 7 \cdot 17 + 4$, so $123 \equiv 4 \pmod{7}$.
3. $456 = 7 \cdot 65 + 1$, so $456 \equiv 1 \pmod{7}$.
4. Multiply the residues: $4 \cdot 1 = 4$.
5. The result is $4$.

Answer: 4

1. Check $\gcd(9, 20)$. Since $20 = 2^2 \cdot 5$ and $9 = 3^2$, $\gcd(9, 20) = 1$. The inverse exists.
2. Use Euclidean Algorithm: $20 = 2(9) + 2$, then $9 = 4(2) + 1$.
3. Back-substitute: $1 = 9 - 4(2) = 9 - 4(20 - 2(9)) = 9 - 4(20) + 8(9) = 9(9) - 4(20)$.
4. Modulo $20$, this gives $9(9) \equiv 1 \pmod{20}$.

Answer: 9

1. Find the inverse of $11$ modulo $26$. $\gcd(11, 26) = 1$.
2. Euclidean Algorithm: $26 = 2(11) + 4$, $11 = 2(4) + 3$, $4 = 1(3) + 1$.
3. Back-substitute: $1 = 4 - 1(3) = 4 - 1(11 - 2(4)) = 3(4) - 1(11) = 3(26 - 2(11)) - 1(11) = 3(26) - 7(11)$.
4. The inverse is $-7$, which is $26 - 7 = 19$.
5. Multiply both sides by $19$: $x \equiv 19 \cdot 5 \pmod{26}$.
6. Compute $95 \pmod{26}$: $95 = 3 \cdot 26 + 17$.

Answer: 17

1. Check $\gcd(6, 9) = 3$.
2. Since $\gcd(6, 9) = 3$ and $3$ divides the constant $3$, solutions exist.
3. The inverse method fails because $\gcd(6, 9) \neq 1$.
4. Test small values: if $x=2$, $6(2) = 12$. $12 \pmod{9} = 3$.
5. Thus, $x=2$ is a solution.

Answer: x = 2 (or x = 5, 8)

1. Calculate $N = 3 \cdot 4 \cdot 5 = 60$.
2. For $n_1=3$, $M_1=20$. $20 \equiv 2 \pmod{3}$, so $y_1 = 2^{-1} \equiv 2 \pmod{3}$. Term 1: $1 \cdot 20 \cdot 2 = 40$.
3. For $n_2=4$, $M_2=15$. $15 \equiv 3 \pmod{4}$, so $y_2 = 3^{-1} \equiv 3 \pmod{4}$. Term 2: $2 \cdot 15 \cdot 3 = 90$.
4. For $n_3=5$, $M_3=12$. $12 \equiv 2 \pmod{5}$, so $y_3 = 2^{-1} \equiv 3 \pmod{5}$. Term 3: $3 \cdot 12 \cdot 3 = 108$.
5. Sum: $x = 40 + 90 + 108 = 238$.
6. Reduce modulo 60: $238 = 3 \cdot 60 + 58$.

Answer: 58

1. Calculate $N = 7 \cdot 11 = 77$.
2. For $n_1=7$, $M_1=11$. $11 \equiv 4 \pmod{7}$. The inverse of $4 \pmod{7}$ is $2$ because $4 \cdot 2 = 8 \equiv 1 \pmod{7}$. Term 1: $3 \cdot 11 \cdot 2 = 66$.
3. For $n_2=11$, $M_2=7$. $7 \equiv 7 \pmod{11}$. The inverse of $7 \pmod{11}$ is $8$ because $7 \cdot 8 = 56 \equiv 1 \pmod{11}$. Term 2: $4 \cdot 7 \cdot 8 = 224$.
4. Sum: $x = 66 + 224 = 290$.
5. Reduce modulo 77: $290 = 3 \cdot 77 + 59$.

Answer: 59

1. Check the coprimality of the moduli: $\gcd(6, 9) = 3$.
2. For a solution to exist, the remainders must be congruent modulo the GCD: $2 \equiv 5 \pmod{3}$.
3. Check: $2 \pmod{3} = 2$ and $5 \pmod{3} = 2$. Since $2 \equiv 2 \pmod{3}$, a solution exists.
4. List values for $x \equiv 5 \pmod{9}$: $5, 14, 23, 32, \dots$
5. Check against $x \equiv 2 \pmod{6}$: $5 \equiv 5 \pmod{6}$, $14 \equiv 2 \pmod{6}$.
6. The smallest positive solution is $14$.

Answer: 14

1. Check conditions: $11$ is prime and $11$ does not divide $3$.
2. By Fermat's Little Theorem, $3^{10} \equiv 1 \pmod{11}$.
3. Divide the exponent $121$ by $10$: $121 = 10 \times 12 + 1$.
4. Rewrite the expression: $3^{121} = (3^{10})^{12} \cdot 3^1$.
5. Substitute the congruence: $1^{12} \cdot 3 \equiv 3 \pmod{11}$.

Answer: 3

1. Check conditions: $17$ is prime and $17$ does not divide $2$.
2. By Fermat's Little Theorem, $2^{16} \equiv 1 \pmod{17}$.
3. Divide the exponent $50$ by $16$: $50 = 16 \times 3 + 2$.
4. Rewrite the expression: $2^{50} = (2^{16})^3 \cdot 2^2$.
5. Substitute the congruence: $1^3 \cdot 4 \equiv 4 \pmod{17}$.

Answer: 4

1. We seek $x$ such that $3x \equiv 1 \pmod{13}$.
2. By Fermat's Little Theorem, $3^{12} \equiv 1 \pmod{13}$.
3. Rewrite as $3 \cdot 3^{11} \equiv 1 \pmod{13}$.
4. Thus, the inverse is $3^{11} \pmod{13}$.
5. Compute $3^3 = 27 \equiv 1 \pmod{13}$.
6. Then $3^{11} = (3^3)^3 \cdot 3^2 \equiv 1^3 \cdot 9 \equiv 9 \pmod{13}$.

Answer: 9

1. Find the prime factorization of $72$: $72 = 8 \times 9 = 2^3 \times 3^2$.
2. Identify the distinct prime factors: $p_1 = 2$ and $p_2 = 3$.
3. Apply the formula: $\phi(72) = 72(1 - 1/2)(1 - 1/3)$.
4. Calculate: $72 \times (1/2) \times (2/3) = 36 \times (2/3) = 24$.

Answer: 24

1. Check coprimality: $\gcd(11, 10) = 1$.
2. Compute $\phi(10)$: $10 = 2 \times 5$, so $\phi(10) = 10(1/2)(4/5) = 4$.
3. Reduce the exponent modulo $\phi(10)$: $42 \pmod{4} = 2$.
4. Apply Euler's Theorem: $11^{42} \equiv 11^2 \pmod{10}$.
5. Calculate: $11^2 = 121$, and $121 \equiv 1 \pmod{10}$.

Answer: 1

1. Check coprimality: $\gcd(7, 15) = 1$.
2. Compute $\phi(15)$: $15 = 3 \times 5$, so $\phi(15) = 15(2/3)(4/5) = 8$.
3. The inverse is $7^{\phi(15)-1} = 7^7 \pmod{15}$.
4. Compute $7^7 \pmod{15}$: $7^2 = 49 \equiv 4 \pmod{15}$.
5. Then $7^4 \equiv 4^2 = 16 \equiv 1 \pmod{15}$.
6. Then $7^7 = 7^4 \times 7^2 \times 7^1 \equiv 1 \times 4 \times 7 = 28 \equiv 13 \pmod{15}$.

Answer: 13

1. Convert exponent to binary: $21 = 16 + 4 + 1$.
2. Compute squares: $3^1 \equiv 3$, $3^2 \equiv 9$, $3^4 \equiv 81 \equiv 13 \equiv -4 \pmod{17}$, $3^8 \equiv (-4)^2 \equiv 16 \equiv -1 \pmod{17}$, $3^{16} \equiv (-1)^2 \equiv 1 \pmod{17}$.
3. Multiply components: $3^{21} = 3^{16} \cdot 3^4 \cdot 3^1 \equiv 1 \cdot 13 \cdot 3 = 39$.
4. Reduce modulo 17: $39 = 2 \cdot 17 + 5$.

Answer: 5

1. Convert exponent to binary: $50 = 32 + 16 + 2$.
2. Compute squares: $2^1 \equiv 2$, $2^2 \equiv 4$, $2^4 \equiv 16 \equiv 5 \pmod{11}$, $2^8 \equiv 25 \equiv 3 \pmod{11}$, $2^{16} \equiv 9 \equiv -2 \pmod{11}$, $2^{32} \equiv 4 \pmod{11}$.
3. Multiply components: $2^{50} = 2^{32} \cdot 2^{16} \cdot 2^2 \equiv 4 \cdot 9 \cdot 4 = 144$.
4. Reduce modulo 11: $144 = 13 \cdot 11 + 1$.

Answer: 1

1. First, use Euler's Theorem to reduce the exponent: $\phi(13) = 12$. $103 \pmod{12} = 7$.
2. Now compute $5^7 \pmod{13}$. Binary: $7 = 4 + 2 + 1$.
3. Compute squares: $5^1 \equiv 5$, $5^2 \equiv 25 \equiv 12 \equiv -1 \pmod{13}$, $5^4 \equiv (-1)^2 \equiv 1 \pmod{13}$.
4. Multiply components: $5^7 = 5^4 \cdot 5^2 \cdot 5^1 \equiv 1 \cdot 12 \cdot 5 = 60$.
5. Reduce modulo 13: $60 = 4 \cdot 13 + 8$.

Answer: 8

1. Compute $n = 7 \times 13 = 91$.
2. Compute $\phi(n) = (7-1)(13-1) = 6 \times 12 = 72$.
3. Find $d$ such that $5d \equiv 1 \pmod{72}$. Since $5 \times 29 = 145 = 2 \times 72 + 1$, we have $d=29$.
4. Encrypt $M=2$: $C = 2^5 \pmod{91} = 32 \pmod{91} = 32$.

Answer: n=91, \phi(n)=72, d=29, C=32

1. The private key $d$ for $n=33, e=3$ was found to be $7$.
2. Compute $M = 15^7 \pmod{33}$.
3. Using fast exponentiation: $15^1 \equiv 15$, $15^2 = 225 = 6 \times 33 + 27 \equiv 27 \equiv -6 \pmod{33}$.
4. $15^4 \equiv (-6)^2 = 36 \equiv 3 \pmod{33}$.
5. $15^7 = 15^4 \times 15^2 \times 15^1 \equiv 3 \times (-6) \times 15 = -18 \times 15 = -270$.
6. $-270 \pmod{33}$: $33 \times (-9) = -297$. $-270 - (-297) = 27$.

Answer: M=27

1. Compute $n = 11 \times 17 = 187$.
2. Compute $\phi(n) = 10 \times 16 = 160$.
3. Solve $7d \equiv 1 \pmod{160}$.
4. Apply Euclidean Algorithm: $160 = 22 \times 7 + 6$; $7 = 1 \times 6 + 1$.
5. Back-substitute: $1 = 7 - 1(6) = 7 - 1(160 - 22 \times 7) = 23 \times 7 - 1 \times 160$.
6. Thus, $23 \times 7 \equiv 1 \pmod{160}$, so $d=23$.

Answer: d=23

1. Compute $n = 3 \times 11 = 33$.
2. Compute $\phi(n) = (3-1)(11-1) = 2 \times 10 = 20$.
3. Find $d$ such that $3d \equiv 1 \pmod{20}$. Since $3 \times 7 = 21 \equiv 1 \pmod{20}$, we have $d=7$.
4. Encrypt $M=5$: $C = 5^3 \pmod{33} = 125 \pmod{33}$.
5. Since $33 \times 3 = 99$, $125 - 99 = 26$.

Answer: d=7, C=26

1. Compute $M = 26^7 \pmod{33}$.
2. Use repeated squaring: $26^1 \equiv 26 \equiv -7 \pmod{33}$.
3. $26^2 \equiv (-7)^2 = 49 \equiv 16 \pmod{33}$.
4. $26^4 \equiv 16^2 = 256$. $256 = 33 \times 7 + 25$, so $26^4 \equiv 25 \equiv -8 \pmod{33}$.
5. $26^7 = 26^4 \times 26^2 \times 26^1 \equiv (-8) \times 16 \times (-7) \pmod{33}$.
6. $-8 \times 16 = -128$. $-128 = 33 \times (-4) + 4$, so $-128 \equiv 4 \pmod{33}$.
7. $4 \times (-7) = -28$. $-28 \equiv 5 \pmod{33}$.

Answer: M=5

1. The attacker calculates $\phi(n) = (61-1)(53-1) = 60 \times 52 = 3120$.
2. They now solve $17d \equiv 1 \pmod{3120}$ using the extended Euclidean algorithm.
3. Step 1: $3120 = 183 \times 17 + 9$.
4. Step 2: $17 = 1 \times 9 + 8$.
5. Step 3: $9 = 1 \times 8 + 1$.
6. Back-substituting: $1 = 9 - 8 = 9 - (17 - 9) = 2(9) - 17 = 2(3120 - 183 \times 17) - 17 = 2(3120) - 367 \times 17$.
7. Thus, $d \equiv -367 \pmod{3120}$.
8. Adding the modulus: $d = 3120 - 367 = 2753$.

Answer: d=2753

1. Use the Euclidean algorithm: $28 = 1 \cdot 15 + 13$, then $15 = 1 \cdot 13 + 2$, then $13 = 6 \cdot 2 + 1$.
2. Work backwards: $1 = 13 - 6 \cdot 2$.
3. Substitute $2 = 15 - 13$: $1 = 13 - 6(15 - 13) = 7 \cdot 13 - 6 \cdot 15$.
4. Substitute $13 = 28 - 15$: $1 = 7(28 - 15) - 6 \cdot 15 = 7 \cdot 28 - 13 \cdot 15$.
5. The inverse is $-13$, which is $28 - 13 = 15$ modulo $28$.

Answer: 15

1. Since $11$ is prime and $2$ is not a multiple of $11$, $2^{10} \equiv 1 \pmod{11}$.
2. Rewrite the exponent: $100 = 10 \cdot 10 + 0$.
3. Then $2^{100} = (2^{10})^{10} \cdot 2^0 \equiv 1^{10} \cdot 1 \pmod{11}$.
4. The result is $1$.

Answer: 1

1. Calculate $n = 3 \cdot 11 = 33$.
2. Calculate $\phi(n) = (3-1)(11-1) = 2 \cdot 10 = 20$.
3. Solve $3d \equiv 1 \pmod{20}$.
4. We look for a multiple of $20$ plus $1$ that is divisible by $3$. $21$ is divisible by $3$.
5. Since $3 \cdot 7 = 21$, $d = 7$.

Answer: 7

1. Identify if order matters. Since the roles are distinct (VP vs Secretary), order matters.
2. Identify if repetition is allowed. One person cannot hold both roles, so no repetition.
3. Use the permutation formula $P(15, 2)$.
4. Calculate $15 \times 14 = 210$.

Answer: 210

1. Identify if order matters. The problem explicitly states it does not.
2. Identify if repetition is allowed. You are choosing a set of 4 distinct colors, so no repetition.
3. Use the combination formula $\binom{12}{4}$.
4. Calculate $\frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = \frac{11880}{24} = 495$.

Answer: 495

1. Identify if order matters. The order in the box does not matter.
2. Identify if repetition is allowed. You can buy multiple donuts of the same type, so yes.
3. Use the stars and bars formula with $n=5$ types and $k=12$ items.
4. Calculate $\binom{5+12-1}{12} = \binom{16}{12} = \binom{16}{4}$.
5. Calculate $\frac{16 \times 15 \times 14 \times 13}{4 \times 3 \times 2 \times 1} = \frac{43680}{24} = 1820$.

Answer: 1820

1. Step 1: Define the set. We are counting the number of ways to choose a committee of $k$ people from $n$, and then choosing $m$ of those $k$ people to be on a special sub-committee.
2. Step 2: Count method 1. First choose the $k$ committee members in $\binom{n}{k}$ ways, then choose $m$ sub-committee members from the $k$ in $\binom{k}{m}$ ways. Total: $\binom{n}{k} \binom{k}{m}$.
3. Step 3: Count method 2. First choose the $m$ sub-committee members from the total $n$ in $\binom{n}{m}$ ways. Then, choose the remaining $k-m$ committee members from the remaining $n-m$ people in $\binom{n-m}{k-m}$ ways. Total: $\binom{n}{m} \binom{n-m}{k-m}$.
4. Step 4: Since both methods count the same set of configurations, the expressions must be equal.

Answer: \binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n-m}{k-m}

1. Step 1: Define the set. We are counting the number of ways to choose a subset of $k$ elements from a set of $n$ elements.
2. Step 2: Method 1. By definition, there are $\binom{n}{k}$ ways to choose $k$ elements to be in the subset.
3. Step 3: Method 2. Choosing $k$ elements to be in the subset is logically identical to choosing $n-k$ elements to be excluded from the subset. There are $\binom{n}{n-k}$ ways to choose the excluded elements.
4. Step 4: Because every selection of $k$ elements uniquely determines a selection of $n-k$ elements, the counts are equal.

Answer: \binom{n}{k} = \binom{n}{n-k}

1. Step 1: Define the set. We are counting the total number of subsets of a set with $n$ elements (the power set).
2. Step 2: Method 1. We can count subsets by their size $k$. For a fixed $k$, there are $\binom{n}{k}$ subsets. Summing from $k=0$ to $n$ gives $\sum_{k=0}^{n} \binom{n}{k}$.
3. Step 3: Method 2. For each of the $n$ elements, we have a binary choice: it is either in the subset or it is not. By the multiplication principle, there are $2 \times 2 \times \dots \times 2$ ($n$ times), which is $2^n$ ways.
4. Step 4: Both methods count the total number of subsets, so the identity holds.

Answer: \sum_{k=0}^{n} \binom{n}{k} = 2^n

1. Identify $k=3$ and $n=10$ in the identity $\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}$.
2. Substitute the values: $\sum_{i=3}^{10} \binom{i}{3} = \binom{10+1}{3+1} = \binom{11}{4}$.
3. Calculate $\binom{11}{4} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1} = 330$.

Answer: 330

1. The total number of ways is $\binom{7+6}{5} = \binom{13}{5}$.
2. Using Vandermonde's identity $\binom{n+m}{r} = \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k}$ with $n=7, m=6, r=5$.
3. The sum is $\sum_{k=0}^{5} \binom{7}{k} \binom{6}{5-k} = \binom{7}{0}\binom{6}{5} + \binom{7}{1}\binom{6}{4} + \binom{7}{2}\binom{6}{3} + \binom{7}{3}\binom{6}{2} + \binom{7}{4}\binom{6}{1} + \binom{7}{5}\binom{6}{0}$.

Answer: \sum_{k=0}^{5} \binom{7}{k} \binom{6}{5-k}

1. Consider a set of $2n$ objects divided into two groups of $n$ objects each.
2. The number of ways to choose $n$ objects from the $2n$ is $\binom{2n}{n}$.
3. Alternatively, we can choose $k$ objects from the first group and $n-k$ objects from the second group for $k=0, 1, \dots, n$.
4. The number of ways to do this is $\sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}$.
5. Since $\binom{n}{n-k} = \binom{n}{k}$, the sum becomes $\sum_{k=0}^{n} \binom{n}{k}^2$.

Answer: \binom{2n}{n}

1. Identify that this is a strict composition since parts must be positive.
2. Use the formula $\binom{n-1}{k-1}$.
3. Substitute $n=12$ and $k=4$ to get $\binom{11}{3}$.
4. Calculate $\frac{11 \times 10 \times 9}{3 \times 2 \times 1} = 11 \times 5 \times 3 = 165$.

Answer: 165

1. Identify that this is a weak composition since parts can be zero.
2. Use the formula $\binom{n+k-1}{k-1}$.
3. Substitute $n=8$ and $k=3$ to get $\binom{8+3-1}{3-1} = \binom{10}{2}$.
4. Calculate $\frac{10 \times 9}{2 \times 1} = 45$.

Answer: 45

1. Set constraints: $x_1 \ge 5, x_2 \ge 1, x_3 \ge 1$.
2. Subtract the minimum requirements from the total: $20 - (5+1+1) = 13$.
3. Distribute the remaining 13 units into 3 parts using the weak formula: $\binom{13+3-1}{3-1}$.
4. Calculate $\binom{15}{2} = \frac{15 \times 14}{2 \times 1} = 105$.

Answer: 105

1. Draw the Ferrers diagram: Row 1 has 6 dots, Row 2 has 3, Row 3 has 2, Row 4 has 1.
2. Count the columns: Column 1 has 4 dots, Column 2 has 3, Column 3 has 3, Column 4 has 1, Column 5 has 1, Column 6 has 1.
3. The conjugate partition is the sequence of column lengths.

Answer: 4 + 3 + 3 + 1 + 1 + 1

1. We need $n_1 + n_2 + n_3 = 6$ with $n_1 \ge n_2 \ge n_3 \ge 1$.
2. If $n_1 = 4$, then $n_2 + n_3 = 2$, which forces $n_2 = 1, n_3 = 1$. Partition: $4+1+1$.
3. If $n_1 = 3$, then $n_2 + n_3 = 3$, which forces $n_2 = 2, n_3 = 1$. Partition: $3+2+1$.
4. If $n_1 = 2$, then $n_2 + n_3 = 4$, which forces $n_2 = 2, n_3 = 2$. Partition: $2+2+2$.

Answer: 4+1+1, 3+2+1, 2+2+2

1. The number of partitions of $7$ with largest part $2$ is equal to the number of partitions of $7$ into exactly $2$ parts.
2. We list partitions of $7$ into exactly $2$ parts: $6+1, 5+2, 4+3$.
3. There are $3$ such partitions.

Answer: 3

1. Identify that $n=3$ pairs of parentheses corresponds to the 3rd Catalan number $C_3$.
2. Apply the formula $C_n = \frac{1}{n+1} \binom{2n}{n}$.
3. Compute $\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$.
4. Calculate $C_3 = \frac{1}{4} \times 20 = 5$.

Answer: 5

1. The number of triangulations of a polygon with $k$ sides is $C_{k-2}$.
2. Here $k=6$, so we need $C_{6-2} = C_4$.
3. Apply the formula $C_4 = \frac{1}{5} \binom{8}{4}$.
4. Compute $\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$.
5. Calculate $C_4 = \frac{70}{5} = 14$.

Answer: 14

1. This is the definition of the 5th Catalan number $C_5$.
2. Apply the formula $C_5 = \frac{1}{6} \binom{10}{5}$.
3. Compute $\binom{10}{5} = \frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1} = 252$.
4. Calculate $C_5 = \frac{252}{6} = 42$.

Answer: 42

1. Identify $n = 5$, so we need $\binom{10}{5} - \binom{10}{4}$.
2. Calculate $\binom{10}{5} = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 252$.
3. Calculate $\binom{10}{4} = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210$.
4. Subtract the results: $252 - 210 = 42$.

Answer: 42

1. The reflection line is $y = x + 2$.
2. The reflection of a point $(x, y)$ across $y = x + k$ is $(y-k, x+k)$.
3. Here $k = 2$, so the point $(n, n)$ reflects to $(n-2, n+2)$.

Answer: (n-2, n+2)

1. Map each 'Right' step to an opening parenthesis '(' and each 'Up' step to a closing parenthesis ')'.
2. A path stays below the diagonal if at any point, the number of Right steps is greater than or equal to the number of Up steps.
3. In parentheses, this means at any point, the number of '(' is greater than or equal to the number of ')'.
4. Since the path ends at $(n,n)$, there are exactly $n$ of each, resulting in a balanced string of $2n$ parentheses.

Answer: The mapping is Right $\to$ '(' and Up $\to$ ')'.

1. Use the recurrence $S(n, k) = S(n-1, k-1) + k S(n-1, k)$.
2. For $n=5, k=2$: $S(5, 2) = S(4, 1) + 2 S(4, 2)$.
3. We know $S(4, 1) = 1$.
4. From the lesson, $S(4, 2) = 7$.
5. Calculate $S(5, 2) = 1 + 2(7) = 1 + 14 = 15$.

Answer: 15

1. Use the recurrence $c(n, k) = c(n-1, k-1) + (n-1) c(n-1, k)$.
2. For $n=4, k=3$: $c(4, 3) = c(3, 2) + 3 c(3, 3)$.
3. From the lesson, $c(3, 2) = 3$.
4. We know $c(3, 3) = 1$.
5. Calculate $c(4, 3) = 3 + 3(1) = 6$.

Answer: 6

1. The Bell number $B_3$ is the sum $\sum_{k=1}^{3} S(3, k)$.
2. Compute the terms: $S(3, 1) = 1$, $S(3, 2) = 3$, $S(3, 3) = 1$.
3. Sum them: $1 + 3 + 1 = 5$.
4. The meaning is that there are 5 distinct equivalence relations that can be defined on a set of 3 elements.

Answer: 5

1. The group size is $|G| = 5$.
2. For $k=0$, $\gcd(5,0)=5$, so $|X^{r_0}| = 3^5 = 243$.
3. For $k=1, 2, 3, 4$, $\gcd(5,k)=1$, so $|X^{r_k}| = 3^1 = 3$.
4. Sum of fixed points: $243 + 3 + 3 + 3 + 3 = 255$.
5. Number of orbits: $255 / 5 = 51$.

Answer: 51

1. The group size is $|G| = 4$.
2. For $k=0$, $\gcd(4,0)=4$, so $|X^{r_0}| = 2^4 = 16$.
3. For $k=1$, $\gcd(4,1)=1$, so $|X^{r_1}| = 2^1 = 2$.
4. For $k=2$, $\gcd(4,2)=2$, so $|X^{r_2}| = 2^2 = 4$.
5. For $k=3$, $\gcd(4,3)=1$, so $|X^{r_3}| = 2^1 = 2$.
6. Sum: $16 + 2 + 4 + 2 = 24$.
7. Orbits: $24 / 4 = 6$.

Answer: 6

1. The group size is $|G| = 6$.
2. For $k=0$, $\gcd(6,0)=6$, so $|X^{r_0}| = 3^6 = 729$.
3. For $k=1$, $\gcd(6,1)=1$, so $|X^{r_1}| = 3^1 = 3$.
4. For $k=2$, $\gcd(6,2)=2$, so $|X^{r_2}| = 3^2 = 9$.
5. For $k=3$, $\gcd(6,3)=3$, so $|X^{r_3}| = 3^3 = 27$.
6. For $k=4$, $\gcd(6,4)=2$, so $|X^{r_4}| = 3^2 = 9$.
7. For $k=5$, $\gcd(6,5)=1$, so $|X^{r_5}| = 3^1 = 3$.
8. Sum: $729 + 3 + 9 + 27 + 9 + 3 = 780$.
9. Orbits: $780 / 6 = 130$.

Answer: 130

1. Arrange 5 vertices in a circle.
2. Colour the edges of the outer pentagon red.
3. Colour the edges of the inner star (the diagonals) blue.
4. Check all possible triangles: any three vertices will have at least one red edge and at least one blue edge.
5. Since no monochromatic triangle exists, $R(3, 3)$ must be greater than 5.

Answer: A pentagon of red edges and a star of blue edges avoids monochromatic triangles.

1. The number of items is $n = 5$ (edges).
2. The number of containers is $k = 2$ (colours).
3. By the Pigeonhole Principle, at least $\lceil n/k \rceil$ items must be in one container.
4. $\lceil 5/2 \rceil = 3$.

Answer: 3

1. Person A is connected to B, C, and D via red edges.
2. The problem states B, C, and D are mutual strangers.
3. In our graph model, 'mutual strangers' means the edges between B, C, and D are all blue.
4. Therefore, the vertices B, C, and D form a blue triangle.
5. Yes, a monochromatic triangle exists.

Answer: Yes, a blue triangle formed by the three people who are mutual strangers.

1. Identify $n = 2$ and $r = 3$.
2. Calculate the number of subsets of size 3: $\binom{2}{3} = 0$.
3. Calculate the probability of a monochromatic triangle: $0 \cdot 2^{1-3} = 0$.
4. Since $0 < 1$, the condition is satisfied.

Answer: Yes, it proves $R(3, 3) > 2$.

1. The probability for a fixed set of 4 is $2^{1-6} = 1/32$.
2. We need $\binom{n}{4} < 32$.
3. For $n=6$, $\binom{6}{4} = 15 < 32$.
4. For $n=7$, $\binom{7}{4} = 35 \not< 32$.

Answer: n = 6

1. Set $n = 10$ and $r = 5$.
2. Calculate $\binom{10}{5} = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 252$.
3. Calculate the probability of a monochromatic $K_5$: $2^{1 - \binom{5}{2}} = 2^{1-10} = 2^{-9} = 1/512$.
4. Check the inequality: $252 \cdot (1/512) = 252/512 \approx 0.492$.
5. Since $0.492 < 1$, the probabilistic method proves $R(5, 5) > 10$.

Answer: The probability of failure is $252/512 < 1$, so $R(5, 5) > 10$.

1. We need to find the Stirling number of the second kind $S(6, 2)$.
2. The formula for $S(n, 2)$ is $2^{n-1} - 1$.
3. Plugging in $n=6$, we get $2^{6-1} - 1 = 2^5 - 1$.
4. This equals $32 - 1 = 31$.

Answer: 31

1. The number of ways to triangulate a convex polygon with $n+2$ sides is given by the $n$-th Catalan number $C_n$.
2. Here, $n+2 = 6$, so $n = 4$.
3. We calculate $C_4 = \frac{1}{4+1} \binom{2 \times 4}{4} = \frac{1}{5} \binom{8}{4}$.
4. $\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$.
5. The result is $70 / 5 = 14$.

Answer: 14

1. The group $G$ has 3 rotations: $0^{\circ}, 120^{\circ}, 240^{\circ}$.
2. For $0^{\circ}$, all $3^3 = 27$ colorings are fixed.
3. For $120^{\circ}$, all beads must be the same color, so 3 fixed points.
4. For $240^{\circ}$, all beads must be the same color, so 3 fixed points.
5. By Burnside's Lemma, the number of orbits is $\frac{1}{3}(27 + 3 + 3) = \frac{33}{3} = 11$.

Answer: 11

1. The last move to reach step $n$ must be a $1$-step, a $2$-step, or a $3$-step.
2. This gives the recurrence $a_n = a_{n-1} + a_{n-2} + a_{n-3}$.
3. For $n=3$: $a_3 = a_2 + a_1 + a_0 = 2 + 1 + 1 = 4$.
4. For $n=4$: $a_4 = a_3 + a_2 + a_1 = 4 + 2 + 1 = 7$.

Answer: a_n = a_{n-1} + a_{n-2} + a_{n-3}, a_4 = 7

1. If the string ends in 'A', the previous $n-1$ characters can be any valid string: $a_{n-1}$ ways.
2. If the string ends in 'B', the character before it must be 'A'. The previous $n-2$ characters can be any valid string: $a_{n-2}$ ways.
3. The recurrence is $a_n = a_{n-1} + a_{n-2}$.
4. Base cases: $a_1 = 2$ ('A', 'B'), $a_2 = 3$ ('AA', 'AB', 'BA').
5. Compute: $a_3 = 3+2=5, a_4 = 5+3=8, a_5 = 8+5=13$.

Answer: a_n = a_{n-1} + a_{n-2}, a_5 = 13

1. For $n=1$: $a_1 = 2^1 - 1 = 1$. Matches base case.
2. For $n=2$: $a_2 = 2(1) + 1 = 3$. Also $2^2 - 1 = 3$.
3. For $n=3$: $a_3 = 2(3) + 1 = 7$. Also $2^3 - 1 = 7$.

Answer: a_1=1, a_2=3, a_3=7

1. The characteristic equation is $r^2 - 4r + 3 = 0$.
2. Factoring gives $(r-1)(r-3) = 0$, so roots are $r_1 = 1$ and $r_2 = 3$.
3. General solution: $a_n = A(1^n) + B(3^n) = A + B(3^n)$.
4. Using $a_0 = 2$: $A + B = 2$.
5. Using $a_1 = 4$: $A + 3B = 4$.
6. Subtracting the first from the second: $2B = 2$, so $B = 1$. Then $A = 1$.

Answer: a_n = 1 + 3^n

1. Characteristic equation: $r^2 - r - 6 = 0$.
2. Factoring: $(r-3)(r+2) = 0$, so roots are $3$ and $-2$.
3. General solution: $a_n = A(3^n) + B(-2^n)$.
4. Base cases: $A + B = 5$ and $3A - 2B = 5$.
5. From first: $B = 5 - A$. Substitute: $3A - 2(5 - A) = 5 \implies 5A - 10 = 5 \implies 5A = 15 \implies A = 3$.
6. Then $B = 5 - 3 = 2$.

Answer: a_n = 3(3^n) + 2(-2^n)

1. Characteristic equation: $r^2 - 7r + 10 = 0$.
2. Factoring: $(r-2)(r-5) = 0$, so roots are $2$ and $5$.
3. General solution: $a_n = A(2^n) + B(5^n)$.
4. Base cases: $A + B = 2$ and $2A + 5B = 7$.
5. Multiply first by 2: $2A + 2B = 4$.
6. Subtract from second: $3B = 3 \implies B = 1$.
7. Then $A = 2 - 1 = 1$.

Answer: a_n = 2^n + 5^n

1. The characteristic equation is $r^2 - 6r + 9 = 0$, which factors as $(r-3)^2 = 0$.
2. The root is $r = 3$ (repeated), so the general solution is $a_n = A(3^n) + Bn(3^n)$.
3. Using $a_0 = 1$: $A(3^0) + B(0)(3^0) = 1$, so $A = 1$.
4. Using $a_1 = 6$: $1(3^1) + B(1)(3^1) = 6$, which means $3 + 3B = 6$, so $3B = 3$ and $B = 1$.
5. The closed form is $a_n = 3^n + n 3^n = (n+1)3^n$.

Answer: a_n = (n+1)3^n

1. The characteristic equation is $r^2 - 4r + 8 = 0$.
2. Using the quadratic formula: $r = \frac{4 \pm \sqrt{16-32}}{2} = 2 \pm 2i$.
3. Magnitude $\rho = \sqrt{2^2 + 2^2} = \sqrt{8} = 2\sqrt{2}$. Angle $\theta = \operatorname{atan}(2/2) = \pi/4$.
4. General solution: $a_n = (2\sqrt{2})^n (C \cos(n\pi/4) + D \sin(n\pi/4))$.
5. For $a_0 = 1$: $1(C(1) + D(0)) = 1$, so $C = 1$.
6. For $a_1 = 2$: $2\sqrt{2}(1 \cdot \frac{1}{\sqrt{2}} + D \cdot \frac{1}{\sqrt{2}}) = 2$, which simplifies to $2 + 2D = 2$, so $D = 0$.
7. The closed form is $a_n = (2\sqrt{2})^n \cos(n\pi/4)$.

Answer: a_n = (2\sqrt{2})^n \cos(n\pi/4)

1. The characteristic equation is $r^2 - 2r + 1 = 0$, which is $(r-1)^2 = 0$.
2. The root is $r = 1$ (repeated), so $a_n = A(1^n) + Bn(1^n) = A + Bn$.
3. Using $a_0 = 0$: $A + B(0) = 0$, so $A = 0$.
4. Using $a_1 = 1$: $0 + B(1) = 1$, so $B = 1$.
5. The closed form is $a_n = n$.

Answer: a_n = n

1. Find homogeneous solution: $r - 3 = 0 \implies a_n^{(h)} = A 3^n$.
2. Guess particular solution: $a_n^{(p)} = K$. Plug in: $K = 3K + 4 \implies -2K = 4 \implies K = -2$.
3. General solution: $a_n = A 3^n - 2$.
4. Use base case $a_0 = 2$: $A 3^0 - 2 = 2 \implies A - 2 = 2 \implies A = 4$.
5. Final solution: $a_n = 4 \times 3^n - 2$.

Answer: a_n = 4 \times 3^n - 2

1. Homogeneous solution: $r - 2 = 0 \implies a_n^{(h)} = A 2^n$.
2. Guess particular solution: $a_n^{(p)} = Kn + L$.
3. Plug in: $Kn + L = 2(K(n-1) + L) + n = 2Kn - 2K + 2L + n$.
4. Match coefficients: $K = 2K + 1 \implies K = -1$. Constant terms: $L = -2K + 2L \implies L = 2K = -2$.
5. General solution: $a_n = A 2^n - n - 2$.
6. Use base case $a_0 = 1$: $A - 0 - 2 = 1 \implies A = 3$.
7. Final solution: $a_n = 3 \times 2^n - n - 2$.

Answer: a_n = 3 \times 2^n - n - 2

1. Homogeneous: $r^2 - 4r + 4 = 0 \implies (r-2)^2 = 0$. Roots are $2, 2$. $a_n^{(h)} = A 2^n + B n 2^n$.
2. Forcing function $2^n$ is a double root of the characteristic equation. Guess $a_n^{(p)} = K n^2 2^n$.
3. Plug in: $K n^2 2^n = 4 K (n-1)^2 2^{n-1} - 4 K (n-2)^2 2^{n-2} + 2^n$.
4. Divide by $2^{n-2}$: $4 K n^2 = 8 K (n^2 - 2n + 1) - 4 K (n^2 - 4n + 4) + 4$.
5. Simplify: $4 K n^2 = 8 K n^2 - 16 K n + 8 K - 4 K n^2 + 16 K n - 16 K + 4$.
6. The $n^2$ and $n$ terms cancel: $0 = -8 K + 4 \implies K = 0.5$.
7. General solution: $a_n = A 2^n + B n 2^n + 0.5 n^2 2^n$.
8. Base cases: $a_0 = 1 \implies A = 1$. $a_1 = 4 \implies 2 A + 2 B + 0.5(1)(2) = 4 \implies 2 + 2 B + 1 = 4 \implies 2 B = 1 \implies B = 0.5$.
9. Final solution: $a_n = 2^n + 0.5 n 2^n + 0.5 n^2 2^n = (1 + 0.5 n + 0.5 n^2) 2^n$.

Answer: a_n = (1 + 0.5n + 0.5n^2) 2^n

1. The sequence is $1, 3, 9, 27, \dots$
2. The generating function is $G(x) = \sum_{n=0}^{\infty} 3^n x^n$.
3. This is a geometric series with common ratio $3x$.
4. Using the formula $\frac{1}{1-r}$, we substitute $r = 3x$.

Answer: G(x) = \frac{1}{1-3x}

1. We know that $\frac{1}{1-x}$ corresponds to the sequence $1, 1, 1, \dots$ (all ones).
2. Multiplying by $x^3$ shifts the sequence to the right by 3 positions.
3. The first three terms $a_0, a_1, a_2$ become $0$.
4. The terms from $a_3$ onwards are all $1$.

Answer: a_n = 0 \text{ for } n < 3, a_n = 1 \text{ for } n \ge 3

1. We know the generating function for $b_n = 2^n$ is $B(x) = \frac{1}{1-2x}$.
2. To introduce the factor of $n$, we use the operator $x \frac{d}{dx}$.
3. Compute the derivative: $\frac{d}{dx}(1-2x)^{-1} = -1(1-2x)^{-2} \cdot (-2) = \frac{2}{(1-2x)^2}$.
4. Multiply by $x$ to get $G(x) = \frac{2x}{(1-2x)^2}$.

Answer: G(x) = \frac{2x}{(1-2x)^2}

1. Define $G(x) = \sum_{n=0}^{\infty} a_n x^n$.
2. Multiply recurrence by $x^n$ and sum from $n=1$: $\sum_{n=1}^{\infty} a_n x^n = 4 \sum_{n=1}^{\infty} a_{n-1} x^n$.
3. Rewrite in terms of $G(x)$: $G(x) - a_0 = 4x G(x)$.
4. Substitute $a_0 = 5$: $G(x) - 5 = 4x G(x)$.
5. Solve for $G(x)$: $G(x)(1-4x) = 5 \implies G(x) = \frac{5}{1-4x}$.
6. Decode using the geometric series: $a_n = 5 \cdot 4^n$.

Answer: a_n = 5 \cdot 4^n

1. Sum from $n=2$: $\sum_{n=2}^{\infty} a_n x^n = 3 \sum_{n=2}^{\infty} a_{n-1} x^n - 2 \sum_{n=2}^{\infty} a_{n-2} x^n$.
2. Substitute $G(x)$: $G(x) - a_0 - a_1 x = 3x(G(x) - a_0) - 2x^2 G(x)$.
3. Substitute $a_0=0, a_1=1$: $G(x) - x = 3x G(x) - 2x^2 G(x)$.
4. Solve for $G(x)$: $G(x)(1 - 3x + 2x^2) = x \implies G(x) = \frac{x}{(1-x)(1-2x)}$.
5. Partial fractions: $\frac{x}{(1-x)(1-2x)} = \frac{-1}{1-x} + \frac{1}{1-2x}$.
6. Decode: $a_n = -1(1^n) + 1(2^n) = 2^n - 1$.

Answer: a_n = 2^n - 1

1. Sum from $n=1$: $\sum_{n=1}^{\infty} a_n x^n = 2 \sum_{n=1}^{\infty} a_{n-1} x^n + \sum_{n=1}^{\infty} x^n$.
2. Substitute $G(x)$: $G(x) - a_0 = 2x G(x) + \frac{x}{1-x}$.
3. Substitute $a_0=0$: $G(x)(1-2x) = \frac{x}{1-x}$.
4. Solve for $G(x)$: $G(x) = \frac{x}{(1-x)(1-2x)}$.
5. Partial fractions: $G(x) = \frac{-1}{1-x} + \frac{1}{1-2x}$.
6. Decode: $a_n = 2^n - 1$.

Answer: a_n = 2^n - 1

1. The generating function for $1\text{p}$ coins is $G_1(x) = 1 + x + x^2 + \dots = \frac{1}{1-x}$.
2. The generating function for $3\text{p}$ coins is $G_3(x) = 1 + x^3 + x^6 + \dots = \frac{1}{1-x^3}$.
3. The total generating function is $G(x) = (1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + \dots)(1 + x^3 + x^6 + \dots)$.
4. To get $x^7$, we can have $x^7 \cdot 1$, $x^4 \cdot x^3$, or $x^1 \cdot x^6$.
5. There are $3$ such pairs.

Answer: 3

1. For A, the generating function is $G_A(x) = x + x^2 + x^3 + x^4 + x^5 + \dots = \frac{x}{1-x}$.
2. For B, the generating function is $G_B(x) = 1 + x + x^2$.
3. We want the coefficient of $x^5$ in $G(x) = (x + x^2 + x^3 + x^4 + x^5)(1 + x + x^2)$.
4. The pairs $(a, b)$ that sum to $5$ are $(5, 0), (4, 1), (3, 2)$.
5. There are $3$ ways.

Answer: 3

1. The generating function for $1\text{p}$ is $\frac{1}{1-x}$.
2. The generating function for $2\text{p}$ is $\frac{1}{1-x^2}$.
3. The generating function for $5\text{p}$ is $(1 + x^5)$ because we can use zero or one.
4. Total $G(x) = \frac{1+x^5}{(1-x)(1-x^2)}$.
5. Case 1: Zero $5\text{p}$ coins. We need $10$ from $1\text{p}$ and $2\text{p}$. The ways are $(10,0), (8,1), (6,2), (4,3), (2,4), (0,5)$, which is $6$ ways.
6. Case 2: One $5\text{p}$ coin. We need $5$ from $1\text{p}$ and $2\text{p}$. The ways are $(5,0), (3,1), (1,2)$, which is $3$ ways.
7. Total ways = $6 + 3 = 9$.

Answer: 9

1. Expand $(1-4x)^{1/2}$ using the binomial theorem: $1 + \frac{1}{2}(-4x) + \frac{(1/2)(-1/2)}{2}(-4x)^2 + \frac{(1/2)(-1/2)(-3/2)}{6}(-4x)^3 + \frac{(1/2)(-1/2)(-3/2)(-5/2)}{24}(-4x)^4 + \dots$
2. Simplify terms: $1 - 2x - 2x^2 - 4x^3 - 10x^4 - \dots$
3. Substitute into $C(x)$: $\frac{1 - (1 - 2x - 2x^2 - 4x^3 - 10x^4 - \dots)}{2x} = \frac{2x + 2x^2 + 4x^3 + 10x^4 + \dots}{2x}$
4. Divide by $2x$: $1 + 1x + 2x^2 + 5x^3 + \dots$
5. The coefficient of $x^3$ is 5.

Answer: 5

1. Start with $C(x) = \frac{1 - \sqrt{1-4x}}{2x}$.
2. Compute $C(x)^2 = \frac{(1 - \sqrt{1-4x})^2}{4x^2} = \frac{1 + (1-4x) - 2\sqrt{1-4x}}{4x^2} = \frac{2 - 4x - 2\sqrt{1-4x}}{4x^2}$.
3. Multiply by $x$: $x C(x)^2 = \frac{2 - 4x - 2\sqrt{1-4x}}{4x} = \frac{1 - 2x - \sqrt{1-4x}}{2x}$.
4. Add 1: $1 + x C(x)^2 = \frac{2x + 1 - 2x - \sqrt{1-4x}}{2x} = \frac{1 - \sqrt{1-4x}}{2x}$.
5. This is exactly $C(x)$.

Answer: The identity holds.

1. The function $C(x) = \frac{1 - \sqrt{1-4x}}{2x}$ has a singularity where the square root argument is zero: $1-4x = 0$.
2. Solving for $x$ gives $x = 1/4$.
3. The radius of convergence is $R = 1/4$.
4. By the root test, $\limsup_{n \to \infty} (C_n)^{1/n} = 1/R = 4$.
5. This implies that the Catalan numbers grow roughly as $4^n$.

Answer: R = 1/4; the sequence grows exponentially as 4^n.

1. The E G F for $A$ (odd counts) is $\sinh(x) = \frac{e^x - e^{-x}}{2}$.
2. The E G F for $B$ (any count) is $e^x$.
3. The total E G F is $E(x) = \frac{e^x - e^{-x}}{2} e^x = \frac{e^{2x} - 1}{2}$.
4. The coefficient of $x^n/n!$ in $e^{2x}$ is $2^n$.
5. The coefficient of $x^n/n!$ in $1$ is $1$ if $n=0$ and $0$ otherwise.
6. For $n > 0$, the number of strings is $\frac{2^n}{2} = 2^{n-1}$.

Answer: 2^{n-1} \text{ for } n > 0

1. We know $e^x = \sum \frac{x^n}{n!}$.
2. Differentiating once gives $e^x = \sum \frac{n x^{n-1}}{n!}$.
3. Multiplying by $x$ gives $x e^x = \sum \frac{n x^n}{n!}$.
4. Differentiating again gives $(1+x)e^x = \sum \frac{n^2 x^{n-1}}{n!}$.
5. Multiplying by $x$ again gives $(x+x^2)e^x = \sum \frac{n^2 x^n}{n!}$.

Answer: (x + x^2)e^x

1. The E G F for $A$ is $\cosh(x) = \frac{e^x + e^{-x}}{2}$.
2. The E G F for $B$ is $\cosh(x) = \frac{e^x + e^{-x}}{2}$.
3. The E G F for $C$ is $e^x$.
4. The total E G F is $E(x) = \frac{(e^x + e^{-x})^2}{4} e^x = \frac{e^{2x} + 2 + e^{-2x}}{4} e^x$.
5. Simplify: $E(x) = \frac{1}{4}(e^{3x} + 2e^x + e^{-x})$.
6. Extract the coefficient of $x^n/n!$: $a_n = \frac{3^n + 2(1)^n + (-1)^n}{4}$.

Answer: \frac{3^n + 2 + (-1)^n}{4}

1. Identify $a = 4$, $b = 2$, and $f(n) = n$.
2. Compute the critical value: $n^{\log_2 4} = n^2$.
3. Compare $f(n) = n$ with $n^2$. Since $n$ is polynomially smaller than $n^2$ (e.g., $\epsilon = 1$), this is Case 1.
4. The growth rate is $n^2$.

Answer: n^2

1. Identify $a = 7$, $b = 2$, and $f(n) = n^2$.
2. Compute the critical value: $n^{\log_2 7} \approx n^{2.81}$.
3. Compare $f(n) = n^2$ with $n^{2.81}$. Since $n^2$ is polynomially smaller than $n^{2.81}$, this is Case 1.
4. The growth rate is $n^{\log_2 7}$.

Answer: n^{\log_2 7}

1. Identify $a = 2$, $b = 2$, and $f(n) = n \log n$.
2. Compute the critical value: $n^{\log_2 2} = n$.
3. Compare $f(n) = n \log n$ with $n$. $f(n)$ is larger, but not polynomially larger (the difference is only a $\log n$ factor).
4. Because there is no $\epsilon > 0$ such that $n \log n$ is at least $n^{1+\epsilon}$, Case 3 does not apply. Case 2 also does not apply because $f(n)$ is not proportional to $n$.
5. The standard Master Theorem does not apply.

Answer: The standard Master Theorem does not apply.

1. Find the homogeneous solution: $r^2 - 4r + 4 = 0$ gives a repeated root $r=2$, so $a_n^{(h)} = (A+Bn)2^n$.
2. Find a particular solution: try $a_n^{(p)} = C$. Substituting into the recurrence: $C = 4C - 4C + 3$, so $C=3$.
3. General solution: $a_n = (A+Bn)2^n + 3$.
4. Use initial conditions: $a_0 = A + 3 = 1 \implies A = -2$.
5. Use $a_1 = (A+B)2 + 3 = 2 \implies (-2+B)2 = -1 \implies B = 1.5$.
6. Final form: $a_n = (-2 + 1.5n)2^n + 3$.

Answer: a_n = (1.5n - 2)2^n + 3

1. Identify parameters: $a=2, b=4, f(n) = n^{1/2}$.
2. Compute critical value: $n^{\log_4 2} = n^{1/2}$.
3. Compare $f(n)$ and critical value: $n^{1/2}$ is exactly the same as $n^{1/2}$.
4. This is Case 2 of the Master Theorem.
5. The solution is $T(n) = \Theta(n^{1/2} \log n)$.

Answer: \Theta(\sqrt{n} \log n)

1. Divide by $n!$: $\frac{a_n}{n!} = \frac{a_{n-1}}{(n-1)!} + 1$.
2. Let $b_n = \frac{a_n}{n!}$. Then $b_n = b_{n-1} + 1$ with $b_0 = 1$.
3. This is an arithmetic progression: $b_n = b_0 + n(1) = 1 + n$.
4. Substitute back: $\frac{a_n}{n!} = n+1$.
5. Solve for $a_n$: $a_n = (n+1)n! = (n+1)!$.

Answer: a_n = (n+1)!

1. The characteristic equation is $r^2 - 4r + 4 = 0$.
2. This factors as $(r-2)^2 = 0$, so there is a repeated root $r=2$.
3. The general solution is $a_n = (A + Bn)2^n$.
4. Using $a_0 = 1$, we get $A(2^0) = 1$, so $A=1$.
5. Using $a_1 = 4$, we get $(1 + B)2^1 = 4$, which means $1+B = 2$, so $B=1$.
6. The closed form is $a_n = (1+n)2^n$.

Answer: a_n = (n+1)2^n

1. Identify $a=8, b=2, f(n)=n^2$.
2. Compute the critical value $n^{\log_b a} = n^{\log_2 8} = n^3$.
3. Compare $f(n) = n^2$ with $n^3$.
4. Since $n^2 = O(n^{3-\epsilon})$ for $\epsilon=1$, we are in Case 1.
5. The growth rate is $\Theta(n^{\log_b a})$.

Answer: T(n) = \Theta(n^3)

1. The EGF for X is $\cosh(x) = \frac{e^x + e^{-x}}{2}$.
2. The EGF for Y is $e^x$.
3. The total EGF is $E(x) = \frac{e^x + e^{-x}}{2} e^x = \frac{e^{2x} + 1}{2}$.
4. The coefficient of $\frac{x^n}{n!}$ is the $n$-th term $a_n$.
5. For $n > 0$, the constant term $1$ does not contribute, so $a_n = \frac{2^n}{2} = 2^{n-1}$.

Answer: a_n = 2^{n-1} \text{ for } n > 0

1. Check for loops: No edge is of the form $\{u, u\}$.
2. Check for multiple edges: Each pair in $E$ is unique.
3. Since there are no loops and no multiple edges, it is a simple graph.
4. Count edges for each vertex: 1 is in 2 edges, 2 is in 2 edges, 3 is in 4 edges, 4 is in 2 edges, 5 is in 2 edges.

Answer: Yes, it is a simple graph. $\text{deg}(1)=2, \text{deg}(2)=2, \text{deg}(3)=4, \text{deg}(4)=2, \text{deg}(5)=2$.

1. In-degree of $A$: Count edges where $A$ is the second element. $(C, A)$ and $(A, A)$ both end at $A$.
2. Out-degree of $A$: Count edges where $A$ is the first element. $(A, B)$ and $(A, A)$ both start at $A$.
3. The loop $(A, A)$ contributes to both.

Answer: $\text{in-deg}(A) = 2, \text{out-deg}(A) = 2$.

1. If Vertex 1 is connected to all other vertices (2, 3, and 4) in a simple graph, it must have exactly one edge to each.
2. This would give Vertex 1 a degree of 3, which matches the prompt.
3. Now check Vertex 2. It has degree 3. It is already connected to Vertex 1. It needs 2 more edges.
4. The only remaining vertices are 3 and 4. If it connects to both, it reaches degree 3.
5. Now check Vertex 3. It is connected to 1 and 2. Its degree is now 2. It cannot have any more edges.
6. Now check Vertex 4. It is connected to 1 and 2. Its degree is now 2. It cannot have any more edges.
7. This configuration satisfies all degree requirements without loops or multiple edges.

Answer: Yes, it is possible.

1. First, check the number of odd-degree vertices. The degrees are $3$ and $3$, so there are $2$ odd-degree vertices. Since $2$ is even, the parity condition is satisfied.
2. Next, calculate the sum of degrees: $4 + 4 + 3 + 3 + 2 + 2 = 18$.
3. Apply the Handshake Lemma: $2|E| = 18$, which means $|E| = 9$.
4. Since the sum is even and the number of odd vertices is even, such a graph can exist.

Answer: Yes

1. Total sum of degrees is $2 \times |E| = 2 \times 15 = 30$.
2. The sum of degrees for the first $5$ vertices is $5 \times 4 = 20$.
3. The remaining sum for the other $5$ vertices is $30 - 20 = 10$.
4. The average degree of the remaining $5$ vertices is $10 / 5 = 2$.

Answer: 2

1. Represent the group as a graph where vertices are people and edges are handshakes.
2. The number of handshakes a person has made is the degree of their vertex.
3. By the Handshake Lemma, $\sum \text{deg}(v) = 2|E|$, so the total sum of degrees is even.
4. The sum of degrees of even-degree vertices is always even.
5. Therefore, the sum of degrees of odd-degree vertices must also be even to keep the total sum even.
6. A sum of odd numbers is even if and only if there is an even number of terms.

Answer: The number of odd-degree vertices must be even.

1. Identify the sizes of the two vertex sets: $m = 5$ and $n = 7$.
2. Use the formula for edges in a complete bipartite graph: $|E| = m \times n$.
3. Compute $5 \times 7 = 35$.

Answer: 35

1. The number of vertices in $Q_n$ is $2^n$. For $n=4$, $|V| = 2^4 = 16$.
2. The degree of every vertex in $Q_n$ is $n$. For $n=4$, $\text{deg}(v) = 4$.

Answer: 16 vertices, degree 4

1. Using the combination formula: $|E| = \binom{8}{2} = \frac{8 \times 7}{2} = 28$.
2. Using the Handshake Lemma: each of the 8 vertices has degree $8-1 = 7$.
3. Sum of degrees is $8 \times 7 = 56$.
4. Number of edges is $56 / 2 = 28$.

Answer: 28

1. Step 1: Count vertices and edges. Both have 5 vertices and 6 edges.
2. Step 2: Compute degree sequences. In $G_1$, vertex 1 has degree 3, vertex 3 has degree 3, and others have degree 2. Sequence: $(3,3,2,2,2)$. In $G_2$, vertex A has degree 3, vertex C has degree 3, and others have degree 2. Sequence: $(3,3,2,2,2)$.
3. Step 3: Try a mapping. Map $1 \to A, 3 \to C, 2 \to B, 4 \to D, 5 \to E$.
4. Step 4: Check edges. $(1,2) \to (A,B)$, $(2,3) \to (B,C)$, $(3,4) \to (C,D)$, $(4,5) \to (D,E)$, $(5,1) \to (E,A)$, $(1,3) \to (A,C)$. All edges match.

Answer: Yes, they are isomorphic.

1. Step 1: Check basic invariants. Both have 6 vertices and the same degree sequence.
2. Step 2: Check connectivity. Connectivity is a graph invariant.
3. Step 3: Since $G_1$ is connected and $G_2$ is disconnected, they cannot be isomorphic.

Answer: No, they are not isomorphic.

1. Step 1: Check degree sequences. Both have all vertices of degree 2.
2. Step 2: Look for the smallest cycle (the girth).
3. Step 3: In $G_1$, the smallest cycle is of length 6.
4. Step 4: In $G_2$, the smallest cycle is of length 3.
5. Step 5: Since the length of the shortest cycle is an invariant and they differ, the graphs are not isomorphic.

Answer: Not isomorphic because $G_2$ contains $C_3$ while $G_1$ does not.

1. The adjacency matrix $A$ has $A_{12}=A_{21}=A_{23}=A_{32}=A_{34}=A_{43}=A_{41}=A_{14}=1$, and all other entries $0$.
2. Compute $A^2$: the diagonal entries are the degrees, so $(A^2)_{ii} = 2$. The off-diagonal entries $(A^2)_{13} = A_{12}A_{23} + A_{14}A_{43} = 1+1 = 2$.
3. Compute $(A^3)_{11}$ as the dot product of row 1 of $A^2$ and column 1 of $A$. Row 1 of $A^2$ is $[2, 0, 2, 0]$. Column 1 of $A$ is $[0, 1, 0, 1]^T$.
4. The dot product is $2(0) + 0(1) + 2(0) + 0(1) = 0$.

Answer: 0

1. A walk of length 2 from $v_i$ to $v_j$ is a sequence $v_i \to v_m \to v_j$.
2. This walk exists if and only if $v_m$ is adjacent to both $v_i$ and $v_j$.
3. Such a vertex $v_m$ is by definition a common neighbor of $v_i$ and $v_j$.
4. The number of such walks is the number of such vertices $v_m$.

Answer: The number of walks is exactly the number of common neighbors.

1. We know that $(A^2)_{ii} = \text{deg}(v_i)$.
2. The trace of $A^2$ is the sum of the degrees of all vertices: $\text{tr}(A^2) = \sum \text{deg}(v_i)$.
3. For a 3-regular graph with $n$ vertices, every vertex has degree 3, so $\text{tr}(A^2) = 3n$.
4. Setting $3n = 21$ gives $n = 7$.

Answer: 7

1. Start at vertex 1. It is connected to 2, and 2 is connected to 3. This forms the first component: $\{1, 2, 3\}$.
2. Look for unvisited vertices. Vertex 4 is unvisited. It is connected to 5. This forms the second component: $\{4, 5\}$.
3. All vertices are now visited.

Answer: 2 components: $\{1, 2, 3\}$ and $\{4, 5\}$

1. Use the formula $|E| \ge n - k$, where $n$ is the number of vertices and $k$ is the number of components.
2. Substitute the known values: $8 \ge 12 - k$.
3. Rearrange the inequality to solve for $k$: $k \ge 12 - 8$.
4. This gives $k \ge 4$.

Answer: 4

1. Let $u$ be a vertex in $G_1$ and $v$ be a vertex in $G_2$.
2. By the definition of disjoint union, there are no edges in $G$ that connect a vertex in $G_1$ to a vertex in $G_2$.
3. Since any path from $u$ to $v$ would require at least one edge crossing from $G_1$ to $G_2$, no such path exists.
4. Because there exists at least one pair of vertices $(u, v)$ with no path between them, $G$ is disconnected by definition.

Answer: The absence of edges between $G_1$ and $G_2$ ensures no path exists between their vertices.

1. Check the degrees of all vertices: 2, 4, 2, 2, 2.
2. Observe that every single degree is an even number.
3. According to the theorem, if all vertices in a connected graph have even degrees, an Eulerian circuit exists.
4. Since every Eulerian circuit is also an Eulerian path, both exist.

Answer: Yes to both.

1. Count the number of odd-degree vertices.
2. The vertices with degree 3 are odd. There are 4 such vertices.
3. The theorem states an Eulerian path exists if and only if there are 0 or 2 odd-degree vertices.
4. Since there are 4 odd-degree vertices, no Eulerian path exists.

Answer: No.

1. In a complete graph $K_n$, every vertex is connected to every other vertex, so $\deg(v) = n - 1$.
2. For $K_5$, $n = 5$, so $\deg(v) = 5 - 1 = 4$ for all vertices.
3. Since all vertices have a degree of 4, which is even, and the graph is connected, it satisfies the condition for an Eulerian circuit.

Answer: Yes, because all vertices have degree 4.

1. Identify $n = 7$.
2. Calculate the Dirac threshold: $n/2 = 7/2 = 3.5$.
3. Check if the minimum degree $\delta(G) \ge 3.5$.
4. Since $4 \ge 3.5$, the condition is satisfied.

Answer: Yes, it must contain a Hamiltonian cycle.

1. For $C_5$, $n = 5$.
2. The degree of every vertex is $2$.
3. The Dirac threshold is $5/2 = 2.5$.
4. Since $2 < 2.5$, Dirac's theorem does not apply.
5. However, by definition, a cycle graph $C_n$ is its own Hamiltonian cycle.

Answer: It does not satisfy Dirac's theorem, but it is still Hamiltonian.

1. A Hamiltonian cycle must enter and leave every vertex using two distinct edges.
2. This means every vertex in a Hamiltonian cycle must have a degree of at least $2$.
3. Since one vertex has degree $1$, it is impossible to enter and leave it without reusing an edge or vertex.
4. Therefore, no Hamiltonian cycle can exist.

Answer: No, because a vertex of degree $1$ cannot be part of a cycle.

1. Step 1: Identify the number of vertices $n = 6$.
2. Step 2: Identify the number of edges $|E| = 5$.
3. Step 3: Check the condition $|E| = n - 1$. Here, $5 = 6 - 1$, which is true.
4. Step 4: Since the graph is connected and has $n - 1$ edges, it satisfies one of the equivalent definitions of a tree.

Answer: Yes, it is a tree.

1. Step 1: A graph with $n$ vertices and $k$ connected components has at least $n - k$ edges.
2. Step 2: For an acyclic graph, the number of edges is exactly $n - k$.
3. Step 3: We are given $|E| = n - 1$.
4. Step 4: Setting $n - k = n - 1$ gives $k = 1$.
5. Step 5: Since there is only one connected component, the graph is connected.

Answer: The graph is connected because $k=1$.

1. Step 1: Since $G$ is a tree, there exists a unique path $P$ between $u$ and $v$.
2. Step 2: Adding the edge $(u, v)$ creates a cycle consisting of the path $P$ and the new edge $(u, v)$.
3. Step 3: If there were a second cycle, there would have to be another path between $u$ and $v$ in the original tree.
4. Step 4: But the path in a tree is unique, so only one cycle can be formed.

Answer: The unique path $P$ plus the new edge forms the only possible cycle.

1. Smallest leaf is 1, neighbour is 2. Sequence: (2), Tree: {2,3,4,5,6}
2. Smallest leaf is 2, neighbour is 3. Sequence: (2,3), Tree: {3,4,5,6}
3. Smallest leaf is 3, neighbour is 4. Sequence: (2,3,4), Tree: {4,5,6}
4. Smallest leaf is 4, neighbour is 5. Sequence: (2,3,4,5), Tree: {5,6}
5. Stop when 2 vertices remain.

Answer: (2, 3, 4, 5)

1. Use Cayley's formula $T_n = n^{n-2}$
2. Substitute $n = 6$
3. Compute $6^{6-2} = 6^4$
4. $6^4 = 1296$

Answer: 1296

1. Use the property that the number of occurrences of vertex $v$ in the sequence is $\deg(v) - 1$.
2. Vertex 3 appears 2 times in the sequence $(3, 3, 1)$.
3. Set $2 = \deg(3) - 1$.
4. Solve for $\deg(3) = 3$.

Answer: 3

1. Sort edges: $(2,3,1), (4,5,1), (1,2,2), (1,3,3), (2,4,4), (3,4,5)$.
2. Pick $(2,3,1)$. Total weight = 1.
3. Pick $(4,5,1)$. Total weight = 2.
4. Pick $(1,2,2)$. Total weight = 4.
5. Check $(1,3,3)$: adding it creates cycle $(1,2,3)$. Discard.
6. Pick $(2,4,4)$. Total weight = 8. All vertices connected.

Answer: 8

1. Any spanning tree of a graph with $n$ vertices must have exactly $n-1$ edges.
2. Since all edges have the same weight $k$, every spanning tree has the same total weight.
3. The total weight is the number of edges multiplied by the weight per edge.

Answer: (n-1)k

1. Let the new edge be $e$ with weight $w(e) < w(e')$ for all $e' \in MST$.
2. Adding $e$ to the MST creates a cycle $C$.
3. Since $e$ is the lightest edge in the graph, it must be the lightest edge in $C$.
4. Removing any other edge $f$ from $C$ results in a new spanning tree with weight $W(MST) - w(f) + w(e)$.
5. Since $w(e) < w(f)$, the total weight decreases, so the MST must change to include $e$.

Answer: Yes, the MST will change to include the new edge.

1. Start at 1: $d(1)=0$, others $\infty$. Relax neighbors: $d(2)=10, d(3)=3$.
2. Visit 3 (min distance 3): Relax neighbors: $d(2)=\min(10, 3+4)=7, d(4)=\min(\infty, 3+8)=11, d(5)=\min(\infty, 3+2)=5$.
3. Visit 5 (min distance 5): Relax neighbors: $d(4)=\min(11, 5+4)=9$.
4. Visit 2 (min distance 7): Relax neighbors: $d(4)=\min(9, 7+2)=9$.
5. Visit 4 (min distance 9): No unvisited neighbors.

Answer: 9

1. From the distances in Problem 1, $d(4)=9$.
2. Check predecessors: $d(4)$ was reached via vertex 5 ($5+4=9$) or vertex 2 ($7+2=9$).
3. If via 2: $d(2)=7$ was reached via vertex 3 ($3+4=7$). $d(3)=3$ was reached via vertex 1.
4. Path 1: $1 \to 3 \to 2 \to 4$.
5. If via 5: $d(5)=5$ was reached via vertex 3 ($3+2=5$). $d(3)=3$ was reached via vertex 1.
6. Path 2: $1 \to 3 \to 5 \to 4$.

Answer: 1 \to 3 \to 2 \to 4 \text{ or } 1 \to 3 \to 5 \to 4

1. Dijkstra's algorithm assumes that once a vertex $u$ is visited, its distance $d(u)$ is the absolute minimum.
2. If there is a negative edge later in the graph, a path with more edges could potentially have a lower total weight than the current minimum.
3. Because Dijkstra's never revisits a 'visited' vertex to update its distance, it will miss any improvements offered by negative edges encountered after the vertex was locked in.

Answer: The greedy assumption that visited vertices have finalized distances is violated by negative weights.

1. Start at node $1$. Mark $1$ as visited. Queue: $[1]$.
2. Pop $1$. Neighbors are $2$ and $3$. Add them to queue. Queue: $[2, 3]$. Visited: $\{1, 2, 3\}$.
3. Pop $2$. Neighbor is $4$. Add to queue. Queue: $[3, 4]$. Visited: $\{1, 2, 3, 4\}$.
4. Pop $3$. Neighbors are $4$ and $5$. $4$ is visited, so add $5$. Queue: $[4, 5]$. Visited: $\{1, 2, 3, 4, 5\}$.
5. Pop $4$. No unvisited neighbors.
6. Pop $5$. No unvisited neighbors.

Answer: 1, 2, 3, 4, 5

1. Start at node $1$. Mark $1$ as visited.
2. Visit neighbor $2$. Mark $2$ as visited.
3. From $2$, visit neighbor $4$. Mark $4$ as visited.
4. From $4$, visit neighbor $3$. Mark $3$ as visited.
5. From $3$, visit neighbor $5$. Mark $5$ as visited.
6. No more unvisited neighbors; backtrack to $3$, then $4$, then $2$, then $1$.

Answer: 1, 2, 4, 3, 5

1. BFS must store the entire 'frontier' of the search. In a graph with a high branching factor, the number of nodes in the queue grows exponentially with depth.
2. DFS only needs to store the current path from the start node to the current node, plus the untried neighbors of nodes on that path.
3. Since the target is deep, BFS would likely store a massive number of nodes at intermediate levels before reaching the target.
4. DFS only stores a linear amount of data relative to the maximum depth of the graph.

Answer: DFS, because it only stores the current path (linear space) rather than the entire frontier (exponential space).

1. Sum the degrees: $3 + 3 + 3 + 2 + 2 + 1 = 14$.
2. Check if the sum is even: $14$ is even, so the handshake lemma is satisfied.
3. Calculate edges: $|E| = 14 / 2 = 7$.

Answer: Yes, it exists with 7 edges.

1. Sort edges: $(C,D,1), (A,B,2), (B,C,3), (D,A,4), (A,C,5)$.
2. Pick $(C,D,1)$.
3. Pick $(A,B,2)$.
4. Pick $(B,C,3)$. Now we have 3 edges for 4 vertices, and no cycles.
5. Total weight: $1 + 2 + 3 = 6$.

Answer: 6

1. BFS explores the graph in layers (breadth-first).
2. The first time BFS reaches node $T$, it is guaranteed to have taken the path with the minimum number of edges.
3. DFS explores as deep as possible and may find a very long path to $T$ before ever finding the shortest one.
4. Therefore, BFS is the correct choice for shortest paths in unweighted graphs.

Answer: BFS, because it explores layer by layer and guarantees the shortest path in unweighted graphs.

1. Use Euler's formula for connected planar graphs: $V - E + F = 2$.
2. Substitute the given values: $12 - 20 + F = 2$.
3. Simplify the left side: $-8 + F = 2$.
4. Solve for $F$: $F = 2 + 8 = 10$.

Answer: 10

1. Use the generalized Euler's formula for $C$ components: $V - E + F = 1 + C$.
2. Substitute the values: $15 - 12 + F = 1 + 3$.
3. Simplify: $3 + F = 4$.
4. Solve for $F$: $F = 4 - 3 = 1$.

Answer: 1

1. Use Euler's formula for connected planar graphs: $V - E + F = 2$.
2. Substitute the given values: $8 - E + 6 = 2$.
3. Simplify the left side: $14 - E = 2$.
4. Solve for $E$: $E = 14 - 2 = 12$.

Answer: 12

1. Identify the graph as bipartite, so use the inequality $E \le 2V - 4$.
2. Substitute the values: $13 \le 2(8) - 4$.
3. Calculate the right side: $2(8) - 4 = 16 - 4 = 12$.
4. Check the inequality: $13 \le 12$ is false.

Answer: No, it cannot be planar.

1. Use the general planar inequality $E \le 3V - 6$.
2. Substitute the values: $13 \le 3(6) - 6$.
3. Calculate the right side: $18 - 6 = 12$.
4. Check the inequality: $13 \le 12$ is false.

Answer: The graph is non-planar because it exceeds the maximum number of edges allowed for a planar graph with 6 vertices.

1. Use the bipartite planar inequality $E \le 2V - 4$.
2. Substitute $V = 10$: $E \le 2(10) - 4$.
3. Calculate: $E \le 20 - 4 = 16$.

Answer: 16 edges

1. Use the formula $\frac{1}{m} + \frac{1}{n} - \frac{1}{2} = \frac{1}{E}$.
2. Substitute $n=3$ and $m=4$: $\frac{1}{4} + \frac{1}{3} - \frac{1}{2} = \frac{3+4-6}{12} = \frac{1}{12}$.
3. Thus, $E = 12$.
4. Use $mV = 2E$: $4V = 24 \implies V = 6$.
5. Use $nF = 2E$: $3F = 24 \implies F = 8$.

Answer: V=6, E=12, F=8

1. Check the condition $\frac{1}{m} + \frac{1}{n} > \frac{1}{2}$.
2. Substitute $n=5$ and $m=4$: $\frac{1}{4} + \frac{1}{5} = \frac{5+4}{20} = \frac{9}{20}$.
3. Compare $\frac{9}{20}$ to $\frac{1}{2}$. Since $\frac{1}{2} = \frac{10}{20}$, we see that $\frac{9}{20} < \frac{10}{20}$.
4. The inequality is not satisfied, so such a solid cannot exist.

Answer: The sum of reciprocals is $9/20$, which is less than $1/2$.

1. Use Euler's formula: $20 - E + 12 = 2 \implies 32 - E = 2 \implies E = 30$.
2. Use $nF = 2E$: $n(12) = 60 \implies n = 5$.
3. Use $mV = 2E$: $m(20) = 60 \implies m = 3$.

Answer: E=30, n=5, m=3

1. The graph contains a triangle ($K_3$), so $\omega(G) = 3$, meaning $\chi(G) \ge 3$.
2. We attempt to colour the graph with 3 colours.
3. The triangle vertices must be colours 1, 2, and 3.
4. The remaining two vertices can be coloured using these 3 colours without conflict.
5. Since a 3-colouring exists and $\chi(G) \ge 3$, the answer is 3.

Answer: 3

1. Represent projects as vertices and conflicts as edges.
2. Vertices {1,2,3} form a $K_3$, so $\chi(G) \ge 3$.
3. Vertices {4,5,6} also form a $K_3$, so $\chi(G) \ge 3$.
4. Colour {1,2,3} with {Red, Blue, Green}.
5. Vertex 4 is connected to 3 (Green), so 4 can be Red.
6. Vertices 5 and 6 are connected to 4 (Red) and each other, so they can be Blue and Green.
7. A 3-colouring is possible.

Answer: 3

1. Assume $G$ has a proper 2-colouring using colours {1, 2}.
2. In any path, the colours must alternate: 1, 2, 1, 2, ...
3. In a cycle of length $k$, the $k$-th vertex is connected to the 1st vertex.
4. If $k$ is odd, the $k$-th vertex will have the same colour as the 1st vertex (both colour 1).
5. This creates a conflict, meaning the colouring is not proper.
6. Therefore, a 2-colourable graph can only have even cycles.

Answer: A 2-colourable graph is bipartite, and bipartite graphs contain no odd cycles.

1. Vertex 1 is coloured 1.
2. Vertex 2 is adjacent to 1, so it is coloured 2.
3. Vertex 3 is adjacent to 2, so it is coloured 1.
4. Vertex 4 is adjacent to 3, so it is coloured 2.
5. Vertex 5 is adjacent to 4 (colour 2) and 1 (colour 1), so it must be coloured 3.

Answer: 3

1. Brooks' theorem states that $\chi(G) \le \Delta(G)$ unless $G$ is a complete graph or an odd cycle.
2. We are given $\Delta(G) = 4$.
3. Since $G$ is neither $K_5$ nor an odd cycle, the bound $\chi(G) \le 4$ applies.

Answer: 4

1. The general greedy bound is $\Delta(G) + 1 = 10 + 1 = 11$.
2. By definition, a bipartite graph can be coloured with 2 colours, so $\chi(G) = 2$.
3. The difference is $11 - 2 = 9$.

Answer: 9

1. Since $G$ contains $K_4$, we know $\chi(G) \ge \chi(K_4) = 4$.
2. Since $G$ is planar, the Four Colour Theorem states $\chi(G) \le 4$.
3. Therefore, $\chi(G)$ must be exactly 4.

Answer: Minimum 4, Maximum 4

1. The theorem specifically applies to planar graphs.
2. If point-contacts are edges, the resulting graph may no longer be planar (edges may cross).
3. For non-planar graphs, the chromatic number can be arbitrarily large (e.g., $K_n$ requires $n$ colours).

Answer: The resulting graph may be non-planar.

1. If every region shares a border with every other, the corresponding graph is $K_5$.
2. We know from a previous lesson that $K_5$ is non-planar.
3. Since the graph is non-planar, the map cannot be drawn on a flat plane without borders crossing or regions being disconnected.

Answer: No, because it would require a $K_5$ graph, which is non-planar.

1. The vertices $v, v_1, v_3$ and the path in $H(\text{Red}, \text{Green})$ between $v_1$ and $v_3$ form a cycle $C$.
2. Because the graph is planar, this cycle $C$ divides the plane into an interior and an exterior.
3. Vertex $v_2$ is on one side of the cycle $C$, and vertex $v_4$ is on the other side.
4. Any path from $v_2$ to $v_4$ must cross the cycle $C$.
5. The cycle $C$ consists only of vertices coloured Red or Green.
6. A path in $H(\text{Blue}, \text{Yellow})$ can only contain vertices coloured Blue or Yellow.
7. Therefore, no such path can cross the cycle $C$, meaning $v_2$ and $v_4$ are not connected in $H(\text{Blue}, \text{Yellow})$.

Answer: The red-green path forms a topological barrier that separates the blue and yellow neighbours.

1. A graph with $n$ vertices can be coloured with $n$ colours by giving each vertex a unique colour.
2. If $n \le 5$, then $n$ colours are at most 5 colours.
3. Since we are proving that 5 colours are always sufficient, any graph with 5 or fewer vertices is trivially 5-colourable.

Answer: Because any graph with $n$ vertices is $n$-colourable, and for $n \le 5$, $n \le 5$.

1. The Kempe chain argument relies on the fact that if $v_1$ and $v_3$ are connected by a red-green path, then $v_2$ and $v_4$ cannot be connected by a blue-yellow path.
2. This relies on the Jordan Curve Theorem, which states that a simple closed curve divides the plane into two regions.
3. In a non-planar graph, edges can 'jump' over each other without intersecting.
4. Therefore, a red-green path between $v_1$ and $v_3$ does not necessarily block a blue-yellow path between $v_2$ and $v_4$.
5. If both pairs are connected, no single swap of two colours can free up a colour for $v$.

Answer: Without planarity, the red-green chain does not act as a barrier to the blue-yellow chain.

1. Check subsets of size 1: all have size $\ge 1$.
2. Check subsets of size 2: any pair has at least 2 elements.
3. Check subset $A = \{S_1, S_2, S_3\}$: $N(A) = \{a, b, c\}$, size 3 $\ge 3$.
4. Check subset $A = \{S_1, S_2, S_3, S_4\}$: $N(A) = \{a, b, c\}$, size 3 < 4.

Answer: No, because the union of all four sets only contains 3 elements, violating Hall's condition for the set of all four sets.

1. The sum of degrees from $X$ is at least $5 \times 3 = 15$.
2. The sum of degrees from $Y$ is at most $5 \times 3 = 15$.
3. For these to be equal, every vertex in $X$ must have degree exactly 3 and every vertex in $Y$ must have degree exactly 3.
4. Thus the graph is 3-regular. In a 3-regular bipartite graph, for any $A \subseteq X$, the number of edges leaving $A$ is $3|A|$.
5. These edges must end in $N(A)$. Since each vertex in $N(A)$ has degree 3, the number of edges entering $N(A)$ is at most $3|N(A)|$.
6. Thus $3|A| \le 3|N(A)|$, which implies $|A| \le |N(A)|$.

Answer: Yes, it must have a perfect matching because it is a 3-regular bipartite graph.

1. To prove a perfect matching exists, we check Hall's condition for any $A \subseteq X$.
2. The number of edges incident to $A$ is exactly $3|A|$ because the graph is 3-regular.
3. All these edges are incident to vertices in $N(A)$.
4. Since each vertex in $N(A)$ has degree 3, the total number of edges incident to $N(A)$ is $3|N(A)|$.
5. Therefore, $3|A| \le 3|N(A)|$, which simplifies to $|A| \le |N(A)|$.
6. Since Hall's condition is satisfied for all $A \subseteq X$, a matching saturating $X$ exists. Since $|X|=|Y|$, this is a perfect matching.

Answer: A perfect matching exists because the 3-regularity ensures $|N(A)| \ge |A|$ for all $A \subseteq X$.

1. Step 1: $P_1$ proposes to $A$. $A$ is free, so $(P_1, A)$ is a tentative match.
2. Step 2: $P_2$ proposes to $A$. $A$ compares $P_2$ to $P_1$. Since $A$ prefers $P_2$, $A$ dumps $P_1$ and accepts $P_2$.
3. Step 3: $P_1$ is now unmatched. $P_1$ proposes to their next choice, $B$. $B$ is free, so $(P_1, B)$ is a tentative match.
4. Step 4: All proposers are matched. The algorithm terminates.
5. Step 5: Check for blocking pairs. $P_1$ is with $B$ (second choice), but $A$ prefers $P_2$ (current partner) over $P_1$. $P_2$ is with $A$ (first choice). No blocking pairs exist.

Answer: \{(P_1, B), (P_2, A)\}

1. Step 1: Consider $P_1: [A, B], P_2: [B, A]$ and $A: [P_2, P_1], B: [P_1, P_2]$.
2. Step 2: Proposer-optimal: $P_1$ proposes to $A$ (accepted), $P_2$ proposes to $B$ (accepted). Result: $(P_1, A), (P_2, B)$.
3. Step 3: Acceptor-optimal: $A$ proposes to $P_2$ (accepted), $B$ proposes to $P_1$ (accepted). Result: $(P_2, A), (P_1, B)$.
4. Step 4: The results are different, showing that the matching depends on who proposes.

Answer: No, the matching can change depending on who proposes.

1. Step 1: Let $M$ be a stable matching where proposer $P$ is matched with their first choice $A$.
2. Step 2: Let $M_{opt}$ be the proposer-optimal stable matching produced by Gale-Shapley.
3. Step 3: The proposer-optimal property states that for every proposer $P$, the partner they are matched with in $M_{opt}$ is at least as preferred as the partner they are matched with in any other stable matching $M$.
4. Step 4: Since $A$ is $P$'s first choice, no partner can be more preferred than $A$.
5. Step 5: Therefore, $P$ must be matched with $A$ in $M_{opt}$ to satisfy the proposer-optimal property.

Answer: By the proposer-optimal property, the partner in the Gale-Shapley matching is the best possible partner across all stable matchings; since the first choice is the absolute best, it must be the partner in the optimal matching.

1. Path $s \to A \to t$ can take $\min(10, 8) = 8$ units.
2. Path $s \to B \to t$ can take $\min(5, 7) = 5$ units.
3. Remaining capacity $c(s, A)=2, c(s, B)=0, c(A, B)=2, c(A, t)=0, c(B, t)=2$.
4. Path $s \to A \to B \to t$ can take $\min(2, 2, 2) = 2$ units.
5. Total flow is $8 + 5 + 2 = 15$.
6. Check cut $S=\{s, A, B\}, T=\{t\}$: capacity is $c(A, t) + c(B, t) = 8 + 7 = 15$.

Answer: 15

1. According to the Max-Flow Min-Cut Theorem, the maximum flow value is exactly equal to the capacity of the minimum cut.
2. Since the minimum cut capacity is given as 12, the max flow must also be 12.

Answer: 12

1. Path $s \to A \to t$ takes 5 units.
2. Path $s \to B \to t$ takes 5 units.
3. Total flow is 10.
4. Check cut $S=\{s, A, B\}, T=\{t\}$: capacity is $c(A, t) + c(B, t) = 5 + 5 = 10$.
5. Since flow equals cut capacity, the max flow is 10.

Answer: 10

1. Apply the recursive formula: $R(3, 5) \le R(2, 5) + R(3, 4)$.
2. Substitute the given values: $R(3, 5) \le 5 + 9$.
3. Calculate the sum: $5 + 9 = 14$.

Answer: 14

1. Consider a complete graph $K_s$.
2. If any edge is coloured red, we have a monochromatic $K_2$ in red, satisfying the condition.
3. If no edges are coloured red, then all edges must be blue.
4. Since the graph is $K_s$, all edges being blue means we have a monochromatic $K_s$ in blue.
5. Thus, $s$ vertices are always sufficient. For $s-1$ vertices, we can colour all edges blue, which contains no red $K_2$ and no blue $K_s$.

Answer: R(2, s) = s

1. Model the people as vertices of a complete graph $K_6$.
2. Colour an edge red if two people know each other, and blue if they are strangers.
3. The problem is equivalent to finding a monochromatic $K_3$ in a 2-coloured $K_6$.
4. Since $R(3, 3) = 6$, any 2-colouring of $K_6$ must contain a monochromatic $K_3$.
5. Therefore, there must be a red triangle (3 mutual acquaintances) or a blue triangle (3 mutual strangers).

Answer: Proven by R(3, 3) = 6

1. Sum the degrees: $3 + 3 + 4 + 4 + 2 + 2 = 18$.
2. Apply the handshake lemma: $2|E| = 18$.
3. Divide by 2 to find $|E| = 9$.

Answer: 9

1. Use Euler's formula: $V - E + F = 2$.
2. Substitute values: $10 - 15 + F = 2$.
3. Simplify: $-5 + F = 2$.
4. Solve for $F$: $F = 7$.

Answer: 7

1. In $K_4$, every vertex is connected to every other vertex.
2. Vertex 1 gets colour 1.
3. Vertex 2 is adjacent to 1, so it gets colour 2.
4. Vertex 3 is adjacent to 1 and 2, so it gets colour 3.
5. Vertex 4 is adjacent to 1, 2, and 3, so it must get colour 4.

Answer: 4

1. For $n \ge 1$, we know $n^2 \le n^3$ and $1 \le n^3$.
2. Thus, $7n^3 + 12n^2 - 5 \le 7n^3 + 12n^3 + 0$.
3. This simplifies to $19n^3$.
4. We can choose $C = 19$ and $n_0 = 1$.

Answer: C = 19, n_0 = 1 (or any valid pair)

1. Compute the limit $\lim_{n \to \infty} \frac{n^2 \log n}{n^3}$.
2. Simplify the expression to $\lim_{n \to \infty} \frac{\log n}{n}$.
3. Apply L'Hopital's rule: the derivative of $\log n$ is $1/n$ and the derivative of $n$ is $1$.
4. The limit is $\lim_{n \to \infty} \frac{1}{n} = 0$.
5. Since $0 < \infty$, the relation holds.

Answer: Yes, f(n) = O(n^3)

1. Consider the limit $\lim_{n \to \infty} \frac{3^n}{n^{100}}$.
2. Applying L'Hopital's rule 100 times, the denominator becomes a constant ($100!$).
3. The numerator remains a multiple of $3^n$ (specifically $(\ln 3)^{100} 3^n$).
4. The limit is $\infty$.
5. Since the limit is not finite, $3^n$ grows strictly faster than $n^{100}$.

Answer: No, f(n) is not O(n^{100})

1. The maximum number of probes is given by $\lceil \log_2 n \rceil$.
2. We check powers of two: $2^{10} = 1024$, $2^{11} = 2048$, $2^{12} = 4096$, $2^{13} = 8192$.
3. Since $8192 = 2^{13}$, the logarithm is exactly $13$.

Answer: 13

1. For linear search, the worst case is $n$ operations, which is $1,048,576$.
2. For binary search, the worst case is $\log_2 n$.
3. Since $2^{20} = 1,048,576$, the binary search takes $\log_2(2^{20}) = 20$ operations.

Answer: Linear: 1,048,576; Binary: 20

1. The lower bound for comparison sorting is proportional to $n \log_2 n$.
2. Substitute $n = 100$: $100 \times \log_2 100$.
3. Using the approximation: $100 \times 6.64 = 664$.

Answer: Approximately 664

1. Initialize $dp[0] = 0$ and all other $dp[i] = \infty$.
2. Fill the table: $dp[1]=1, dp[5]=1, dp[10]=1, dp[25]=1$.
3. For $dp[37]$, the options are $1+dp[36], 1+dp[32], 1+dp[27], 1+dp[12]$.
4. The best is $1+dp[12]$ (using a $25$c coin).
5. Since $dp[12] = 1 + dp[2] = 1 + 2 = 3$ (using a $10$c coin and two $1$c coins), the total is $1 + 3 = 4$.

Answer: 4

1. Base cases: $dp[0] = 1$ (one way to stay at the bottom), $dp[1] = 1$ (one way to take one step).
2. Recurrence: To reach step $i$, you must have come from step $i-1$ or step $i-2$. So $dp[i] = dp[i-1] + dp[i-2]$.
3. Fill the table: $dp[2] = 1+1=2$, $dp[3] = 2+1=3$, $dp[4] = 3+2=5$, $dp[5] = 5+3=8$, $dp[6] = 8+5=13$.
4. The number of ways is $13$.

Answer: 13

1. Initialize $dp[0]=0$.
2. Fill table: $dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1$.
3. Continue: $dp[5]=\min(1+dp[4], 1+dp[2], 1+dp[1]) = \min(2, 3, 2) = 2$.
4. $dp[6]=\min(1+dp[5], 1+dp[3], 1+dp[2]) = \min(3, 2, 3) = 2$ (two $3$c coins).
5. $dp[7]=\min(1+dp[6], 1+dp[4], 1+dp[3]) = \min(3, 2, 2) = 2$ (one $3$c, one $4$c).
6. $dp[8]=\min(1+dp[7], 1+dp[5], 1+dp[4]) = \min(3, 3, 2) = 2$ (two $4$c coins).
7. $dp[9]=\min(1+dp[8], 1+dp[6], 1+dp[5]) = \min(3, 3, 3) = 3$.
8. $dp[10]=\min(1+dp[9], 1+dp[7], 1+dp[6]) = \min(4, 3, 3) = 3$.
9. $dp[11]=\min(1+dp[10], 1+dp[8], 1+dp[7]) = \min(4, 3, 3) = 3$.
10. $dp[12]=\min(1+dp[11], 1+dp[9], 1+dp[8]) = \min(4, 4, 3) = 3$ (three $4$c coins).
11. $dp[13]=\min(1+dp[12], 1+dp[10], 1+dp[9]) = \min(4, 4, 4) = 4$.

Answer: 4

1. For B-F-S, the cost is $5000 + 20000 = 25000$ operations.
2. For Dijkstra's, $\log_2(5000)$ is approximately $12.28$.
3. The cost is $20000 \times 12.28 \approx 245600$ operations.

Answer: B-F-S: 25,000; Dijkstra: $\approx 245,600$

1. The general cost is $O(V + E)$.
2. Substitute $E = \frac{V^2 - V}{2}$.
3. The expression becomes $O(V + \frac{V^2 - V}{2})$, which is dominated by the $V^2$ term.

Answer: O(V^2)

1. If $E \approx V$, the second algorithm runs in $O(V \log V)$.
2. We compare $V^2$ with $V \log V$.
3. Since $\log V$ grows much slower than $V$, $V \log V$ is asymptotically smaller than $V^2$.

Answer: O(E \log V)