Qm
BrainteasersJane StreetSIG

Handshakes across a round table without crossing

countingcatalan-numbersrecursionnon-crossing

Eight people sit evenly spaced around a round table. Simultaneously, everyone shakes hands with exactly one other person, reaching across the table, and no two pairs of arms may cross.

In how many ways can the eight people be paired up like this? Find the rule that generates the answer for 2, 4, 6, 8, 10 people.

Show a hint

Pick one person. Their partner must be at an odd distance around the table (otherwise the people between them could not pair off among themselves). The handshake splits the rest into two groups that must each pair up without crossing.

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.

Catalan NumbersBalls and Bins and the Birthday ProblemBinomial Coefficients and Pascal's TriangleBurnside's Lemma and Polya CountingCounting: Permutations and Combinations

Related questions

1, 1, 2, 5, 14, 42, what next?Binary strings with no two 1s in a rowA hundred empty glasses and the dregsMost regions from four circlesClimbing ten steps one or two at a time
All questions →