Listing - Handshake Problems

## Listing - Handshake Problems

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

This shows how pairs of items interact. Draw up a table, with the set of items listed as both rows and as columns.

Check the type of interaction. For example, a handshake with another person is a joint interaction: 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).

## Example 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?

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.

 Blue Red Green Orange Purple Yellow Blue - B-R B-G B-O B-P B-Y Red - - R-G R-O R-P R-Y Green - - - G-O G-P G-Y Orange - - - - O-P O-Y Purple - - - - - P-Y Yellow - - - - - -

## Example 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?

Handshake problem, with all combinations being two way.

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

 A B C D E F G H A - AB AC AD AE AF AG AH B BA - BC BD BE BF BG BH C CA CB - CD CE CF CG CH D DA DB DC - DE DF DG DH E EA EB EC ED - EF EG EH F FA FB FC FD FE - FG FH G GA GB GC GD GE GF - GH H HA HB HC HD HE HF HG -