Author |
Topic: A Smallest Value Puzzle (Read 1047 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
A Smallest Value Puzzle
« on: Mar 18th, 2009, 1:03am » |
 Quote  Modify
|
Find the smallest value of m, such that for any m positive integers chosen from the set S = {1,2,3,4,....., ,90, 91}, there exists two positive integers x and y each belonging to S, such that:
2/3 <= x/y <= 3/2
|
| « Last Edit: Mar 18th, 2009, 1:33am by K Sengupta » |
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: A Smallest Value Puzzle
« Reply #1 on: Mar 18th, 2009, 1:45am » |
Quote Modify
|
on Mar 18th, 2009, 1:03am, K Sengupta wrote:Find the smallest value of m, such that for any m positive integers chosen from the set S = {1,2,3,4,....., ,90, 91}, there exists two positive integers x and y each belonging to S, such that:
2/3 <= x/y <= 3/2 |
|
I think the greedy approach works here.
| hidden: | Alternatively, we find the largest n such that n positive integers exist in S with all quotients greater than 3/2 (or smaller than 2/3). Then m = n + 1.
Let tn be the smallest possible value of the largest number in a set of n positive integers with this property. Obviously, t1 = 1 and tn+1 = 1 + floor( (3/2) * tn ). Iterating, we find t9 = 61 < 91 < 92 = t10.
Thus, the answer to the original question is m = 10, and a set with n = 9 integers from S that proves that m > 9 is { t1, ..., t9 } = { 1, 2, 4, 7, 11, 17, 26, 40, 61 }. |
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Smallest Value Puzzle
« Reply #2 on: Mar 18th, 2009, 1:56am » |
Quote Modify
|
I guess I'm ten minutes too late. I had the same thoughts..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print