A handshaking puzzle

By Przemysław Wałęga, Queen Mary University of London

Logical reasoning and proof, whether done using math notation or informally in your head, is an important tool of computer scientists. The idea of proving, however, is often daunting for beginners and it takes a lot of practice to master this skill. Here we look at a simple puzzle to get you started.

Computer Scientists use logical reasoning and proofs a lot. They can be used to ensure correctness of algorithms. Researchers doing theoretical computer science use proofs all the time, working out theories about computation.

Proving mathematical statements can be very challenging, though. Coming up with a proof often requires making observations about a problem and exploiting a variety of different proof methods. Making sure that the proof is correct, concise, and easy to follow matters too, but that in itself needs skill and a lot of practice. As a result, proving can be seen as a real art of mathematics.

Let’s think about a simple puzzle to show how logical thinking can be used when solving a problem. The puzzle can be solved without knowing any specific maths, so anyone can attempt it, but it will probably look very hard to start with.

Before you start working on it though, let me recommend that first you try to solve it entirely in your mind, that is, with no pen and paper (and definitely no computer!). 

The Puzzle

Here is the puzzle, which I heard at a New Year’s party from a friend Marcin:

Mrs. and Mr. Taylor hosted a party and invited four other couples. After the party, everyone gathered in the hallway to say their goodbyes with handshakes. No one shook hands with themselves (of course!) or their partner, and no one shook hands with the same person more than once. Each person kept track of how many people they had shaken hands with. At one point, Mr. Taylor shouted “STOP” and asked everyone to say how many people they had shaken hands with. He received nine different answers. 

How many people did Mrs Taylor shake hands with?

I will give you some hints to help solving the puzzle, but first try to solve it on you own, and see how far you get. Maybe you will be solve the puzzle on your own? 

Why did I recommend solving the puzzle without pen and paper? Because, our goal is to use logical and critical thinking instead of finding a solution in a “brute force” manner, that is, blindly listing all the possibilities and checking each of them to find a solution to the puzzle. As an example of a brute force way of solving a problem, take a crossword puzzle where you have all but one of the letters of a word. You have no idea what the clue is about, so instead you just try the 26 possible letters for the missing one and see which make a word and then check which that do fit the clue! 

Notice that the setting of our puzzle is finite: there are 10 people shaking hands, so the number of ways they shake hands is also finite if bigger than say checking 26 different letters of the crossword problem. That means you could potentially list all the possible ways people might shake hands to solve the puzzle. This is, however, not what we are aiming for. We would like to solve the puzzle by analysing the structure of the problem instead of performing brute force computation. 

Also, it is important to realise that often mathematicians solve puzzles (or prove theorems) about situations in which the number of possibilities is infinite so the brute force approach of listing them all is not possible at all. There are also many situations where the brute force approach is applicable in theory, but in practice it would require considering too many cases: so many that even the most powerful computers would not be able to provide us with an answer in our lifetimes. 

For our puzzle, you may be tempted to list all possible handshake situations between 10 people. Before you do start listing them, let’s check how much time you would need for that.  You have to consider every pair that can be formed from 10 people. A mathematician refers to that as “10 choose 2”, the answer to which is that there are 45 possible pairs among 10 people (the first person pairs with 9 others, the next has 8 others to pair with having been paired with the first already, and so on and 9+8+….+1 = 45). However, 45 is not the number that we are looking for. Each of these pairs can either shake hands or not, and we need to consider all those different possibilities. There are 2⁴⁵ such handshake combinations. How big is this number? The number 2¹⁰ is 1024, so it is approximately 1000. Hence 2⁴⁰=(2¹⁰)⁴ (which is clearly smaller than our 2⁴⁵) is approximately 1000⁴ = 1,000,000,000,000 that is, a trillion. Listing a trillion combinations should sound scary to you. Indeed, if you can be quick enough to write each of the trillion combinations in one second, you will spend 31 688 years. Let’s not try this!

Of course, we can look more closely at the description of the puzzle to decrease the number of combinations. For example, we know that nobody shakes hands with their partner, which will already massively reduce the number. However, let’s try to solve the puzzle without using any external memory aids or computational power. Only our minds.

Can you solve it? A key trick that mathematicians and computer scientists use is to break down problems into simpler problems first (decomposition). You may not be able to solve this puzzle straight away, so instead think about what facts you can deduce about the situation instead.

