Let n>1 be an integer. A set S⊆{0,1,2,⋯,4n−1} is called ’sparse’ if for any k∈{0,1,2,⋯,n−1} the following two conditions are satisfied: (a) The set S∩{4k−2,4k−1,4k,4k+1,4k+2} has at most two elements; (b) The set S∩{4k+1,4k+2,4k+3} has at most one element.
Prove that there are exactly 8⋅7n−1 sparse subsets.