Determine minimum value of P, such that for any arbitrary subset S’ consisting of precisely P distinct positive integers chosen from the set S = {1,2,3,4,.....,90, 91}, there exists two positive integers m and n each belonging to S’, such that:

2/3 ≤ m/n ≤ 3/2

The solution is P=10 and it is proven below:

First look at the 9 element subsets S'={1,2,4,7,11,17,26,40,x} with x in the interval [61,91].  Now for any of these subsets there does not exist a pair m,n in S' for which 2/3<=m/n<=3/2.  Thus P can not be 9.  Furthermore these are the only 9 element subsets of S that have this property because it is easy to see that no matter what value you choose for x in [61,91] you can not replace any element of S' without either simply replacing x with another value in [61,91] or creating a pair m,n with 2/3<=m/n<=3/2.  Also since any subset of these S' also have this property then P can not be less than or equal to 9.  Thus the first possible value of P is 10.

Now for P=10 we need to try and find an S' with the above property.  This can only be done by adding an element to one of the subsets {1,2,4,7,11,17,26,40,x}.  For for any value x in [61,91] you can not add another element without creating a pair m,n for which 2/3<=m/n<=3/2, thus P=10 is the minimal value.

Posted by Daniel on 2009-09-07 14:28:42