Assessment Solutions and Scoring

Open after an independent checkpoint attempt. Apply the per-competency rubric; alternative correct proofs and witnesses receive credit.

A1/C1: 5!/(2!2!)=30 arrangements, since permuting the two labeled A copies and the two B copies leaves each word unchanged with uniform multiplicity four. The chaired subset count is 5·C(8,5)=280, also 8·C(7,4). Explain whether the leader is one of the selected people; here it is.

A2/C2: Unrestricted C(8,2)=28. Each coordinate ≥4 contributes C(4,2)=6; two cannot both exceed the bound at total six. Count 28−18=10. If each of three boxes held at most three objects, only nine would fit, contradicting ten. The second result proves existence without counting assignments.

A3/C3: b₀=1,b₁=3; for n≥2, each valid length-(n−1) word has exactly two legal next letters. The construction is unique and exhaustive, so bₙ=2bₙ₋₁ and bₙ=3·2ⁿ⁻¹ for n≥1. At zero the separate empty word count is one, not 3/2. Available choices depend on the last letter but their number is constant.

A4/C4: Unordered OGF 1/((1−x)(1−x³)); at six, multiplicity of 3 can be 0,1,2, giving three choices. Ordered OGF 1/(1−x−x³) with t₀=1 and tₙ=tₙ₋₁+tₙ₋₃, treating negative indices as zero. Values t₀..t₆ are 1,1,1,2,3,4,6. Both constant coefficients count one empty object. Coefficients come from specified constructions, not numerical evaluation of x.

A5/C5: Degrees 1,2,2,1,0; components {0,1,2,3},{4}. Zero-step matrix is the 5×5 identity. Two two-step walks return from 1: 1–0–1 and 1–2–1. They repeat the endpoint, so they are not simple paths. C₆ and two disjoint triangles have the same degree sequence and different connectivity, disproving degree-sequence sufficiency.

A6/C6: Repeatedly delete a cycle edge while preserving connectivity; finite edge count ensures termination in a spanning tree T. A tree on n vertices has n−1 edges (prove by leaf removal). Since the original graph also had n−1, no edges could have been deleted; hence it was acyclic. If a bridge were omitted from a spanning tree, its endpoints would still have a tree path avoiding it, contradicting its bridge property. A triangle has no bridges but each spanning tree retains two edges. The finite nonempty hypothesis covers the base tree.

A7/C7: All degrees are even and all edges lie in one component, so traverse one triangle then the other for an Euler circuit. Deleting the shared vertex disconnects the remainder. A Hamilton cycle would leave a spanning path, a contradiction. Adding a separate edge component prevents a single Euler trail covering every edge. A separate isolate would not prevent edge coverage.

A8/C8: Triangle vertices must receive three distinct colors: 3!=6 choices. The isolate has any of three, giving 18 assignments. The triangle forces at least three colors, and these witnesses show three suffice. Division by k! requires uniform fibers: assignments can use fewer than k colors, so unused color permutations can fix them. This fixture uses every color, but that does not establish a general rule for arbitrary graphs and k.

A9/C9: Matching (0,10),(2,11) has size two. S={0,1} has N(S)={10}; upper bound |L|−|S|+|N(S)|=3−2+1=2 matches the construction. Add permission (1,11); now (0,10),(1,11),(2,12) saturates L. Merely finding a maximal matching or checking selected Hall subsets without a witness would leave a gap.

A10/C10: 18≤3·12−6=30 is necessary but insufficient. Take disjoint K₃,₃ and the triangular prism: each has six vertices and nine edges, so their union has exactly twelve vertices and eighteen edges and contains nonplanar K₃,₃. The prism consists of two triangles with three corresponding cross edges. Euler's formula is v−e+f=1+c for a chosen plane embedding, including its outer face. Solving for a plausible integer f assumes the embedding whose existence you were supposed to establish. A disconnected formula does not remove that assumption. An alternative example with these exact counts is equally valid.