Practice Solutions and Feedback

Use after saving an independent attempt. Equivalent correct proofs and different valid witnesses count. A numerical answer without its model is incomplete.

P1–P5: Counted objects

P1: Choose the three positions of ones: C(5,3)=10. The forward map sends a word to those positions; the inverse fills exactly those positions with ones.

P2: C(9,4)·4=504, also 9·C(8,3)=504. Both count the same chaired committee. More generally k·C(n,k)=n·C(n−1,k−1) for 1≤k≤n: mark a member or select the marked member first. The hypotheses keep the factorial expressions meaningful.

P3: Labeled groups: C(4,2)=6. Each unlabeled split has two labelings, so there are three. For necklaces, representatives 0000,0001,0011,0101,0111,1111 have orbit sizes 1,4,4,2,4,1. There are six classes, not 16/4. Division fails because representation counts differ.

P4: 50+33+20−16−10−6+3=74. An element in j selected sets contributes C(j,1)−C(j,2)+...=1 for j≥1. The complement contains 26 integers. Endpoints are inclusive; changing 1..100 to another interval requires a new count.

P5: 2³−2=6, removing the two constant maps. Each unlabeled two-block partition corresponds to 2! onto maps, so there are three such partitions. There is one empty-to-empty map; neither empty-to-nonempty nor nonempty-to-empty can be onto. The latter cannot even be total. The 0⁰ convention here counts one empty choice and is not a claim about limits in analysis.

P6–P11: Constraints, recurrence and series

P6: Unrestricted count C(9,2)=36. If x≥4, substituting x′=x−4 leaves total 3, giving C(5,2)=10; likewise for y,z. Two overflowing variables would sum to at least 8, impossible. Thus 36−30=6. Solution types are permutations of (3,3,1) and (3,2,2), three each.

P7: Twelve remainder boxes hold 13 integers, so a box contains two; their difference is divisible by 12. If each of three servers received at most two tasks, at most six tasks would be assigned, contradicting seven. Neither proof specifies the number of legal assignments or identifies a particular collision.

P8: Let aₙ count the words. For n≥2, last-bit cases contribute aₙ₋₁ and aₙ₋₂; a₀=1,a₁=2, giving 1,2,3,5,8,... . Tilings have T₀=T₁=1 and the same recurrence, so aₙ=Tₙ₊₁. Append a zero to the word, parse it uniquely into tokens 0 and 10, and replace these by tiles of lengths 1 and 2. Inverse: expand tiles to 0/10 and remove the final zero. The empty word maps to one length-one tile. Equal recurrence shape alone does not identify equal-index counts.

P9: Set bₙ=aₙ+1; then bₙ=3bₙ₋₁ and b₀=2, so aₙ=2·3ⁿ−1. At n=0 it gives 1. Substituting the preceding formula into the recurrence yields 3(2·3ⁿ⁻¹−1)+2=2·3ⁿ−1, completing induction. The characteristic method applies to the specified constant-coefficient linear family, not arbitrary recurrences.

P10: Unordered: 1+1+1+1, 1+1+2, 2+2, hence three. Ordered: 1111,112,121, 211,22, hence five. OGFs are 1/((1−x)(1−x²)) and 1/(1−x−x²) respectively. The first chooses each denomination's multiplicity; the second chooses a finite sequence of parts. Both have constant coefficient one.

P11: Coefficients are aₙ₋₁ for n≥1 (zero at n=0), sum from i=0 to n of aᵢ, and n·aₙ. In A′ alone, the coefficient of xⁿ is (n+1)aₙ₊₁: differentiation lowers size by one. For example the x⁴ coefficient of the coin product in P10 is 1+1+1 from pairs of exponents (4,0),(2,2),(0,4). No real substitution is needed.

P12–P15: Graph structure

P12: Degrees 2,2,2,0; two components; n=4,m=3. A cycle and disconnection prevent a tree despite m=n−1. C₆ and two disjoint triangles both have six degree-two vertices but different component counts, so they are not isomorphic.

P13: Zero-step matrix is the 3×3 identity. The two-step matrix has rows (1,0,1),(0,2,0),(1,0,1). The walk 1–0–1 repeats vertex 1; it is not a simple path. Matrix powers count all walks, not only vertex-distinct ones.

P14: An endpoint of a longest simple path cannot have another neighbor off the path (that extends it) or on the path other than its next vertex (that creates a cycle). Both distinct endpoints are degree-one leaves. Sum nᵢ−1 over the c tree components to obtain m=n−c; empty sums give 0=0. In a rooted two-vertex tree the root has degree one but has a child, so it is not a rooted leaf. The singleton root has no children and is a rooted leaf.

P15: MST AB,BC has total weight 4; the alternatives weigh 5. Its A-to-C path costs 4, while original edge AC costs 3. No triangle edge is a bridge, yet the spanning tree retains two of them. All original bridges must appear in every spanning tree; not every non-bridge is discarded in a particular tree.

P16–P20: Existence and impossibility

P16: Center degree 4, others degree 2, with one edge-bearing component: an Euler circuit follows one triangle then the other. Deleting the shared vertex disconnects the remaining graph. A Hamilton cycle would leave a spanning path after deleting any vertex, so none exists. An isolate leaves Euler edge coverage possible. Two disjoint triangles have even degrees but no single trail covering both components' edges.

P17: A connected even cycle has two labeled two-colorings; the isolate has either color independently, giving four. An edge requires at least two colors, and the assignments prove two suffice. A diagonal creates a triangle; alternation around an odd cycle makes a two-coloring impossible. Three colors suffice by assigning the triangle three colors and extending to the fourth vertex.

P18: Match (10,20),(12,21), size two. S={10,11} has neighborhood {20}, so at most one of those two can be matched; vertex 12 adds at most one. This upper bound two equals the witness size. Add (11,21): matching (10,20),(11,21),(12,22) saturates L. A few checked subsets would not by themselves prove Hall's condition for every subset.

P19: f=1+c−n+m=1. Joining different components adds an edge, reduces c by one and leaves f unchanged. Adding an edge within a face to close a cycle adds one edge and one face, preserving v−e+f. These operations preserve the disconnected formula; they should not be conflated with changing a connected embedding into a disconnected one.

P20: K₅ has 10>3·5−6=9 edges. K₃,₃ has 9>2·6−4=8, using its bipartite nature and n≥3. Subdividing every K₅ edge gives n=15,m=20, passing the necessary bound 20≤39. It still contains a subdivision of K₅ (itself), so Kuratowski's obstruction proves nonplanarity. Passing an inequality is not a proof that an embedding exists.