Skip to main content

Module Quiz

Complete this quiz after finishing all concept and practice pages.

Current Module Questions​

Question 1: Product Rule vs Case Split​

How many length-6 strings over the alphabet {A, B, C, D} contain at least one A?

Answer: 4^6 - 3^6 = 4096 - 729 = 3367.

Solution Walkthrough:

  1. Count all strings of length 6: 4^6.
  2. Count strings with no A: only {B, C, D} allowed, so 3^6.
  3. Subtract to get the complement.

Common Errors:

  • Error Pattern: Multiplying by 6 because the A could appear in six positions.
  • Why This Happens: Treating "at least one" like "exactly one."
  • Correct Approach: Complement counting avoids overlap between cases with multiple As.

Question 2: Ordered vs Unordered Choice​

A committee of 3 students and a chairperson are chosen from 10 students. How many outcomes are possible if the chairperson must be one of the committee members?

Answer: 10 * C(9,2) = 360.

Solution Walkthrough:

  1. Choose the chairperson first: 10 choices.
  2. Choose the other 2 committee members from the remaining 9: C(9,2) = 36.
  3. Multiply: 10 * 36 = 360.

Common Errors:

  • Procedural Error: Computing C(10,3) and stopping.
  • Conceptual Error: Forgetting the extra role inside the selected committee.

Question 3: Combinatorial Identity​

Give a combinatorial proof of C(n, k) = C(n, n-k).

Answer: Both expressions count the same selection from an n-element set. C(n, k) counts choosing the k selected elements. C(n, n-k) counts choosing the n-k elements left out. These determine each other uniquely.

Question 4: Inclusion-Exclusion​

In a cohort of 120 learners, 68 study Python, 54 study Linux, 49 study discrete math, 28 study Python and Linux, 23 study Python and discrete math, 17 study Linux and discrete math, and 9 study all three. How many study none of the three?

Answer: |P union L union D| = 68 + 54 + 49 - 28 - 23 - 17 + 9 = 112, so 120 - 112 = 8.

Question 5: Pigeonhole Principle​

Show that among any 11 integers, two have the same remainder when divided by 10.

Answer: There are only 10 possible remainders modulo 10. Placing 11 integers into 10 remainder classes forces at least two into the same class.

Question 6: Stars and Bars​

How many nonnegative integer solutions satisfy x1 + x2 + x3 + x4 = 12?

Answer: C(12 + 4 - 1, 4 - 1) = C(15,3) = 455.

Question 7: Recurrence Modeling​

Let a_n be the number of binary strings of length n with no consecutive 1s. Derive the recurrence and initial conditions.

Answer: a_n = a_(n-1) + a_(n-2) for n >= 2, with a_0 = 1, a_1 = 2.

Question 8: Generating Functions​

What generating function counts the number of ways to form n using any number of 1s, 2s, and 5s?

Answer: 1 / ((1-x)(1-x^2)(1-x^5)).

Question 9: Degree Sum​

A simple graph has 12 vertices, each of degree 3. How many edges does it have?

Answer: The degree sum is 12 * 3 = 36 = 2|E|, so |E| = 18.

Question 10: Trees​

Prove that every tree with at least two vertices has at least two leaves.

Answer: Take a longest simple path in the tree. Each endpoint must have degree 1, otherwise the path could be extended. So the tree has at least two leaves.

Question 11: Euler vs Hamilton​

Does the graph with vertices {A,B,C,D,E} and edges {AB, BC, CD, DE, EA, AC} have an Euler circuit, an Euler path only, or neither?

Answer: Degrees are 3,2,3,2,2. Exactly two vertices have odd degree, so the graph has an Euler path but no Euler circuit.

Question 12: Bipartite and Coloring​

Why is every bipartite graph 2-colorable?

Answer: Its vertices split into two parts with all edges crossing between the parts. Color one part with color 1 and the other with color 2.

Question 13: Planarity​

Use Euler-style edge bounds to explain why K5 is not planar.

Answer: A simple planar graph with v >= 3 satisfies e <= 3v - 6. For K5, v = 5 and e = 10, but 3v - 6 = 9, so K5 cannot be planar.

Interleaved Review Questions​

Prior Module Question 1​

What proof technique is usually cleanest for "If n^2 is odd, then n is odd"?

Answer: Contrapositive.

Prior Module Question 2​

What are the two directions needed to prove A = B by double inclusion?

Answer: Show A subseteq B and B subseteq A.

Prior Module Question 3​

When are two functions equal?

Answer: When they agree on every input from the same domain and codomain.

Prior Module Question 4​

What is the difference between symmetric and antisymmetric?

Answer: Symmetric means aRb implies bRa. Antisymmetric means if aRb and bRa, then a = b.

Prior Module Question 5​

What is the role of the inductive hypothesis?

Answer: It is the temporary assumption used to prove the next case.

Self-Assessment and Remediation​

Mastery Level (90-100% correct):

  • Ready to advance to Module 3.

Proficient Level (75-89% correct):

  • Review the specific concepts you missed and redo two similar problems for each.

Developing Level (60-74% correct):

  • Rework the counting and graph practice pages before advancing.

Insufficient Level (<60% correct):

  • Return to the concept sequence and rebuild your notes from definitions and proof patterns upward.