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