Problem

Source:

Tags: combinatorics unsolved, combinatorics



Let $n > 1$ be an integer. A set $S \subseteq \{ 0, 1, 2, \cdots , 4n - 1 \}$ is called ’sparse’ if for any $k \in \{ 0, 1, 2, \cdots , n - 1 \}$ the following two conditions are satisfied: $(a)$ The set $S \cap \{4k - 2, 4k - 1, 4k, 4k + 1, 4k + 2 \}$ has at most two elements; $(b)$ The set $S \cap \{ 4k +1, 4k +2, 4k +3 \}$ has at most one element. Prove that there are exactly $8 \cdot 7^{n-1}$ sparse subsets.