43rd Putnam 1982

Problem B4

A set S of k distinct integers ni is such that ∏ ni divides ∏ (ni + m) for all integers m. Must 1 or -1 belong to S? If all members of S are positive, is S necessarily just {1, 2, ... , k}?

Solution

m is allowed to be negative, so we can use the weaker condition that ∏ ni ≥ ∏ (ni + m). Suppose neither 1 nor -1 is in S. Then taking m = 1 and -1 gives non-zero products. Moreover the product of their absolute values is ∏ |ni + 1| |ni - 1| = ∏ |ni2 - 1| < (∏ ni)2. So at least one of the absolute values is less than | ∏ ni | (and hence cannot be divisible by it). Contradiction.

Now consider the case where all members of S are positive. Let m be the smallest positive integer not in S. Then ∏ ni = | ∏ (ni - m) |, where we take the product over the members of S less than m. For any member x of S greater than m, we obviously have 0 < x - m < m. So if there are any such members, then ∏ ni > |∏ (ni - m) | (taking the products over all members of S). Contradiction. Hence S must be just 1, 2, ... , m - 1.

Of course, the question becomes more interesting if we restrict m to be positive.