Author |
Topic: Please help (Read 8772 times) |
|
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
|
 |
Re: Please help
« Reply #1 on: Feb 3rd, 2004, 6:28pm » |
 Quote  Modify
|
 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
|
|
Re: Please help
« Reply #2 on: Feb 4th, 2004, 12:12am » |
Quote Modify
|
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
|
|
Re: Please help
« Reply #3 on: Feb 4th, 2004, 2:04pm » |
Quote Modify
|
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
|
|
Re: Please help
« Reply #4 on: Feb 4th, 2004, 5:55pm » |
Quote Modify
|
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
|
|
Re: Please help
« Reply #5 on: Feb 4th, 2004, 11:32pm » |
Quote Modify
|
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
|
|
Re: Please help
« Reply #6 on: Feb 5th, 2004, 12:52am » |
Quote Modify
|
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
|
|
Re: Please help
« Reply #7 on: Feb 5th, 2004, 9:21pm » |
Quote Modify
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print