Given a sequence of 19 positive (not necessarily distinct) integers not greater than 93, and a set of 93 positive (not necessarily distinct) integers not greater than 19. Show that we can find non-empty subsequences of the two sequences with equal sum.

**Solution**

*Moderately hard. It is not clear how to proceed.*

We establish the general case for 0 < x_{1} ≤ x_{2} ≤ ... ≤ x_{m} ≤ n, 0 < y_{1} ≤ y_{2} ≤ ... ≤ y_{n} ≤ m ≤ n.

Let a_{h} = x_{1} + x_{2} + ... + x_{h}, b_{k} = y_{1} + y_{2} + ... + y_{k}. Suppose that a_{m} ≤ b_{n} (if not, we can just reverse the roles of x, a and y, b in what follows). For each i we have b_{n} ≥ a_{m} ≥ a_{i}, so we may define f(i) as the smallest j such that b_{j} ≥ a_{i}. Now consider the set {b_{f(1)} - a_{1}, b_{f(2)} - a_{2}, ... , b_{f(m)} - a_{m}}. If any element is zero, then we are done, so we may assume that all elements are ≥ 1. Each element must be less than m, because if b_{f(i)} ≥ a_{i} + m, then b_{f(i)-1} >= a_{i}, contradicting the minimality of f(i). So we have a set of m elements drawn from {1, 2, ... , m-1}. Hence there must be two elements, b_{f(r)} - a_{r} and b_{f(s)} - a_{s}, which are equal. Assume r < s, then b_{f(s)-f(r)} = a_{s-r}.

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998