A set of 19 numbers that are at most 93, and a set of 93 numbers that are at most 19, have equal sumsets If $x_1, x_2, ..., x_{19}$ are natural numbers lower or equal than 93 and $y_1, y_2, ..., y_{93}$ are natural numbers lower or equal than 19 then there is a non zero sum of some $x_i$ which is equal to sum of some $y_j$.
Any hints on how to prove this? I've been thinking about this for couple of days but still can't find a way to show that...
 A: As user Rebecca J. Stones pointed out in the comments, this is question A$4$ on the $1993$ Putnam exam. I will reproduce the solutions provided.

Let $x_1, x_2, \ldots, x_{19}$ be positive integers each of which is less than or equal to $93$. Let $y_1, y_2, \ldots, y_9$ be positive integers each of which is less than or equal to $19$. Prove that there exists a (nonempty) sum of some $x_i$ 's equal to a sum of some $y_j$ 's.

Solution 1. We move a pebble among positions numbered $-18,-17, \ldots, 0,1$, $2, \ldots, 93$, until it revisits a location. The pebble starts at position 0 . Thereafter, if the pebble is at position $t$, we move it as follows. If $t \leqslant 0$, choose some unused $x_i$, move the pebble to $t + x_i$, and then discard that $x_i$. If $t > 0$, choose some unused $y_j$, move the pebble to $t - y_j$, and then discard that $y_j$. Since $x_i \leqslant 93$ and $y_j \leqslant 19$, the pebble's position stays between $-18$ and $93$.
In order to continue this process until a location is revisited, we must show that there is always an unused $x_i$ or $y_j$ as needed. If $t \leqslant 0$ and a revisit has not yet occurred, then one $x_i$ has been used after visiting each nonpositive position except the current one, so the total number of $x_i$ 's used so far is at most $19 - 1 = 18$, and at least one $x_i$ remains. Similarly, if $t > 0$ and a revisit has not yet occurred, then one $y_j$ has been used after visiting each positive position except the current one, so the total number of $y_j$ 's used so far is at most $93 - 1 = 92$, and at least one $y_j$ remains.
Since there are only finitely many $x_i$ 's and $y_j$ 's to be used, the algorithm must eventually terminate with a revisit. The steps between the two visits of the same position constitute a sum of some $x_i$ 's equal to a sum of some $y_j$ 's.
Our next solution is similar to Solution 1, but we dispense with the algorithmic interpretation.
Solution 2. For the sake of generality, replace $19$ and $93$ in the problem statement by $m$ and $n$ respectively. Define $X_k = \sum_{i = 1}^k x_i$ and $Y_{\ell} = \sum_{j = 1}^{\ell} y_j$. Without loss of generality, assume $X_m \geqslant Y_n$. For $1 \leqslant \ell \leqslant n$, define $f(\ell)$ by
$$X_{f(\ell)} \leqslant Y_{\ell} < X_{f(\ell) + 1}$$
so $0 \leqslant f(\ell) \leqslant m$. Let $g(\ell) = Y_{\ell} - X_{f(\ell)}$. If $g(\ell)=0$ for some $\ell$, we are done. Otherwise,
$$g(\ell) = Y_{\ell} - X_{f(\ell)} < x_{f(\ell) + 1} \leqslant n,$$
so $0 < g(\ell) \leqslant n-1$ whenever $1 \leqslant \ell \leqslant n$. Hence by the Pigeonhole Principle, there exist $\ell_0 < \ell_1$ such that $g\left(\ell_0\right) = g\left(\ell_1\right)$. Then
$$\sum_{i = f\left(\ell_0\right) + 1}^{f\left(\ell_1\right)} 
x_i = X_{f\left(\ell_1\right)} - X_{f\left(\ell_0\right)} = Y_{\ell_1} - 
Y_{\ell_0} = \sum_{j = \ell_0 + 1}^{\ell_1} y_j$$
Solution 3 (based on an idea of Noam Elkies). With the same notation as in the previous solution, without loss of generality $X_m \geqslant Y_n$. If equality holds, we are done, so assume $X_m > Y_n$. By the Pigeonhole Principle, two of the $(m + 1)(n + 1)$ sums $X_i + Y_j(0 \leqslant i \leqslant m, 0 \leqslant j \leqslant n)$ are congruent modulo $X_m$, say
$$X_{i_1} + Y_{j_1} \equiv X_{i_2} + Y_{j_2} \quad\left(\bmod 
X_m\right).$$
But the difference
$$\left(X_{i_1} - X_{i_2}\right) + \left(Y_{j_1} - Y_{j_2}\right)\quad (1)$$
lies strictly between $-2X_m$ and $+2X_m$, so it equals $0$ or $\pm X_m$. Clearly $i_1 \neq i_2$; without loss of generality $i_1 > i_2$, so (1) equals $0$ or $X_m$. If $j_1 < j_2$, then ($1$) must be $0$, so $X_{i_1} -X_{i_2} = Y_{j_2} - Y_{j_1}$ are two equal subsums. If $j_1 > j_2$, then ($1$) must be $X_m$, and $Y_{j_1 } - Y_{j_2} = X_m - \left(X_{j_1} - X_{j_2}\right)$ are two equal subsums.
I will note that this took me quite awhile to write out.
