Q21 Matemática  (Tournament Of Towns 2020)

Henry convidou convidados de $2N$ para sua festa de aniversário. Ele tem $N$ chapéus brancos e $N$ chapéus pretos. Ele quer colocar chapéus em seus convidados e dividi-los em um ou vários círculos de dança para que em cada círculo haja pelo menos duas pessoas e as cores dos chapéus de quaisquer dois vizinhos sejam diferentes. Prove que Henry pode fazer isso exatamente de $(2N)!$ maneiras diferentes. (Todos os chapéus com a mesma cor são idênticos, todos os convidados são obviamente distintos, $(2N)!=1\cdot 2\cdot ...\cdot (2N)$.) Gleb Pogudin