Let $X = \{x_1, x_2, \ldots, x_m\}$ be a set of $m$ positive integers, all less than or equal to $n$, and let $Y = \{y_1, y_2, \ldots, y_n\}$ be a set of $n$ positive integers, all less than or equal to $m$. Prove that there is a nonempty subset of $X$ and a nonempty subset of $Y$ with the same sum.
The ''informal'' solution given was: Imagine that the elements of $X$ are white stones, with weights $x_1,x_2,\ldots,x_m$, and that the elements of $Y$ are black stones, with weights $y_1,y_2,\ldots,y_n$. We also imagine a large balance-type scale, with two pans balancing across a fulcrum. Our goal is to put some number of white stones in the left pan and some number of black stones in the right pan, so that the two sides balance.
We use what is essentially a “greedy” algorithm: start by placing a white stone in the left pan, and then at each step, add a stone to whichever side is lighter, and keep doing this until we run out of stones. Either at some intermediate point the scales will be in balance (in which case we’re done), or we’ll run out of stones. But the bounds on the weights of the individual stones mean that the scale can never be out-of-balance by more than $n$ on the left side or by more than $m-1$ on the right side. (It can never be out of balance by $m$ on the right, since we started with a white stone in the left pan.) Since there are $m+n$ total stones and only $m+n-1$ different ways that the scale can be out of balance, we may conclude by the Pigeonhole Principle that if we run out of stones, the scale must have been out of balance by the same amount at two different times. But this means that all the stones that we added between these two times must balance evenly, thus solving the problem.
How does the scale balancing twice evenly solve the problem?
What has happened is that you've had $A$ as one side's total and $B$ as the other side's total, where $A = B + w$. After adding more stones as described, you have once again arrived at $C$ and $D$, where $C = D + w$. In particular, the stones that were added to the former side have weight $C-A$, and the stones added to the latter side have weight $D-B$.
But $C-A = (D+w) - (B+w) = D-B$, which means those two groups of stones -- the ones added to the former side, and the ones added to the latter side -- have the same total weight, which means that they furnish a solution to the problem at hand.