Problem

Source: Canada RepĂȘchage 2020/2 CMOQR

Tags: Sets, Subsets, combinatorics, partition, partitions



Given a set $S$, of integers, an optimal partition of S into sets T, U is a partition which minimizes the value $|t - u|$, where $t$ and $u$ are the sum of the elements of $T$ and U respectively. Let $P$ be a set of distinct positive integers such that the sum of the elements of $P$ is $2k$ for a positive integer $k$, and no subset of $P$ sums to $k$. Either show that there exists such a $P$ with at least $2020$ different optimal partitions, or show that such a $P$ does not exist.