AoPS - Problem

Source: Canada Repêchage 2020/2 CMOQR

Tags: Sets, Subsets, combinatorics, partition, partitions

parmenides51

25.04.2020 16:20

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.

Let the sum of the elements of $P$ be $2k = 16158$. Let the elements of $P$ be $4039$ 2's and $2020$ 4's. As all elements are even, there is no subset that sums to $k = 8079$. Thus $P$ can be optimally partitioned into sets $T$ and $U$ with sums of $8078$ and $8080$, respectively. Let a partition $\rho(a, b, c, d)$ denote that there are $a$ 2's and $b$ 4'2 in $T$ and $c$ 2's and $d$ 4's in $U$. It can easily be verified that the partitions $$\rho(4039, 0, 0, 2020), \rho(4037, 1, 2, 2019), \rho(4035, 2, 4, 2018), \dots, \rho(1, 2019, 4038, 1)$$all work, for a total of $2020$ different optimal partitions. $\square$