Is it possible to construct two subsequences of a sequence X with specific properties such that the two subsequence sums are the same? I have been thinking about a certain variant of a problem from an Olympiad:
A sequence $X =a_1, a_2, \ldots, a_n\;$consists of positive integers, where $a_i \le i$ for $1 \le i \le n$, and $n \ge 2$. The sum of the elements in $X$ is even. Prove that one can split $X$ into two subsequences such that the sum of the elements in each subsequence is the same.
My first step was to try to construct a subsequence and bound the sum of the elements, but I have not found I have made any progress after this step. I have also thought of trying to apply the Pigeonhole Principle, but I am not quite sure how to approach this problem with it.
 A: Let us say that a sequence $\mathbf{a} = (a_1, \ldots, a_n)$ has property (*) if $n \geq 2$ and each $a_i$ is a positive integer less than or equal to $i$.  We will call a sequence $\mathbf{a}$ permissible if it has property (*) and $\sum_i a_i$ is even.  We want to show that

Claim 1
  Every permissible sequence $\mathbf{a} = (a_1, \ldots, a_n)$ can be split into two subsequences $\mathbf{b}$ and $\mathbf{c}$ such that $\sum_i b_i = \sum_i c_i$.

Now, consider the the following claim about sequences with property (*).

Claim 2
  For every integer $m$ such that $0 \leq m \leq n + 1$, every sequence $\mathbf{a} = (a_1, \ldots, a_n)$ with property (*) can be split into two subsequences $\mathbf{b}$ and $\mathbf{c}$ such that $\left|\sum_i b_i - \sum_i c_i - m\right| \leq 1$.

We argue that Claim 2 implies Claim 1.  Suppose that Claim 2 holds and consider a permissible sequence $\mathbf{a} = (a_1, \ldots, a_n)$.  By Claim 2 with $m = 0$, $\mathbf{a}$ can be split into two subsequences $\mathbf{b}$ and $\mathbf{c}$ such that $\left|\sum_i b_i - \sum_i c_i\right| \leq 1$.  Since $\sum_i a_i$ is even, $\sum_i b_i - \sum_i c_i$ is also even so $\sum_i b_i = \sum_i c_i$.
Thus, it suffices to prove Claim 2.  We do this by induction as follows.
The base case is $n = 2$.  There are exactly two sequences with property (*) for $n = 2$: $(1, 1)$ and $(1, 2)$.
Suppose $\mathbf{a} = (1, 1)$.  We know that $0 \leq m \leq 3$.  If $0 \leq m \leq 1$, then by choosing $\mathbf{b} = (1)$ and $\mathbf{c} = (1)$, we see that $$\left|\sum_i b_i - \sum_i c_i - m\right| = |m| \leq 1$$  If $2 \leq m \leq 3$, then after choosing $\mathbf{b} = (1, 1)$ and $\mathbf{c} = ()$ we find that $$\left|\sum_i b_i - \sum_i c_i - m\right| = |2 - m| \leq 1$$  Thus, the basis case holds for $\mathbf{a} = (1, 1)$.
Now assume that $\mathbf{a} = (1, 2)$.  If $0 \leq m \leq 2$ then let $\mathbf{b} = (2)$ and $\mathbf{c} = (1)$.  We have $$\left|\sum_i b_i - \sum_i c_i - m\right| = |1 - m| \leq 1$$  Finally, if $m = 3$, then we choose $\mathbf{b} = (1, 2)$ and $\mathbf{c} = ()$ and observe that $$\left|\sum_i b_i - \sum_i c_i - m\right| = |3 - m| = 0 \leq 1$$  Hence, the basis case holds for both $\mathbf{a} = (1, 1)$ and $\mathbf{a} = (1, 2)$.
Now, let us assume that Claim 2 holds for $n$.  We need to show that it holds for $n + 1$.  Consider an integer $m$ such that $0 \leq m \leq n + 2$ and a sequence $\mathbf{a} = (a_1, \ldots, a_{n + 1})$ of length $n + 1$ with property (*).  Then $$m' = \left|m - a_{n + 1}\right| \leq n + 1$$ since $1 \leq a_{n + 1} \leq n + 1$.  By the inductive hypothesis, the sequence $\mathbf{a'} = (a_1, \ldots, a_n)$ can be split into subsequences $\mathbf{b'}$ and $\mathbf{c'}$ such that $$\left|\sum_i b_i' - \sum_i c_i' - m'\right| \leq 1$$
Now, either $m' = m - a_{n + 1}$ or $m' = a_{n + 1} - m$.  If $m' = m - a_{n + 1}$, then we have
\begin{align}
\left|\left(\sum_i b_i' + a_{n + 1}\right) - \sum_i c_i' - m\right| &= \left|\sum_i b_i' - \sum_i c_i' - m'\right| \leq 1
\end{align}
and the inductive case holds by letting $\mathbf{b} = (\mathbf{b'}, a_{n + 1})$ and $\mathbf{c} = \mathbf{c'}$.
On the other hand, if $m' = a_{n + 1} - m$ then we see that
\begin{align}
\left|\left(\sum_i c_i' + a_{n + 1}\right) - \sum_i b_i' - m\right| &= \left|\sum_i c_i' - \sum_i b_i' + a_{n + 1} - m\right| \\
                                                                 {} &=
\left|\sum_i b_i' - \sum_i c_i' - a_{n + 1} + m\right| \\
                                                                 {} &= \left|\sum_i b_i' - \sum_i c_i' - m'\right| \\
                                                                 {} &\leq 1
\end{align}
so the inductive case holds by letting $\mathbf{b} = (\mathbf{c'}, a_{n + 1})$ and $\mathbf{c} = \mathbf{b'}$.
