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.
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
Now, consider the the following claim about sequences with property (*).
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'}$.