MathDB

Entwined Sets

Source: KöMaL A. 797

March 24, 2022

komalcombinatoricsset theory

Problem Statement

We call a system of non-empty sets

H

entwined, if for every disjoint pair of sets

A

and

B

in

H

there exists

b\in B

such that

A\cup\{b\}

is in

H

or there exists

a\in A

such that

B\cup\{a\}

is in

H.

Let

H

be an entwined system of sets containing all of

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

Prove that if

n>k(k+1)/2,

then

H

contains a set with at least

k+1

elements, and this is sharp for every

k,

i.e. if

n=k(k+1),

it is possible that every set in

H

has at most

k

elements.

Back to Problems View on AoPS