Listing - Handshake Problems

Listing - Handshake Problems

GCSE(F), GCSE(H),

Another type of listing involves identifying pairs of combinations: the handshake problem.

This identifies the number of times a pair of items interact. Draw up a table, with the set of items listed as both rows and as columns.

The table can identify both joint and two-way interactions. For example, a handshake with another person is a joint interaction, as Bob shaking hands with Alice is the same as Alice shaking hands with Bob. However, if Alice and Bob exchanged gifts, then both directions (Alice to Bob and Bob to Alice) need to be identified.

Sometimes items may interact with themselves (a domino can show a pair of 1s), and sometimes they may not (Bob will not shake hands with himself).

Examples

1. Take six colours - blue, red, green, orange, purple and yellow - how many combinations are there if each colour is mixed with one other colour?

Answer: 15

A colour cannot be mixed with itself. The pairs are only shown once (above the diagonal), as blue-orange is the same as orange -blue.

Paint mixing table

2. A town has eight bus terminals: Alexander, Beanhill, Churchway, Downtown, Eagleshill, Flitwick, Georgecross and Highhill. The bus routes are identified with the first letter of both the origin and destination of the route, such that Downtown to Highhill is route DH, and that the reverse direction is route HD. There are no circular routes (eg Downtown to Downtown).

How many routes are there?

Answer: 56

Handshake problem, with all combinations being two way.

8 x 8 combinations, less the 8 combinations with each other, is 64 - 8 = 56.

Route Table