olymmath

CAPS 2015 Problem 2

    A family of sets FF is called perfect if the following condition holds: For every triple of sets X1,X2,X3∈FX_1, X_2, X_3\in F , at least one of the sets (X1∖X2)∩X3,(X_1\setminus X_2)\cap X_3, (X2∖X1)∩X3(X_2\setminus X_1)\cap X_3 is empty. Show that if FF is a perfect family consisting of some subsets of a given finite set UU , then ∣F∣≤∣U∣+1\left\lvert F\right\rvert\le\left\lvert U\right\rvert+1 .

    Proposed by Michał Pilipczuk

    Dataset text AI-MO AoPS. 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 caps/2015/p2 · Tag 1F4QVGXE00 · Edit this page on GitHub · Keys: j next, k previous