Problem

Source: Fourth Saudi Arabia JBMO TST 2019, P1

Tags: combinatorics



A set $S$ is called perfect if it has the following two properties: a) $S$ has exactly four elements b) for every element $x$ of $S$, at least one of the numbers $x - 1$ or $x+1$ belongs to $S$. Find the number of all perfect subsets of the set $\{1,2,... ,n\}$