27th Putnam 1966

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

Solution

Given any a₁ in the set, let f(a₁) be the length of the longest sequence a₁, a₂, ... , a_k taken from the set such that a₁|a₂, a₂|a₃, ... , a_k-1|a_k. If f(a₁) > 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 b₁, b₂, ... , b_m+1 with the same value of f, say h. Now we cannot have any one of these members divide another, for if b_i|b_j, then we could extend the sequence length h for b_j to give a sequence length h+1 for b_i (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
jscholes@kalva.demon.co.uk
25 Jan 2002