For
![n\ge 2](/media/m/9/0/3/903d008e948ff30e3507a6c2af5ef5b7.png)
, let
![S_1](/media/m/7/7/e/77ed808eaa71be903a10ce754f90a904.png)
,
![S_2](/media/m/c/1/1/c11855875777bfedb764b27ccc108413.png)
,
![\ldots](/media/m/5/8/5/58542f3cc6046ef3889f8320b7487d60.png)
,
![S_{2^n}](/media/m/2/b/c/2bc780a8917013e6d0da8d0074e98c16.png)
be
![2^n](/media/m/8/e/a/8ea40429bb1e68f68f9e7a97fd5351f7.png)
subsets of
![A = \{1, 2, 3, \ldots, 2^{n + 1}\}](/media/m/9/d/0/9d0713ae61b229ad476a6dfccb818a98.png)
that satisfy the following property: There do not exist indices
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
and
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
with
![a < b](/media/m/6/a/3/6a3a410dff0a5b1e8d34849a9860b93f.png)
and elements
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
,
![y](/media/m/c/c/0/cc082a07a517ebbe9b72fd580832a939.png)
,
![z\in A](/media/m/a/2/7/a27b34ffbd8bd9b6ae059649f7794e80.png)
with
![x < y < z](/media/m/f/8/2/f8230ecd7f3fe97f52c4f0ed42914597.png)
and
![y](/media/m/c/c/0/cc082a07a517ebbe9b72fd580832a939.png)
,
![z\in S_a](/media/m/b/a/d/bad4435d10ab1139dcfb40c801298be0.png)
, and
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
,
![z\in S_b](/media/m/3/f/d/3fdbac7662ca78370cd90e45ee0608e7.png)
. Prove that at least one of the sets
![S_1](/media/m/7/7/e/77ed808eaa71be903a10ce754f90a904.png)
,
![S_2](/media/m/c/1/1/c11855875777bfedb764b27ccc108413.png)
,
![\ldots](/media/m/5/8/5/58542f3cc6046ef3889f8320b7487d60.png)
,
![S_{2^n}](/media/m/2/b/c/2bc780a8917013e6d0da8d0074e98c16.png)
contains no more than
![4n](/media/m/d/d/f/ddf67aa4ea9ec2adcdeb9f6ea563645d.png)
elements.
Proposed by Gerhard Woeginger, Netherlands
%V0
For $n\ge 2$, let $S_1$, $S_2$, $\ldots$, $S_{2^n}$ be $2^n$ subsets of $A = \{1, 2, 3, \ldots, 2^{n + 1}\}$ that satisfy the following property: There do not exist indices $a$ and $b$ with $a < b$ and elements $x$, $y$, $z\in A$ with $x < y < z$ and $y$, $z\in S_a$, and $x$, $z\in S_b$. Prove that at least one of the sets $S_1$, $S_2$, $\ldots$, $S_{2^n}$ contains no more than $4n$ elements.
Proposed by Gerhard Woeginger, Netherlands