If you need help, start by considering Hint 1 below. If you are still stuck, maybe Hint 2 will help? Answer these questions and you will be a long way to solving the puzzle.

Hints

1. Mr. Taylor received nine different answers. What are these answers?
2. Knowing the numbers above, can you work out who is a partner of whom?

No luck in solving the puzzle? Try to spend some more time before giving up!  Then read on. If you managed to solve it you can compare your way of thinking with the full solution below.

Solution

First we will answer Hint 1. We can show that the answers received by Mr. Taylor are 0, 1, 2, 3, 4, 5, 6, 7, and 8. There are 5 couples, meaning that there are 10 people at the party (Mr. and Mrs. Taylor + 4 other couples). Each person can shake hands with at least 0 people and at most 8 other people (since there are 10 people, and they cannot shake hands with themselves or their partner). Since Mr. Taylor received nine different answers from the other 9 people, they need to be 0, 1, 2, 3, 4, 5, 6, 7, and 8. This is an important observation which we will use in the second part of the solution.

Next, we will answer Hint 2. Let’s call P0 the person who answered 0, P1 the person who answered 1, …, P8 the person who answered 8. The person with the highest (or the lowest) number of handshakes is a good one to look at first.

• Who is the partner of P8? P8 did not shake hands with themselves and with P0 (as P0 did not shake hands with anybody). So P8 had to shake hands with all the other 8 people. Since no one shakes hands with their partner, it follows that P0 is the partner of P8!
• Who is the partner of P7? They did not shake hands with themselves, with P0 and with P1, because we already know that P1 shook hands with P8, and they shook hands with only one person. So the partner of P7 can be either P8, P0, or P1. Since P8 and P0 are partners, P7 needs to be the partner of P1.
• Following through with this analysis for P6 and P5, we can show that the following are partners: P8 and P0, P7 and P1, P6 and P2, P5 and P3. The only person among P0, … , P8 who is left without a partner is P4. So P4 needs to be Mrs. Taylor, the partner of Mr. Taylor, the one person left who didn’t give a number. 

Consequently, we have also showed that Mr Taylor shook hands with 4 people. 

Observe that the analysis above does not only provide us an answer to the puzzle, but it also allows us to uniquely determine the handshake setting as presented in the picture below (called a graph by Computer Scientists). Here, people are nodes (circles) and handshakes are represented as edges (lines) in the graph. Red edges correspond to handshakes with P8, blue edges are handshakes with P7, green with P6 and yellow with P5. Partners are located next to each other, for example, Mr. Taylor is a partner with P4.

Large Language Models

Although this article is about logical thinking, and not about tools to solve logic puzzles, it is interesting to see if current AI models are capable of solving the puzzle. As puzzles go it is relatively easy and occurs on the Internet in different settings and languages, so large language models (LLMs) trained on the Internet should be good at solving it. Let’s test them!

I asked ChatGPT-4o and Gemini 1.5 Flash to solve the puzzle. To my surprise, both of them did struggle. They had problems with understanding some parts of the problem formulation and made mathematical mistakes. 

• ChatGPT seems to wrongly assume that Mr. Taylor answered his own question about the number of handshakes, and so, that each of 10 people announced a different number of handshakes. As follows from our solution of the puzzle, there exists exactly one graph representing the handshake situation. In this graph, the number of handshakes of Mr. and Mrs. Taylor is the same, namely 4. Hence, the additional assumption made by ChatGPT (that each of 10 people had a different number of handshakes) makes the situation described in the puzzle impossible. Interestingly, ChatGPT was able to solve such an impossible puzzle providing a correct answer… Does it mean that ChatGPT has solved the puzzle?
• Gemini, in contrast, states that the puzzle cannot be solved without more information such as the order of arrivals. This is clearly wrong. We know how to solve the puzzle and the order of arrivals is actually completely irrelevant to the puzzle! 

This small experiment uses basic LLMs and does not aim to draw any conclusions about their capabilities. I am quite certain that one can find an LLM that can solve this simple puzzle without mistakes. However, this experiment aims to emphasise the need for checking AI solutions yourself. To do that you need to gain the skills of doing proof yourself!

