Bariz - Problem

Source: 239 School Open MO, 2023, Junior league, Problem 8

Tags: combinatorics, set theory

oVlad

01.04.2023 12:44

Let $n{}$ and $k{}$ be natural numbers, with $n > 2k$. In the deck of cards, each card contains a subset of the set $\{1, 2, \ldots , n\}$ consisting of at least $k+1$, but no more than $n-k$ elements. Each $m$-element set is written exactly on $m-k$ cards. Is it possible to split these cards into $n- 2k$ stacks so that in each stack all subsets on the cards are different, and any two of them intersect?

Here is a construction, Proving that it works is a little bit annoying but it isnt hard after you know the construction so I will not write it down: $A_1:=\{1\}, A_2:=\{2\}, ..., A_{n-2k-1}:=\{n-2k-1\}, A_{n-2k}:=\{n-2k, n-2k+1, ..., n\}$ Now let $A$ be some set with an allowed number of elements. Let $F(A)$ be the set of indices $i$ for which $A_{i}$ and $A$ aren't disjoint. Now write down the set $F(A)$ ascending and write after it the set $\{1,2,...,n-2k\}\backslash F(A)$ descending. Then pick the first $|A|-k$ elements of this sequence and put all cards with set A in the corresponding stacks.