Mathematical Thinking · Quiz 2 · Jan 2025

**1. Question 1 — recover the graph:** The adjacency matrix gives edges {1,2},{1,3},{2,4},{2,5}. All five vertices are connected and there are four edges, so G is a tree. A bipartition is {1,4,5} and {2,3}. Because at least one edge exists, its chromatic number is exactly 2. Every tree is planar. Therefore the true statements are (a) and (b); (c) and (d) are false. **2. Question 2 — apply Euler’s totient facts:** (a) is true: primes are unbounded, so choose p=2 and a prime q≥n+2 to get |p−q|≥n. (b) is false without coprimality: φ(2·2)=φ(4)=2, while φ(2)φ(2)=1. (c) is true because \[\phi(100)=100(1-1/2)(1-1/5)=40.\] (d) is false: φ(8)=4 is even although 8 is composite, while the prime 2 has φ(2)=1. Thus select (a),(c). **3. Question 3(a) — reconstruct the permutation:** Use the standard value-indexed inversion table: bⱼ counts entries greater than j that occur before j. Given b=(2,2,0,2,0,2,1,0), insert values from 8 down to 1, placing j after exactly bⱼ already-placed larger values. The result is \[\sigma=(3,5,1,2,8,4,7,6).\] In this permutation the counts of larger entries before values 1 through 8 are exactly 2,2,0,2,0,2,1,0, verifying the reconstruction. **4. Question 3(b) — use the derangement recurrence:** Derangements satisfy \(D_n=nD_{n-1}+(-1)^n\). Since 2025 is odd, D₂₀₂₅=2025D₂₀₂₄−1, so \[\frac{D_{2025}+1}{D_{2024}}=2025.\] **5. Question 4(a) — give an explicit graph:** Take the cycle C₅ on vertices 1,2,3,4,5 with edges 12,23,34,45,51. Every vertex has exactly two incident edges, so the required graph exists. **6. Question 4(b) — show why n−1 edges need not make a tree:** On six vertices take the disjoint union of a triangle on {1,2,3} and a path on {4,5,6}. Its edges are 12,23,31,45,56, totaling five. It is disconnected and contains a cycle, so it is not a tree despite |E|=|V|−1. **Answer: A — Q1 a,b; Q2 a,c; σ=(3,5,1,2,8,4,7,6); ratio 2025; graph examples exist.** **Convention note:** The inversion-table convention used here counts greater values before each value. If a course instead uses position-indexed counts of smaller entries to the right (Lehmer code), the same digit string decodes as (3,4,1,6,2,8,7,5). The source does not define its convention; the standard inversion-table interpretation is stated explicitly. A: **Correct:** The complete graph, totient, permutation, derangement and construction answers are provided above. B: **Incorrect:** These written questions are applicable and have substantive solutions.

**1. Question 5 — assume the contrary:** Suppose no student solved five or more problems, so each solved at most four. The students who solved exactly 1,2 and 3 problems are three distinct students. **2. Bound the total:** The other seven students could then solve at most four each. The overall number of solved problems would be at most \[1+2+3+7(4)=6+28=34,\] contradicting the given total 35. Therefore at least one student solved at least five problems. **3. Question 6(a) — fix the captain:** The designated person must be on the team and be its captain. Each of the other n−1 people is independently included or excluded, giving \[2^{n-1}\] teams with that fixed captain. Choosing no other person is allowed because a one-person team is permitted. **4. Question 6(b) — choose the captain first:** There are n captain choices. For each, the remaining membership can be chosen in 2ⁿ⁻¹ ways. Hence the number of teams-with-a-captain is n2ⁿ⁻¹. A membership set with different captains represents different teams in this counting problem. **5. Question 6(c) — count by team size:** A k-person membership set can be chosen in \(\binom nk\) ways, and then any of its k members may captain it. Its contribution is k\(\binom nk\). Summing over all permitted sizes counts the same teams as the captain-first method, proving \[\sum_{k=1}^nk\binom nk=n2^{n-1}.\] **6. Optional algebraic verification:** The identity \(k\binom nk=n\binom{n-1}{k-1}\) transforms the left side to \(n\sum_{j=0}^{n-1}\binom{n-1}j=n(1+1)^{n-1}\), agreeing with the counting proof. **Answer: A — at least one student solved ≥5; fixed-captain count 2^(n−1); total count n2^(n−1).** **Convention note:** The export stores several written subquestions under this acknowledgement option. The mathematical conclusions, not the administrative wording, are the intended solution content. A: **Correct:** The contradiction proof and all three captain/team counts are established above. B: **Incorrect:** Both written questions are applicable and have been fully answered.