27th Putnam 1966

Problem B4

Given a set of (mn + 1) unequal positive integers, prove that we can either (1) find m + 1 integers biin the set such that bi does not divide bj for any unequal i, j, or (2) find n+1 integers ai in the set such that ai divides ai+1 for i = 1, 2, ... , n.



Given any a1 in the set, let f(a1) be the length of the longest sequence a1, a2, ... , ak taken from the set such that a1|a2, a2|a3, ... , ak-1|ak. If f(a1) > n, then we are done, so assume that for all a in the set, f(a) <= n. Thus f can only have n possible values (1, 2, ... , n). There are mn+1 members in the set, so there must be at least m+1 members b1, b2, ... , bm+1 with the same value of f, say h. Now we cannot have any one of these members divide another, for if bi|bj, then we could extend the sequence length h for bj to give a sequence length h+1 for bi (in which each element divides the next).

Comment: the proof is almost identical to that for the original Erdos-Szekeres result about increasing or decreasing sequences. If you are familiar with that result, the problem is trivial. If not it is hard.



27th Putnam 1966

(C) John Scholes
25 Jan 2002