wu :: forums - Print Page


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

        general >> wanted >> Please help
        
(Message started by: Zoel on Feb 3^rd, 2004, 5:17pm)

Title: Please help
Post by Zoel on Feb 3^rd, 2004, 5:17pm

let a and b be positive numbers with
(1 /a )+(1 /b )=1, and let [x ] denote the largest integer that does not exceed the
number x. If neither a nor b can be written as the ratio of two integers, show that
each positive integer is either of the form [ma ]or [mb ]for some positive integer m .

I spent about a half hour boggling at this and I figured out that it's true, but I'm not sure at all why

Title: Re: Please help
Post by Hooie on Feb 3^rd, 2004, 6:28pm

:) This was for the Pomona College Math Talent search, right?

I figured out 3 of the questions, but unfortunately, this wasn't one of them. :( Sorry I can't help.

Title: Re: Please help
Post by towr on Feb 4^th, 2004, 12:12am

from (1 /a )+(1 /b )=1 we get a = b/(b-1) = 1 + 1/(b-1) (or alternatively b= a/(a-1) )

[forall]i[exists]m i = [lfloor]ma[rfloor] [vee] [exists]m i = [lfloor]mb[rfloor]
[forall]i[exists]m i < ma < i+1 [vee] [exists]m i < mb < i+1
[forall]i[exists]m i < ma < i+1 [vee] [exists]m i < m a/(a-1) < i+1
[forall]i[exists]m i/a < m < (i+1)/a [vee] [exists]m i(a-1)/a < m < (i+1)(a-1)/a
[forall]i[exists]m i/a < m < i/a+1/a [vee] [exists]m i - i/a < m < i - i/a - 1/a + 1
[forall]i[exists]m i/a < m < i/a+1/a [vee] [exists]m i/a + 1/a - 1 < i-m < i/a
[forall]i[exists]m i/a + 1/a - 1 < m < i/a [vee] i/a < m < i/a+1/a
[forall]i[exists]m i/a + 1/a - 1 < m < i/a+1/a
true

Title: Re: Please help
Post by Zoel on Feb 4^th, 2004, 2:04pm

yes it's for talent search, but out of UW Madison, not Pomona.
I've got pretty good answers for the other four, not perfect but hopefully okay

Title: Re: Please help
Post by Icarus on Feb 4^th, 2004, 5:55pm

on 02/04/04 at 00:12:11, towr wrote:

[forall]i[exists]m i = [lfloor]ma[rfloor] [vee] [exists]m i = [lfloor]mb[rfloor]
[forall]i[exists]m i < ma < i+1 [vee] [exists]m i < mb < i+1
[forall]i[exists]m i < ma < i+1 [vee] [exists]m i < m a/(a-1) < i+1
[forall]i[exists]m i/a < m < (i+1)/a [vee] [exists]m i(a-1)/a < m < (i+1)(a-1)/a
[forall]i[exists]m i/a < m < i/a+1/a [vee] [exists]m i - i/a < m < i - i/a - 1/a + 1
[forall]i[exists]m i/a < m < i/a+1/a [vee] [exists]m i/a + 1/a - 1 < i-m < i/a
[forall]i[exists]m i/a + 1/a - 1 < m < i/a [vee] i/a < m < i/a+1/a
[forall]i[exists]m i/a + 1/a - 1 < m < i/a+1/a
true

A good "B" effort, towr! It would be an "A" if only you hadn't got your proof backwards - starting with the conclusion and working to the known, instead of the other way around. Of course in this case the logic is reversable - each line is actually equivalent to the one before it, so to get a true proof, you need only reverse the order of the lines (otherwise it be a "D" or "F"). Or you could explicitly state the equivalence. By convention, Listing lines in order like this only means that each line follows from the one before, so when equivalence is needed, it must be stated.

I harp on this because it is a common problem among mathematical novices. Even many HS math teachers are not aware that starting with the conclusion and deriving a true statement does not actually prove anything. Since their understanding is flawed, there is no hope of their students comprehending what is necessary and why.

To correct this, and because I found this symbol-ridden logic hard to follow, here is another version of the same proof:

Note that since a, b > 0, then a = b/(b-1) > 1.
Let i be an arbitrary integer. Then there must exist an integer k in the half-open interval [ (i+1)/a - 1, (i+1)/a ). Since a > 1, i/a also lies within this interval.

if k [le] i/a, then

(i+1)/a - 1 [le] k [le] i/a,
(i+1)/a - i -1 [le] k - i [le] i/a - i,
(i+1)(1/a - 1) [le] k - i [le] i(1/a - 1),
(i+1)(-1/b) [le] k - i [le] i(-1/b),
i + 1 [ge] b(i - k) [ge] i.

Let m = i-k. Either b = (i + 1)/m, which is rational, or [lfloor]bm[rfloor] = i.

If i/a < k, then

i/a < k < (i+1)/a,
i < ka < (i+1).

Let m = k. Then [lfloor]ma[rfloor] = i.

In either case, if b (and thus also a) is not rational, every integer is expressible as either [lfloor]ma[rfloor] or [lfloor]mb[rfloor] for some integer m.

As a further result, if a and b are rational, then they share a common numerator n in reduced form, and an integer i is expressible as either [lfloor]ma[rfloor] or [lfloor]mb[rfloor] for some integer m if and only if n does not divide (i + 1).

Title: Re: Please help
Post by Eigenray on Feb 4^th, 2004, 11:32pm

I was going to wait until after February 5th, but whatever:
One can also do the following:
1) Show that {ma} and {mb} are disjoint.
2) Consider the numbers {ma : m positive integer}. How many are less than n?
3) How many of the numbers {ma} U {mb} are less than n? Call this s(n).
4) Now bound s(n) from above and below. Use the fact that a,b are irrational, and that s(n) is an integer, to find s(n) explicitly.

So how many of the numbers {ma} U {mb} fall in the interval [n, n+1) ?

The converse of this problem is also true. Suppose that x and y are such that every positive integer can be written uniquely as [mx] or [my] for some positive integer m. Then 1/x + 1/y = 1, and x,y are irrational.

Title: Re: Please help
Post by towr on Feb 5^th, 2004, 12:52am

on 02/04/04 at 17:55:37, Icarus wrote:

A good "B" effort, towr! It would be an "A" if only you hadn't got your proof backwards

It was neither an A nor B effort, it was a preliminary effort.
Aside from the fact it's backwards it's also somewhat incomplete. (Like in justifying jumping from i/a + 1/a - 1 < i-m < i/a to i/a < m < i/a+1/a and other little but crucial details)
And as you said, readability could be better..

Actually, reconsidering it. It isn't backwards.. I just proved that the conclusion had to be true using the premises as postulates
|- P -> Q <=> P |- Q <=> P |- true

Anyway this isn't an exam, and I had allready spent too much time on it (as I had to go somewhere..)

Title: Re: Please help
Post by Icarus on Feb 5^th, 2004, 9:21pm

I was not intending to be critical. I am sure you know the difference between this and a proof. But, as I said, there are many who do not. For example, a post in the 0.999... thread gave what one HS student claimed was the "proof" his teacher had demonstrated, but the calculation proffered suffered from exactly this problem.

Having a personal interest in the irradicating of such misconcepts, I felt I had to state the objection for the sake of those less-well educated, even though I knew you had not intended what you wrote as being a completed proof, but only a quick guide on how to find it.