wu :: forums    general    wanted (Moderators: Icarus, Eigenray, towr, ThudnBlunder, Grimbal, SMQ, william wu)    Please help « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
Zoel
Newbie

Gender:
Posts: 15

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
 IP Logged
Hooie
Newbie

Gender:
Posts: 29

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.
 « Last Edit: Feb 3rd, 2004, 6:29pm by Hooie » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730

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

 « Last Edit: Feb 4th, 2004, 12:12am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Zoel
Newbie

Gender:
Posts: 15

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
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863

on Feb 4th, 2004, 12:12am, 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).
 « Last Edit: Feb 4th, 2004, 6:12pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948

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.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730

on Feb 4th, 2004, 5:55pm, 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..)
 « Last Edit: Feb 5th, 2004, 3:46pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863

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.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis => wanted   - psychology   - chinese « Previous topic | Next topic »