Introduction to the Handshake Problem
The handshake problem is a classic puzzle in combinatorics that helps us understand how to count unique interactions within a group. It is a fundamental application of the concept of combinations.
The Concept: Combinations vs. Permutations
In this problem, we need to find the number of ways to choose 2 people out of 10 to perform an action (a handshake).
- Order does not matter: If Person A shakes hands with Person B, it is the same event as Person B shaking hands with Person A. Because order is irrelevant, we use combinations rather than permutations.
- The Formula: The number of ways to choose $k$ items from a set of $n$ items is given by the combination formula:
$$C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$$
Solving the Problem
Given:
- Total number of people ($n$) = 10
- People required for a handshake ($k$) = 2
Using the formula:
$$C(10, 2) = \frac{10!}{2!(10-2)!} = \frac{10 \times 9}{2 \times 1} = \frac{90}{2} = 45$$
Intuition through Graph Theory
Think of each person as a 'node' (vertex) in a graph. A handshake is an 'edge' connecting two nodes.
- Each of the 10 people shakes hands with 9 other people.
- This might lead you to think there are $10 \times 9 = 90$ handshakes.
- However, this double-counts every handshake (A shaking B and B shaking A are counted as two).
- Dividing by 2 corrects this double-counting, giving us the final result: 45 handshakes.