olymmath

KöMaL 2021 A797

    We call a system of non-empty sets HH entwined, if for every disjoint pair of sets AA and BB in HH there exists b∈Bb\in B such that A∪{b}A\cup\{b\} is in HH or there exists a∈Aa\in A such that B∪{a}B\cup\{a\} is in HH. Let HH be an entwined system of sets containing the following nn one-element sets: {1},{2},…,{n}\{1\}, \{2\},\dots,\{n\}. Prove that if n>k(k+1)/2n>k(k+1)/2, then HH contains a set with at least k+1k+1 elements, and this is sharp for every kk, i.e. if n=k(k+1)n=k(k+1), it is possible that every set in HH have at most kk elements.

    Official text KöMaL. Quoted with source.

    Solutions

    No solution is on olymmath yet. Official and human solutions come first when they arrive. AI solutions come after them, with a label.

    Add a solution

    Similar problems

    These problems have the most words in common with this statement.

    Locator hu-komal/2021/a797 · Tag 5TADNH9GGW · Edit this page on GitHub · Keys: j next, k previous