1.1 Introducing combinatorics with a handshake
1.1 Introducing combinatorics with a handshake
🧭 Overview
🧠 One-sentence thesis
The handshake problem demonstrates that the same counting question can be solved through multiple approaches—arithmetic reasoning, sequential counting, and visual graph modeling—all yielding the same answer and introducing core combinatorial techniques.
📌 Key points (3–5)
- The problem: five students each shake hands with all others; the goal is to count the total number of handshakes.
- Three solution methods: (1) arithmetic with double-counting correction, (2) sequential counting by student, (3) visual graph representation.
- Graph terminology: vertices represent students, edges represent handshakes, and a complete graph connects every pair of vertices.
- Common confusion: intersections of line segments in the graph drawing are not vertices—only the labeled dots representing students are vertices.
- Why it matters: this simple problem introduces counting techniques, mathematical proof approaches, and graph theory that will be extended to larger, more complex scenarios.
🔢 Three ways to count handshakes
🔢 Arithmetic with double-counting
- Each of 5 students shakes 4 hands, giving 5 times 4 equals 20.
- But each handshake involves 2 students, so we counted every handshake twice.
- Correction: divide 20 by 2 to get 10 handshakes.
- Example: when student a shakes hands with student b, that single handshake is counted once for a and once for b.
📝 Sequential counting by student
- Label the students a, b, c, d, e and count handshakes in order:
- Student a shakes hands with 4 others.
- Student b shakes hands with 3 others (excluding a, already counted).
- Student c shakes 2 more hands (excluding a and b).
- Student d shakes 1 more hand (with e).
- Student e does not need to shake any more hands (all already counted).
- Total: 1 plus 2 plus 3 plus 4 equals 10.
- This method avoids double-counting by ensuring each handshake is recorded only once.
🎨 Visual graph model
- Draw a dot for each student and a line segment connecting each pair of dots.
- Counting the line segments gives 10 handshakes.
- This visual tool is called a graph.
📊 Graph terminology and structure
📊 Basic definitions
Vertices: the dots representing the students in the graph.
Edges: the line segments between vertices representing the handshakes.
Complete graph: a graph where every two vertices are connected by an edge.
- The graph shown is called K5, the "complete graph on 5 vertices."
- Don't confuse: intersection points of line segments that are not labeled are not vertices—they should be ignored.
🔗 Why "complete"
- The graph is complete because every pair of students is connected.
- In K5, every one of the 5 vertices has an edge to every other vertex.
- This models the handshake scenario where every student shakes hands with all others.
🧩 What this problem introduces
🧩 Counting problems
- The handshake problem is a prototype for combinatorial counting.
- The excerpt states that similar questions will become more complicated when the number of students increases beyond 5.
- Example: for 101 students, the handshake count involves adding numbers from 1 to 100.
🧩 Mathematical proofs and techniques
The excerpt mentions that the class will cover:
- Basic counting, sets, and binomial coefficients.
- Advanced counting techniques including bijections, recurrence relations, and generating functions.
- Graph theory and optimization.
- Combinatorial geometry, including planar graphs and coloring problems.
🧩 Extensions of the handshake problem
The excerpt lists example questions that build on the handshake scenario:
| Topic area | Example question |
|---|---|
| Basic counting | How many ways can 5 students line up? How many ways can 3 students be chosen for a project? |
| Counting techniques | How many ways can 10 rocks be distributed among students? |
| Graph theory | How many phone calls are needed to share news? How many cables to connect 40 buildings? Can you trace the edges of K5 without lifting your pencil? |
| Combinatorial geometry | Can K5 be redrawn so edges do not intersect? How many regions can 4 students' lines divide a paper into? |
🎯 Pedagogical approach
🎯 Group work and communication
- The excerpt emphasizes that developing good communication patterns is more important at this stage than answering problems.
- A group works best if everyone speaks for about the same amount of time and questions are valued as much as answers.
- For unsolved problems, groups should decide if the question is clear or ambiguous, if all needed information is provided, and provide ideas or strategies.
🎯 Problem-solving process
The exercises ask students to:
- Introduce themselves and share why they are taking the class.
- Try to solve some problems.
- Develop strategies for approaching other problems.
- Generate ideas about more advanced problems.
- Write down explanations of answers and thought processes for solved problems.