Problem 13 - A First Course in Probability

Question

Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place?

Step-by-Step Solution

Answer

In a group of 20 people, there are \(C(20, 2) = 190\) unique handshakes that can take place, found using the combination formula.

Step 1: Understand the Problem

: We have a group of 20 people and want to find out how many unique handshakes can take place between them. Each handshake involves a pair of 2 individuals.

Step 2: Apply the Combination Formula

: We will use the combination formula to find the number of handshakes. In this case, n = 20 (total people) and k = 2 (number of people in a handshake). The formula is given as: \(C(n, k) = \frac{n!}{k!(n-k)!}\).

Step 3: Calculate Factorials

: Calculate the required factorials for the formula. We need the factorials of n (20), k (2), and (n-k) (20-2=18). \(20! = 20 \times 19 \times 18 \times ... \times 3 \times 2 \times 1\) \(2! = 2 \times 1\) \(18! = 18 \times 17 \times ... \times 3 \times 2 \times 1\)

Step 4: Plug Factorials into the Formula

: Now that we have our factorials, plug them into the combination formula: \(C(20, 2) = \frac{20!}{2!(18)!}\)

Step 5: Calculate the Number of Handshakes

: Evaluate the expression to find the number of unique handshakes between the 20 people: \(C(20, 2) = \frac{20 \times 19 \times 18 \times ... \times 3 \times 2 \times 1}{(2 \times 1)[18 \times 17 \times ... \times 3 \times 2 \times 1]}\) Observe that the terms 18! cancel out from the numerator and the denominator: \(C(20, 2) = \frac{20 \times 19}{2}\) Multiply and divide the expression: \(C(20, 2) = \frac{380}{2}\) \(C(20,2) = 190\) The number of unique handshakes between 20 people is 190.

Key Concepts

handshake problem

When 20 people are all gathered in a room and each person shakes hands with everyone else, this situation is known as the "handshake problem." It is a classic example in combinatorics, which is a branch of mathematics dealing with counting and arrangement concepts. The primary question is: how many unique handshakes take place?

Each handshake involves two distinct people. Thus, the goal is to count how many ways we can pick 2 people out of the 20 to form a handshake. Since the order in which people shake hands doesn't matter (shaking hand with John and then Paul is the same as with Paul and then John), this is essentially a combination problem.

The solution to this problem not only helps in understanding practical scenarios but also aids in grasping foundational concepts in combinatorics.

combination formula

The combination formula is pivotal in solving many counting problems, including the handshake problem. It helps in determining the number of ways to choose a subset of items from a larger set, where the order of selection doesn't matter.

This formula is represented as:

• \(C(n, k) = \frac{n!}{k!(n-k)!}\)

Where:

• \(n\) is the total number of items (people, in this case).
• \(k\) is the number of items to choose (a pair for the handshake).

In the handshake scenario, \(n\) is 20 (the total number of people), and \(k\) is 2 (since a handshake involves 2 people). Hence, we use the combination formula to determine how many pairs can be formed. This formula is essential in combinatorics for solving problems where order doesn't matter.

factorials

Understanding factorials is crucial in applying the combination formula effectively. Factorials, denoted by an exclamation mark (!), represent the product of all positive integers up to a particular number. For example,

• \(n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1\)

In the handshake calculation, we need the factorials of three numbers:

• \(20!\) for the total number of people.
• \(2!\) for the people participating in a single handshake.
• \(18!\) for the remaining people out of the 20 after selecting a pair.

Factorials grow extremely fast, making manual computation difficult for large numbers. Luckily, many calculators and mathematical software have built-in functions to compute them, easing the process of solving problems like the handshake problem.

binomial coefficient

A binomial coefficient, often represented using parentheses such as \(\binom{n}{k}\), is a numerical value that denotes the number of ways to choose \(k\) elements from a set of \(n\) elements without considering the order.

The binomial coefficient is directly related to the combination formula. It uses similar notation:

• \(\binom{n}{k} = C(n, k) = \frac{n!}{k!(n-k)!}\)

In the handshake problem, the binomial coefficient \(\binom{20}{2}\) helps to find the number of unique pairs (or handshakes) possible in a group of 20 people. It's one of the most vital concepts in combinatorics, with applications spanning algebra, calculus, and probability. Calculating the binomial coefficient gives a direct answer to the problem, showing how classical mathematical concepts are interconnected.