MathDB

Let

n>1

be an integer. A set

S \subset \{ 0,1,2, \ldots, 4n-1\}

is called rare if, for any

k\in\{0,1,\ldots,n-1\}

, the following two conditions take place at the same time (1) the set

S\cap \{4k-2,4k-1,4k, 4k+1, 4k+2 \}

has at most two elements; (2) the set

S\cap \{4k+1,4k+2,4k+3\}

has at most one element. Prove that the set

\{0,1,2,\ldots,4n-1\}

has exactly

8 \cdot 7^{n-1}

rare subsets.

Problem Statement