Find all positive integers $n$ such that the elements of $$\{1,2,...,2n+1\}-\{n+1\}$$can be partitioned into two groups with the same number of elements and the same sum of their elements.
Problem
Source: Thailand MO Day 2 P6
Tags: combinatorics
11.05.2024 10:30
I am assuming this means a set $\{1,2,\dots , 2n+1\} \setminus \{n+1\}$ In that case, all $n \ge 2$ would work. The total sum of all elements would be $n(2n+2)$ and each set would have a total sum of $n(n+1)$. This is akin to adding $n+1$ n times and adding or subtracting integers from them. It is always possible to express $0$ as a sum of$n$ distinct positive and negative integers for all positive $n$, however $n=1$ results in 2 occurrences of $n+1$ which is not possible. Thus, $n \ge 2$.
11.05.2024 15:02
The answer is $\boxed{n\geq 2}$. We will provide a construction through induction. Obviously $n=1$ doesn't work. For $n=2$ consider the sets $\{1,5\}$ and $\{2,4\}$. Now when going from $n\rightarrow n+1$ let $S$ be the set containing the element $n+2$. Now simply consider the set $S\cup \{2n+3\} \cup \{n+1\} / \{n+2\}$ which can be verified to work.
16.06.2024 19:26
Solved with kingu but for once I think it was just me solving while he was fooling around. We claim that the answer is all $n\ge2$, it is quite clear that $n=1$ does not satisfy the given conditions. We prove our answer by giving an explicit construction. For even $n$, consider the pairs $(i,2n+2-i)$ for all $1 \le i \le n$. Each pair has sum $2n+2$. Since $n$ is even, we choose $\frac{n}{2}$ of these pais and chuck them in one set, and chuck all the other elements in the other set. This satisfies all the desired conditions. For odd $n$, consider the triples $(n-1,n,n+4) $ and $(n-2,n+2,n+3)$. Each triple has an equal sum of $3n+3$. Then, we pair elements like in the above case into pairs $(i,2n+2-i)$ for all $1\le i \le n-3$. Each pair has an equal sum of $2n+2$. Since since $n-3$ is even (and non-negative), we simply choose $\frac{n-3}{2}$ of these pairs and chuck them in one set, along with the elements of the first triple, $(n-1,n,n+4) $ and chuck all the remaining elements in the other set. This satisfies all the desired conditions. Thus, for all $n\ge 2$, the elements of $\{1,2,\dots , 2n+1\} \setminus \{n+1\}$ can be partitioned into two groups with the same number of elements and the same sum of their elements.