A number partition problem I have encountered the following interesting integer partitioning problem.
Let $n,k,t \in \mathbb{N}$ be given parameters and let $S_1,\ldots, S_t$ be a partition of the numbers $1,2,\ldots,n$ such that each $S_i, i \in \{1,\ldots,t\}$ contains exactly $k$ numbers (i.e., $n = t*k$ and we assume that the parameters satisfy that there is such a partition).
Question: what is the smallest number $N \geq n+1$ for which it is guaranteed that there is a partition $D_1, \ldots, D_t$ of the numbers $n+1,\ldots, N$ such that for all $i,j \in \{1,\ldots,t\}$ it holds that $\sum_{x \in S_i \cup D_i} x = \sum_{x \in S_j \cup D_j} x$, and there is $k_2 \geq k$ such that $|D_i \cup S_i| = |D_j \cup S_j| = k_2$.
Note: I am not sure if the value of $N$ depends on $k$ or not.
 A: Let us consider any partition $S_i$ and its complement $D_i$ such that for any $x \in S_i$, there exists a $2n+1-x$ in $D_i$. This guarantees that $\Sigma_{x∈Si∪Di}x = (2n+1)k$ , if we apply the same algorithm to all the $D \  partitions$, we get our solution.
It is therefore enough to prove that there exists a case when this is the only possible solution that yields the minimal value of $N$.
Hence let us consider a partition with $k > mt$, $m \ge 1$ and  $S_i = [{(i-1)k + 1 ,\ \  (i-1)k + 2, .... , (i-1)k + k}]$ $D_i = [{(2t-i+1)k , \ (2t-i+1)k - 1 ,.... , (2t-i+1)k - k }]$
It is important to note that $N$ must be of the form $n + pt$ where $p \in $ N. Hence for achieving $N < 2tk$, we must remove $mt$ elements from $D_1$ i.e $ [2n, 2n-1 ,2n-2, ... ,2n-mt + 1]$. This removal of integers has cost the $D_1$ group to be lagging behind by a total of $S = \Sigma_{r=0}^{mt-1} ((2t)k - r)$. This depletion in the sum however has to be equally spread in all the $D$ partitions, thereby each partition must be rearranged so that each depletion is $\frac{S}{t}$ in magnitude.
Therefore $D_1$ must be supplied with m additional numbers such that their sum is $S - S/t$ . We know that the biggest numbers apart from $D_1$ exist in $D_2$. even if we were to transfer the top $m$ numbers i.e $S'= \Sigma_{r=0}^{m-1} ((2t-1)k - r)$ we wouldn't be able to compensate.
By assuming $S' \ge S(1-1/t)$ and later contradicting we can thereby prove that $N \ge 2tk$ .
