IMO 1978 SL 8

Origin: GBR

Problem

Let S be the set of all the odd positive integers that are not multiples of 5 and that are less than 30m, m being an arbitrary positive integer. What is the smallest integer k such that in any subset of k integers from S there must be two different integers, one of which divides the other?

Solution

Take the subset {ai} = {1, 7, 11, 13, 17, 19, 23, 29, . . ., 30m −1} of S con- taining all the elements of S that are not multiples of 3. There are 8m such elements. Every element in S can be uniquely expressed as 3tai for some i and t \geq0. In a subset of S with 8m + 1 elements, two of them will have the same ai, hance one will divide the other. On the other hand, for each i = 1, 2, . . . , 8m choose t \geq0 such that 10m < bi = 3tai < 30m. Then there are 8m bi’s in the interval (10m, 30m), and the quotient of any two of them is less than 3, so none of them can divide any other. Thus the answer is 8m.