wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> A Smallest Value Puzzle
        
(Message started by: K Sengupta on Mar 18^th, 2009, 1:03am)

Title: A Smallest Value Puzzle
Post by K Sengupta on Mar 18^th, 2009, 1:03am

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

Title: Re: A Smallest Value Puzzle
Post by pex on Mar 18^th, 2009, 1:45am

on 03/18/09 at 01:03:48, K Sengupta wrote:

I think the greedy approach works here.

[hideb]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 t_n be the smallest possible value of the largest number in a set of n positive integers with this property. Obviously, t₁ = 1 and t_n+1 = 1 + floor( (3/2) * t_n ). Iterating, we find t₉ = 61 < 91 < 92 = t₁₀.

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 { t₁, ..., t₉ } = { 1, 2, 4, 7, 11, 17, 26, 40, 61 }.[/hideb]

Title: Re: A Smallest Value Puzzle
Post by towr on Mar 18^th, 2009, 1:56am

I guess I'm ten minutes too late. I had the same thoughts..