Pairing with a difference of 1 or 11

HardCombinatorics Brainteasers~12m

Let $S = \{1, 2, 3, \dots, 22\}$ . In how many ways can $S$ be partitioned into $11$ pairs such that the two elements of every pair differ by exactly $1$ or exactly $11$ ?

Show hints (2)+

Count perfect matchings of the graph on $1$ – $22$ with edges for differences $1$ and $11$ .
Recurse: the smallest unmatched vertex pairs with $+1$ or $+11$ ; sum the branches to get $145$ .

Answer

Reveal answer →

145

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, Two Sigma

Pairing with a difference of 1 or 11

Answer

Related questions