wu :: forums - Print Page


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

        riddles >> medium >> Even and odd
        
(Message started by: pcbouhid on Jan 26^th, 2006, 10:43am)

Title: Even and odd
Post by pcbouhid on Jan 26^th, 2006, 10:43am

Let [z] mean the greatest integer less than or equal to z.

Find a positive real number X, such that [X^n] is an even number whenever n is even, and [X^n] is an odd number whenever n is odd.

Title: Re: Even and odd
Post by towr on Jan 26^th, 2006, 11:06am

I think you could [hide]solve any appropriate recurrence where
f(0) is even, f(1) is odd, and f(n) = a f(n-1) + b f(n-2) with a even and b odd
If you select the parameters with care carefull, you'll have f(n) = c₁ l₁ⁿ + c₂ l₂ⁿ with one of the terms being negligible.[/hide]

I'll pick [hide]5+sqrt(26)[/hide] if you want a definite answer.

Title: Re: Even and odd
Post by towr on Jan 26^th, 2006, 3:09pm

I'm not so sure about the number I gave now. Seems I overlooked a few things.
Maybe I'll try again later.

Title: Re: Even and odd
Post by Eigenray on Jan 26^th, 2006, 7:23pm

I remember thinking about this very problem before (was it on this site?). I'm not sure, but I don't think I ever got a solution that way -- it seems like it always does the opposite of what you want it to do. If you do get it to work out, please share.

But one can prove such an X exists. Start with the equation 3 < X < 4. Inductively, suppose n>1 and we are given the equation
3ⁿ < k_n < Xⁿ < k_n+1. (*_n)
Now, if f(x) = x^(n+1)/n, then f(k_n+1)-f(k_n) > f'(k_n) > k_n^1/n > 3,
so the interval [f(k_n), f(k_n+1)] must contain 3 consecutive integers. Let k_n+1 be the smallest integer in that interval of the same parity as n+1, namely,
k_n+1 = 2 ceil[f(k_n)/2], if n+1 is even,
= 2 ceil[(f(k_n)-1)/2] + 1, if n+1 is odd.
It follows that [k_n+1, k_n+1+1] is contained in [f(k_n), f(k_n+1)], i.e.,
(3ⁿ)^1/n < k_n^1/n < k_n+1^1/(n+1) < (k_n+1+1)^1/(n+1) < (k_n+1)^1/n, (**)
which means that the equation
3ⁿ⁺¹ < k_n+1 < Xⁿ⁺¹ < k_n+1+1 (*_n+1)
implies (*_n).
Now define X=3.21124734... to be the limit of the sequence k_n^1/n. Equation (**) shows this limit exists, and that for all n, (*_n) is satisfied:
[Xⁿ] = k_n == n mod 2.

[Editted typo in (*_n)]

Title: Re: Even and odd
Post by towr on Jan 29^th, 2006, 11:47am

on 01/26/06 at 19:23:39, Eigenray wrote:

I'm not sure, but I don't think I ever got a solution that way -- it seems like it always does the opposite of what you want it to do. If you do get it to work out, please share.

It turns out to be impossible that way. :(

Title: Re: Even and odd
Post by pcbouhid on Jan 30^th, 2006, 6:48am

The solution I have:

[hide]One example is ½(3+√17). How do we get this?

Consider the binomial equation x²-ax-b=0, with a odd, b even, 0 < b < a.

Let u be the positive root, and v be the negative root.

Create the sequence S as S(n) = u^n + v^n.

We have that S(1) = a and S(2) = a² + 2b

Notice that S(1) is odd and S(2) is odd. Now note that a = u+v and b = -uv, giving S(n) = a*S(n-1) + b*S(n-2).

This implies that S(n) is odd for all n > 0.

Next, by the nature of how a and b were restricted, we see that:
-1 < v < 0, because v=-b/u, and b < a < u.

Now, [u^n] = [S(n) – v^n],
so [u^n] = S(n) when n is odd and
[u^n] = S(n)-1 when n is even.

Therefore, u has the desired property.

As an example, pick a=3, b=2, u = ½(3+√17) [/hide]

Title: Re: Even and odd
Post by Barukh on Jan 30^th, 2006, 9:02am

Excellent! Straight from the Book! :D

Title: Re: Even and odd
Post by towr on Jan 30^th, 2006, 9:11am

Quote:

This implies that S(n) is odd for all n > 0.

Doh.. no wonder it went totally wrong for me. And it's so obvious when you say it..