Problem

Source: Tournament of Towns, Senior A-Level Paper, Spring 2020 , p4

Tags: combinatorics



Henry invited $2N$ guests to his birthday party. He has $N$ white hats and $N$ black hats. He wants to place hats on his guests and split his guests into one or several dancing circles so that in each circle there would be at least two people and the colors of hats of any two neighbours would be different. Prove that Henry can do this in exactly $(2N)!$ different ways. (All the hats with the same color are identical, all the guests are obviously distinct, $(2N)! = 1 \cdot 2 \cdot . . . \cdot (2N)$.) Gleb Pogudin