# Two Sets: Adding Each Integer to the Set With Smaller Sum
## Solution Algorithm
For each integer \( k \) in \( [n \, .. 1] \), if the sum of integers
in the first set is less than or equal to the sum of integers in the
second set, add \( k \) to the first set; otherwise add \( k \) to the
second set.
## Illustration for \( n \equiv 0 \pmod{4} \)
12 9 → 8 5 → 4 1 (set 1)
↓ ↑ ↓ ↑ ↓ ↑
11 → 10 7 → 6 3 → 2 (set 2)
## Illustration for \( n \equiv 3 \pmod{4} \)
11 8 → 7 4 → 3 (set 1)
↓ ↑ ↓ ↑ ↓
10 → 9 6 → 5 2 → 1 (set 2)
## Outline of Proof of Solution for Any \( n \equiv 0 \pmod{4} \)
We first show that we can obtain a valid solution for \( n = 4 \) by
following the solution algorithm.
```
4 1 (set 1)
3 2 (set 2)
```
For \( n \ge 8 \), we add the integers \( n, (n - 1), (n - 2), (n - 3)
\) into the two sets by following the solution algorithm.
```
n n-3 (set 1)
n-1 n-2 (set 2)
```
Then we solve the problem for \( n - 4 \). We keep repeating this
until we reach \( n = 4 \).
## Outline of Proof of Solution for Any \( n \equiv 3 \pmod{4} \)
We first show that we can obtain a valid solution for \( n = 3 \) by
following the solution algorithm.
```
3 (set 1)
2 1 (set 2)
```
For \( n \ge 7 \), we add the integers \( n, (n - 1), (n - 2), (n - 3)
\) into the two sets by following the solution algorithm.
```
n n-3 (set 1)
n-1 n-2 (set 2)
```
Then we solve the problem for \( n - 4 \). We keep repeating this
until we reach \( n = 3 \).