wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> beatty sequences and inverse sum
        
(Message started by: kiochi on Jan 8^th, 2007, 11:46am)

Title: beatty sequences and inverse sum
Post by kiochi on Jan 8^th, 2007, 11:46am

Sort of a cool relationship.

let a and b be postive reals, show

Each integer occurs exactly once in the sequence [a],[b],[2a],[2b],... (where [] is floor)

if and only if

1/a +1/b = 1 with a,b irrational.

Title: Re: floor sequence and inverse sum
Post by Sameer on Jan 8^th, 2007, 1:44pm

It's called the Beatty Sequence

Title: Re: beatty sequences and inverse sum
Post by kiochi on Jan 8^th, 2007, 2:03pm

hmm so I guess this result is just "Beatty's theorem." I had fun proving it anyway when a friend brought it to me.

Title: Re: beatty sequences and inverse sum
Post by balakrishnan on Jan 10^th, 2007, 11:20am

Here is a proof.
https://nrich.maths.org/discus/messages/67613/70119.html?1152314870

Title: Re: beatty sequences and inverse sum
Post by kiochi on Jan 10^th, 2007, 11:27am

actually that's only one direction ;)

Title: Re: beatty sequences and inverse sum
Post by Barukh on Jan 11^th, 2007, 12:20am

A follow up: find the necessary and sufficient conditions for three real numbers a, b, c to cover the integers.

Title: Re: beatty sequences and inverse sum
Post by kiochi on Jan 11^th, 2007, 7:00am

on 01/11/07 at 00:20:13, Barukh wrote:

A follow up: find the necessary and sufficient conditions for three real numbers a, b, c to cover the integers.

Actually, I think I can prove that[hide] it is impossible for the beatty sequences of three positive reals, a,b, and c to partition the natural numbers.[/hide]

Maybe I'll hazzard a proof later today (when I have time), but if anyone beatts me to it that's fine, too.

Title: Re: beatty sequences and inverse sum
Post by kiochi on Jan 11^th, 2007, 2:56pm

on 01/11/07 at 00:20:13, Barukh wrote:

A follow up: find the necessary and sufficient conditions for three real numbers a, b, c to cover the integers.

Actually, here are the necessary and sufficient conditions: [hide]one of a,b,c is zero (w.l.o.g. assume it is c), then it's just the condition in the above theorem, namely, 1/a+1/b = 1, with a,b irrational iff their beatty sequences... btw only one direction of that theorem has been posted (linked) above... anyone want to do the other... actually this result sort of spoils it.[/hide]

Proof:

[hide]
Suppose that a,b,c are positive real numbers s.t. their beatty sequences partition the set of natural numbers, N. w.l.o.g. assume a<b<c. (clearly they can't be equal). Clear also is that 1<a<2<b, 3<c, and no two of a,b,c can be rational (in fact the same arguments used in a proof, or at least my proof, of B's Theorem show that none of them are rational).
Let S_a={[na]:n in N}, and analagously define S_b and S_c.

Note that, for any positive integer n, [ka]<=n iff ka<n +1 iff k<(n+1)/a, so there are k=[(n+1)/a] elements of S_a less than or equal to n (and similarly for S_b and S_c). This shows that the density d(S_a) = lim_n-->infty [(n+1)/a]/n = 1/a. Likewise, the densities of S_b and S_c are 1/b and 1/c, respectively. Now, since they partition N, their densiities must add to the density of N, i.e.

1/a + 1/b +1/c = 1. (look familiar?)

Now as mentioned above c>3, so [c]>=3.

Set k = |{s in S_b : s<[c]}|.

Then |{s in S_a : s<[c]}| = [c]-k, so
([c]-k)a<[c] (in particular, note that 1/a>([c]-k)/[c]), so [([c]-k)a]<[c]-1, and [([c]-k+1)a]>[c], so
[c]>[([c]-k)a]=[([c]-k+1)a-a]>=[c]+1-2 (as a<2)
So [([c]-k)a]=[c]-1
This implies [kb]<[c]-1, so kb<[c]-1, so 1/b>k/([c]-1). Of course c<[c]+1, so 1/c>1/([c]+1). Adding these, we get an inequality:

1 = 1/a+1/b+1/c >([c]-k)/[c]+k/([c]-1)+1/([c]+1)

Multiplying through by the denoms and simplifying some things and getting everything on one side, we see this is equiv. to:
0>k[c]-[c]+[c]^2 +[c], now k,c>1, so this is all >[c]^2+[c] ... but [c]>1!!!
Contradiction!
[/hide]