Problem A. 797. (April 2021)

A. 797. We call a system of non-empty sets \(\displaystyle H\) entwined, if for every disjoint pair of sets \(\displaystyle A\) and \(\displaystyle B\) in \(\displaystyle H\) there exists \(\displaystyle b\in B\) such that \(\displaystyle A\cup\{b\}\) is in \(\displaystyle H\) or there exists \(\displaystyle a\in A\) such that \(\displaystyle B\cup\{a\}\) is in \(\displaystyle H\).

Let \(\displaystyle H\) be an entwined system of sets containing the following \(\displaystyle n\) one-element sets: \(\displaystyle \{1\}, \{2\},\dots,\{n\}\). Prove that if \(\displaystyle n>k(k+1)/2\), then \(\displaystyle H\) contains a set with at least \(\displaystyle k+1\) elements, and this is sharp for every \(\displaystyle k\), i.e. if \(\displaystyle n=k(k+1)\), it is possible that every set in \(\displaystyle H\) have at most \(\displaystyle k\) elements.

(7 pont)

Deadline expired on May 10, 2021.

Statistics:

3 students sent a solution.
7 points:	Füredi Erik Benjámin, Sztranyák Gabriella.
6 points:	Török Ágoston.

Problems in Mathematics of KöMaL, April 2021