Qm
Brainteasers

Can 21 people each shake exactly three hands?

parityhandshakesgraphscounting

At a party, each handshake involves exactly two people.

  1. Is it possible that 21 people each shook hands with exactly three other people?
  2. Is it possible with 20 people?

Explain the general rule behind your answers.

Show a hint

Count the handshakes by adding up everyone's personal count. Each handshake gets counted twice.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Graph Theory BasicsBalls and Bins and the Birthday ProblemBinomial Coefficients and Pascal's TriangleBurnside's Lemma and Polya CountingCatalan Numbers

Related questions

Ten in a circle, each says both neighbours are knavesEveryone shouts the number of red hats, one must be rightThe dinner party handshakesHandshakes at a party of ten couplesThe number of odd-handshakers is always even
All questions →