### 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.

Solution

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.

(C) John Scholes
jscholes@kalva.demon.co.uk
25 Jan 2002