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
Let's try to pick a set that doesn't have any members m,n such that 2/3 < m/n < 3/2.
The lowest integer than we can select is 1.
Once 1 is in the set, the next integer we can select for the set must be greater than 1*(3/2). The lowest such integer is 2.
Once 2 is in the set, the next integer we can select for the set must be greater than 2*(3/2). The lowest such integer is 4.
Similarly, we have room in the set for 7, 11, 17, 26, 40 and then 61.
But now we are stuck. There are no integers that are greater than 61*(2/3) and less than 92. So no more than 9 integers can be selected such that 2/3 < m/n < 3/2 for any m,n in the set. So picking 10 integers is sufficient to guarantee at least one pair m/n where 2/3 ≤ m/n ≤ 3/2.
Extra Credit:
If we are allowed to pick any real numbers between 1 and 91, inclusive, then picking 13 numbers is required to guarantee that at least one pair m/n where 2/3 ≤ m/n ≤ 3/2. This is because (3/2)^11 ~= 86.5, so we can pick 11 numbers after 1 without exceeding 91. (3/2)^12 ~= 129.7, so we cannot pick 12 numbers after 1 without exceeding 91.
Edited on September 7, 2009, 7:26 pm
Same solution, but simpler (spoiler)
