Find all positive integers $n$ such that the set $S=\{1,2,3, \dots 2n\}$ can be divided into $2$ disjoint subsets $S_1$ and $S_2$, i.e. $S_1 \cap S_2 = \emptyset$ and $S_1 \cup S_2 = S$, such that each one of them has $n$ elements, and the sum of the elements of $S_1$ is divisible by the sum of the elements in $S_2$. Proposed by Viktor Simjanoski
Problem
Source: 3rd Memorial Mathematical Competition "Aleksandar Blazhevski - Cane"- Junior D2 P4
Tags: number theory, Sets, disjoint subsets, Divisibility
17.01.2022 22:57
The answer is all $n \not \equiv 5\pmod{6}$. Constraction for $n=2k$ : $S_1=\{1,2,...,k\}\cup \{3k+1,3k+2,...,4k\}$ and $S_2=S\setminus S_1$. For $n\equiv 1,3 \pmod{6}$ I will not give a construction but I will show that it's possible to construct $S_1$ and $S_2$. Let $n=2k+1$ and let $T=\sum_{i\in S_1} i$ and $R=\sum_{j\in S_2} j$ and assume $T\le R$. Then $T\mid R \implies T\mid T+R \implies T\mid (2k+1)(4k+3)$. Since $|S_1|=2k+1$, we have $T\geq (k+1)(2k+1)$. $\bullet$ $k\not\equiv 2\pmod{3}$: In this case we can find $S_1$ such that $T=\frac{(2k+1)(4k+3)}{3}$, because $\frac{(2k+1)(4k+3)}{2}>\frac{(2k+1)(4k+3)}{3}>(k+1)(2k+1)$. $\bullet$ $k\equiv 2\pmod{3}$: Observe that $T\geq (k+1)(2k+1)>\frac{(2k+1)(4k+3)}{4}$. Since $ T\mid (2k+1)(4k+3)$ and $2$ and $3$ doesn't divide $(2k+1)(4k+3)$ we can't find $K$. So we are done!
10.06.2023 11:54
We claim the answer is all $n \not\equiv 5 \pmod 6$. Let $\sum_{i \in S_1} i=A$ and $\sum_{i \in S_2} i=B$. Then, $A+B=n(2n+1)$ and $A \mid B$. Note that $A \geq 1+2+\ldots+n=\dfrac{n(n+1)}{2}$ and $B \leq 2n+(2n-1)+\ldots+(n+1)=\dfrac{n(3n+1)}{2}.$ Therefore, $B \leq \dfrac{n(3n+1)}{2} <\dfrac{3n(n+1)}{2} \leq 3A$ Since $A \mid B$, this implies that $B \in \{A,2A \}$. We distinguish two cases. Case 1: $B=A$. Then, $A=\dfrac{n(2n+1)}{2},$ and so $n$ must be even. For all even $n$, we may take $S_1=\{1,2n \} \cup \{2,2n-1 \} \cup \ldots \cup (\dfrac{n}{2},(2n+1)-\dfrac{n}{2})$. It is straightforward to check that $|S_1|=n$ and $A=n(2n+1)$. Case 2: $B=2A$. Then, $A=\dfrac{n(2n+1)}{3}$, and so $3 \mid n(2n+1)$, i.e. $n \not\equiv 2 \pmod 3$. Consider the collection $\mathcal{F}$ of all sets $X \subseteq \{1,2,\ldots, 2n \}$ such that $|X|=n$. Note that the minimum sum of the elements of a set belonging in $\mathcal{F}$ is $m=1+2+\ldots+n=\dfrac{n(2n+1)}{2}$, and the maximum is $M=2n+(2n-1)+\ldots+(n+1)=\dfrac{n(3n+1)}{2}$. Note that $m<A<M$. We claim that all intermediate sums in $[m,M]$ can be achieved by a set in collection $\mathcal{F}$. Indeed, assume all sums in $[m,t]$ have be achieved for some $t \geq m$. If $t=M$, we are done. If not, we want to find a set that achieves $t+1$. Let $T=\{x_1,\ldots,x_n \}$ be a set such that its elements sum to $t$. If there are two elements of $T$ that are not consecutive, we may increment the smallest one of them by one and finish. Moreover, if $x_n \neq 2n$, we may increment $x_n$ by one and finish. If neither of these happens, set $T$ must necessarily be $\{n+1,n+2,\ldots,2n \}$, which is a contradiction as we assumed $t \neq M$. To sum up, the working $n$ are the evens and the $n \not\equiv 2 \pmod 3$, that is all $n \not\equiv 5 \pmod 6$.