In what follows I provide answers obtained from AI models and highlight as bold parts which are wrong assumptions or reasoning.

Solution by ChatGPT:

Key Observations:

1. There are 10 people in total at the party (5 couples: Mr. and Mrs. Taylor and 4 other couples).
2. No one shakes hands with their own partner.
3. No one shakes hands with themselves or the same person more than once.
4. The handshake answers must be unique and range from 0 to 9 (since there are 10 people, including Mr. and Mrs. Taylor).

Solution:

• Since there are 10 people total, the number of handshakes any one person could have ranges from 0 to 9.
• If everyone gives a unique answer, it means:
  • One person shook hands with 0 people.
  • Another shook hands with 1 person.
  • Another with 2, and so on, up to 9.

Steps:

1. The person who shook hands with 9 people: This person shook hands with everyone else, meaning their partner (who doesn’t shake hands with them) must have shaken hands with 0 people.
2. The person who shook hands with 8 people: This person shook hands with everyone except their partner and the person who shook hands with 0.
3. By continuing this pattern, we see that for every unique count of handshakes k, the person with k handshakes corresponds to a partner with 9−k handshakes.

Mrs. Taylor’s Handshakes:

• Mr. Taylor shouted “STOP” after collecting answers from all 10 people. Since there are 9 different handshake counts, one of those counts must belong to Mrs. Taylor.
• Let’s assume Mr. Taylor is among the group and is the one with the maximum or minimum handshakes.
• The pairing pattern ensures Mrs. Taylor’s number of handshakes must fall within the range, but based on symmetry of couples logic !

The key is to match couples symmetrically:

If Mr. Taylor gets answers (0, 1, 2,…

Let’s refine the solution:

• The possible handshake counts are 0,1,2,…,9, ensuring each number is unique.
• The pairing works such that if one person shakes k hands, their partner shakes 9-k hands.

This logic means:

• The person who shook 9 hands paired with the person who shook 0.
• The person who shook 8 hands paired with the person who shook 1, and so on.

Mrs. Taylor’s Count:

If there are nine unique handshake counts (from 0 to 9), Mrs. Taylor must have shaken 4 hands because her partner, Mr. Taylor, who controls the setup, must fall at the midpoint to allow symmetrical pairing logic.

Solution by Gemini:

Certainly, let’s solve the handshake puzzle!

Understanding the Problem:

• We have 10 people at the party (Mr. and Mrs. Taylor, plus 4 other couples).
• No one shakes hands with themselves or their partner.
• No one shakes hands with the same person more than once.
• Each person keeps track of how many handshakes they’ve done.
• Mr. Taylor asks everyone how many handshakes they’ve done, and gets 9 different answers.
• We need to figure out how many handshakes Mrs. Taylor did.

Let’s Analyze:

The key to solving this is to consider the possible range of handshakes each person could have.

• Lowest Possible Handshakes: If someone is the first to arrive and doesn’t shake hands with anyone else, they’ll have 0 handshakes.
• Highest Possible Handshakes: The maximum number of handshakes depends on the order of arrivals and who shakes hands with whom. In the most efficient scenario, everyone could shake hands with everyone else except their partner. This would lead to a maximum of 8 handshakes for each person.

Now, let’s consider the 9 different answers:

Since there are 9 different answers, and the minimum is 0, the maximum number of handshakes someone could have is 8.

Let’s think about Mrs. Taylor:

• She can’t have 0 handshakes because she would have to shake hands with someone eventually.
• She can’t have 8 handshakes because Mr. Taylor would have to have the same number (since they are the only couple).

Therefore, Mrs. Taylor must have shaken hands with a number between 1 and 7.

Unfortunately, without more information about the order of arrivals and who shook hands with whom, we can’t pinpoint the exact number of handshakes Mrs. Taylor did.

Let me know if you’d like to explore a specific scenario with a particular order of arrivals and handshakes to determine Mrs. Taylor’s exact number!

More on …

• Theory, Logic and Deduction
• Puzzles

Related Magazines …

• The Computational Thinking Puzzle Book

Our Books …

• The Power of Computational Thinking:
  • Games Magic and Puzzles to help you become a computational thinker
• Conjuring with Computation
  • Learn the basics of computer science through magic tricks

---

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

---

This blog is funded by UKRI, through grant EP/W033615/1.