The Diplomatic Puzzle

“Contrariwise,” continued Tweedledee, “if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.” Lewis Carroll, Through the Looking Glass

This logic puzzle reportedly appeared in Omni Magazine decades ago, and it’s astoundingly “impossible” because it seems to lack enough information for a solution. This deceptively simple puzzle captures the essence of the exploration of non-obvious implications; the kind of untimed reflection that allows for deep reasoning. It also unfolds in a charming, diplomatic setting where imagination gives way to cold, symmetrical logic, rich with abstract beauty! 

The Diplomatic Puzzle: A Handshake Puzzle

During an International Summit, each of the Commissioners and the accompanying Delegates from the 27 member countries took part in the inaugural session. There were 54 people in all: two from each country (one Commissioner and one Delegate). Before the start of the session, some of the participants shook hands with each other, although no Commissioner shook hands with his/her Delegate, and no two people shook hands more than once. After the session, the Commissioner from Germany asked everybody how many times they had shaken hands. All the participants (excluding the German Commissioner) answered, and the numbers they gave were all different. How many times did the German Commissioner shake hands?1

europe brilliant style map fixed

Hint

Reveal Hint

How many handshakes can each person have? Consider the case of the person who shook nobody’s hand.

Solution

Reveal solution

First of all, we can determine the number of all possible handshake counts each person can have. Each participant cannot shake hands with themselves, and each one of them did not shake hands with his/her country’s partner. Therefore, the maximum number of handshakes a participant may make is 54−2=5254-2=52. As a result, the range of all possible numbers of handshakes for any given person goes from 00 to 5252. Note that each person, besides the German Commissioner, reported a different number (i.e., a distinct integer), and since handshake counts must be integers between 00 and 5252, the only possible way for this to occur is if the 5353 people’s reported counts are in one-to-one correspondence with the set {0,1,2,...,52}\{ 0,1,2,…,52 \}, which has exactly 5353 distinct elements. 

Now, consider what occurs whenever a given person shakes hands a specific number of times. For instance, suppose a person shook hands 00 times; then their corresponding partner from the same country must have shaken hands 5252 times since the person with 00 handshakes shook hands with nobody, and their partner can neither shake hands with themselves nor can they shake hands with their partner who shook none. 

Why, you may ask, does this follow? Well, we know that someone reported a count of 00, and we also know that someone must report a count of 5252. Who could possibly report 5252? Only the person who shook hands with every participant they were allowed to — namely, the partner of the person who shook hands with nobody.

If this person had shaken hands with fewer than 5252 people, then no one else could report that number. Any other person attempting it could shake hands with, at most, 5151people (they cannot shake hands with themselves, the person who shook hands with nobody, or their own partner). But 5252 must appear somewhere among the answers, which is a contradiction, and thus impossible!

The same reasoning shows that the person who shook 11 hand must be paired with the person who shook 5151, the person who shook 22 hands must be paired with the person who shook 5050, and so forth. We may express this situation as a set of ordered pairs, 

{(0,52),(1,51),(2,50),...,(26,26)}\{ (0,52), (1,51), (2,50), …, (26,26)\}

We are now on the threshold of a solution because the same piece of information that led us to deduce the number of possible values of handshake counts is the one on which our finale depends (though, to be sure, a very diplomatic one). Observe that among the 2727 possible ordered pairs there are 2626 pairs (a,b)(a,b), where a≠ba\neq b, which indeed correspond to the given responses. Consequently, the only pair left, in which both numbers are the same, must correspond to the German Delegate and must be paired with the German Commissioner, that is, (26,26)(26,26). Hence, the German Commissioner shook hands 2626 times!

By the same reasoning, if, under the same conditions, the Summit has nn other partners, the answers would be the numbers 0,1,…,2n0, 1, …, 2n. Then, we may deduce the country partners would be the pairs 2n2n and 00, 2n–12n – 1 and 11, and so on, with the unpaired answer of nn.2

References & Further Reading

  1. Omni IQ Test Problems. (n.d.). Compilation of puzzles attributed to OMNI Magazine. Retrieved from https://vdoc.pub/documents/omni-iq-test-problems-6qfkefa3hea0 ↩︎
  2. For additional presentations and solutions to this classic handshake problem, see Emma R. Hasson’s Math Puzzle: How Many Handshakes?, published in Scientific American, and Presh Talwalkar’s The “Impossible” Handshake Logic Puzzle: A Martin Gardner Classic (2017). The latter offers both a graphical interpretation and a generalization of the problem to an arbitrary number of married couples. ↩︎

Leave a Comment

Your email address will not be published. Required fields are marked *