MathDB

if x \in S => (x - 1) or (x+1) \in S, S has at least 4 elements

Source: JBMO Shortlist 2018 C1

July 22, 2019

combinatoricsSetsSubsets

Problem Statement

A set

S

is called neighbouring if it has the following two properties: a)

S

has exactly four elements b) for every element

x

S

, at least one of the numbers

x - 1

x+1

belongs to

S

. Find the number of all neighbouring subsets of the set

\{1,2,... ,n\}