All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Minimum Value With Ratio (Posted on 2009-09-07) Difficulty: 3 of 5
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

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Same solution, but simpler (spoiler) Comment 2 of 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
  Posted by Steve Herman on 2009-09-07 16:16:13

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information