wu :: forums - Print Page


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

        riddles >> medium >> Consider The Function, Get The Values
        
(Message started by: K Sengupta on Jun 27^th, 2007, 7:43am)

Title: Consider The Function, Get The Values
Post by K Sengupta on Jun 27^th, 2007, 7:43am

g is a function possessing the domain and range of the positive integers satisfying:

(1) g(p+1) > g(p);

(2) g(g(p)) = 3p

Analytically determine all possible values that g(955) can take.

Title: Re: Consider The Function, Get The Values
Post by pex on Jun 27^th, 2007, 7:50am

A quick clarification: is "range" supposed to be "codomain"? Otherwise, no such function exists: an increasing function with domain and range the positive integers has to have g(p) = p. Then g(1) = 1 and by your second rule, g(1) = 3 - contradiction.

Title: Re: Consider The Function, Get The Values
Post by pex on Jun 27^th, 2007, 8:09am

Assuming that this is the case:

[hideb]I ruled out g(1) = 1 above. Let g(1) = k > 1. Then g(k) = 3. As 1 < k, by the monotonicity condition, we must have g(1) < g(k) => k < 3. Thus, k = 2.

This forces the following values: g(1) = 2; g(2) = 3; g(3) = 6; g(6) = 9; g(9) = 18; g(18) = 27; g(27) = 54; g(54) = 81; g(81) = 162; g(162) = 243; g(243) = 486; g(486) = 729; g(729) = 1458; g(1458) = 2187.

Notice that 1458 - 729 = 2187 - 1458. Again, by monotonicity, we must have g(p) = p + 729 for all 729 < p < 1458. In particular, g(955) = 1684.[/hideb]

Nice problem!

Edit: stupid smilies...

Title: Re: Consider The Function, Get The Values
Post by peoplepower on Jul 29^th, 2012, 10:06am

Note that if 0 <= k<2*3^m, then g(3^m+k)=(2*3^m+k)[k<3^m]+(3^m+1+3k)[k>=3^m] (using Iverson brackets), following a proof by induction on m.