Say I have n elements . I want to put them into k sets (S1 ... Sk, ):
$|(S1 ⋃ S2 ⋃ S3 ⋃ ..... ⋃ Sk)| = n$
The sets need not be disjoint (e.g you can place elements into their intersections).
Each set must have n/2 elements.
$|Si| = n/2 $
Can it be proven that there always exist a solution, for all (n,k) :n is even and k < n?
I have a hunch, from the inclusion exclusion principle:
$|(S1 ⋃ S2 ⋃ S3 ⋃ ..... ⋃ Sk)| = Σi|Si| - Σi,j |(Si ∩ Sj)| + Σi,j,m |(Si ∩ Sj ∩ Sm)| - .... -|(S1 ∩ S2 ∩ S3 ∩ ..... ∩ Sk)|$
Since each set has n/2 elements, the sum of the cardinalities of k sets is k (n/2), so,
$n = k (n/2) - Σi,j |(Si ∩ Sj)| + Σi,j,m |(Si ∩ Sj ∩ Sm)| - .... -|(S1 ∩ S2 ∩ S3 ∩ ..... ∩ Sk)|$
thus, so long as the sets fulfil:
$-Σi,j |(Si ∩ Sj)| + Σi,j,m |(Si ∩ Sj ∩ Sm)| - ...-|(S1 ∩ S2 ∩ S3 ∩ ..... ∩ Sk)| = k(n/2) - n$
Then it is a solution for the above problem, and thus there are one or more solutions to the problem.
Is my reasoning correct, or are there any other constraints?
I find it convenient to let $m = n/2$ so there are fewer fractions in the formulas, so wherever you wrote $n/2$ I will write $m$ and wherever you wrote $n$ I will write $2m.$
We then have $k < 2m,$ and we want $\lvert S_i\rvert=m$ for $i=1,\ldots,k.$
These constraints say that $m > 0,$ since we cannot have a list of sets with fewer than zero sets in the list. We must then put the additional constraint that $k \geq 2,$ because $m \geq 1$ and therefore we need the union of the sets $S_i$ to have at least two elements, whereas with $k = 0$ we get an empty set and with $k = 1$ we have only one set $S_1$ and it has only one element, hence the union has only one element.
You did not say the sets $S_i$ must each be different from all others, but you can add that constraint as well; it is still possible to find such a list of sets. We can show this by explicit construction.
Since we want $\lvert S_1 \cup S_2 \cup S_3 \cup\cdots\cup S_k\rvert = 2m,$ let's identify $2m$ unique objects that can be the elements of the set $S_1 \cup S_2 \cup S_3 \cup\cdots\cup S_k$, and let's label these objects $\newcommand{a}{a}\a_1, \a_2,\a_3,\ldots, \a_{2m}.$
First let's consider the case $2 \leq k \leq m+1.$ For $1 \leq i \leq k - 1,$ let $$ S_i = \{ \a_i, \a_{i+1}, \a_{i+2}, \ldots, \a_{i+m-1}\},$$ so $\lvert S_i\rvert = m,$ and let $$ S_k = \{ \a_{m+1}, \a_{m+2}, \a_{m+3}, \ldots, \a_{2m}\},$$ so $\lvert S_k\rvert = m.$ Clearly all these sets are distinguishable, since the "first" element in each of the first $k-1$ sets is a different element from the list $\a_1, \a_2, \ldots \a_{k-1},$ whereas the "first" element of $S_k$ is $\a_{m+1}$, which is different from all the others since $m+1 > k-1.$ Also note that $S_1 \cup S_k = \{ \a_1, \a_2, \a_3, \ldots, \a_{2m}\}$ and that every other $S_i$ is a subset of $S_1 \cup S_k,$ so $\lvert S_1 \cup S_2 \cup S_3 \cup\cdots\cup S_k\rvert = 2m.$
Finally consider the case $m+2 \leq k <2m,$ which is the only other possible case. For $1 \leq i \leq m$ let $$ S_i = \{ \a_i, \a_{i+1}, \a_{i+2}, \ldots, \a_{i+m-1}\}$$ (always $m$ consecutive elements not including $\a_{2m}$). For $m+1 \leq i \leq k-1$, let $$ S_i = \{ \a_{i-(m-1)}, \a_{i-(m-2)}, \ldots, \a_{i-2}, \a_{i-1},\a_{2m}\},$$ which contains $\a_{2m}$ plus $m-1$ consecutive elements other than $\a_{2m}$ but does not contain $\a_{2m-1}$. Finally, let $$ S_k = \{ \a_{m+1}, \a_{m+2}, \a_{m+3}, \ldots, \a_{2m-1}, \a_{2m}\}.$$ So we have $k$ sets, each one distinguishable from all others by considering what its "first" element is and whether it contains $\a_{2m-1}$ and/or $\a_{2m},$ and $\lvert S_i\rvert = m$ for every $i$ where $1 \leq i \leq k.$ Morever, again $S_1 \cup S_k = \{ \a_1, \a_2, \a_3, \ldots, \a_{2m}\}$ and every other $S_i$ is a subset of $S_1 \cup S_k,$ so $\lvert S_1 \cup S_2 \cup S_3 \cup\cdots\cup S_k\rvert = 2m.$