I need some proof...
-
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design. -
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.Shouldnt the following work??? Say:
i) x * y = n ii) x < sqrt(n) iii) y < sqrt(n) => i)*ii): x*y < sqrt(n)*sqrt(n) => x*y < n This is a contradiction to i) => your assumption q.e.d.Cheers Martin "Situation normal - all fu***d up" Illuminatus! http://www.martin-haesemeyer.de -
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.Sorry for the multiple editings of my first post, but the parser seems to get confused by to many ( * etc. Could this be true? Cheers Martin "Situation normal - all fu***d up" Illuminatus! http://www.martin-haesemeyer.de
-
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.Take a look at the link below: http://www.picciotto.org/math-ed/func-diag/applets/fd-ellipse.html[^] You can scale the function y=1/x to y=n/x by replacing the upper point 1 by sqrt(n). /moliate
The corners of my eyes catch hasty, bloodless motion - a mouse? Well, certainly a peripheral of some kind.
Neil Gaiman - Cold Colours
-
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design. -
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) => Assume by contradiction y<=n^(1/2), three cases: 1 - xy. y*y=n^(1/2), three cases: 1 - x=n^(1/2). 2 - x=y. x*x=x*y=n x*x=x*y=y*y Therefore y=n^(1/2), contradicting y>n^(1/2). 3 - x>y. y*yn^(1/2). All sqrt legal because x,y,n are positives. It's long, but formal.
-
Shouldnt the following work??? Say:
i) x * y = n ii) x < sqrt(n) iii) y < sqrt(n) => i)*ii): x*y < sqrt(n)*sqrt(n) => x*y < n This is a contradiction to i) => your assumption q.e.d.Cheers Martin "Situation normal - all fu***d up" Illuminatus! http://www.martin-haesemeyer.deMartin, I don't mean to deride you or anything; but your proof is just the same as mine, except where you've used inequalities, I've replaced them with constants. On the bright side of things, if you think what you've posted (and hence what I've posted) is acceptable as a formal proof, then I must be on the right path. :) BTW, nice sig. Where did you get it? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Proof by means of Induction would probably be considered the best IMO, but much more work. But who am I to say? :) I rated this article 2 by mistake. It deserves more. I wanted to get to the second page... - vjedlicka 3:33 25 Nov '02
leppie wrote: Induction How, man? I've been racking my brains since I saw your post, but I can't even think of where to start. Any help? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) => Assume by contradiction y<=n^(1/2), three cases: 1 - xy. y*y=n^(1/2), three cases: 1 - x=n^(1/2). 2 - x=y. x*x=x*y=n x*x=x*y=y*y Therefore y=n^(1/2), contradicting y>n^(1/2). 3 - x>y. y*yn^(1/2). All sqrt legal because x,y,n are positives. It's long, but formal.
Thanks for the reply, but your post is rather confusing. What in tarnation does the fourth line mean? The fifth line in your post says "by contradiction". Contradiction of what? Maybe the reason I can't understand your proof is that it's nearly 1 AM here. :Vikram stifles a yawn: I'll look into it tomorrow. Could you give me a more coherent proof, please? Preferably using "sqrt(n)" instead of n^(1/2) ? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Martin, I don't mean to deride you or anything; but your proof is just the same as mine, except where you've used inequalities, I've replaced them with constants. On the bright side of things, if you think what you've posted (and hence what I've posted) is acceptable as a formal proof, then I must be on the right path. :) BTW, nice sig. Where did you get it? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
Vikram Punathambekar wrote: Martin, I don't mean to deride you or anything; but your proof is just the same as mine, except where you've used inequalities, I've replaced them with constants. Yup, I realised that, too... :-O Vikram Punathambekar wrote: BTW, nice sig. Where did you get it? It's from the Illuminatus! trilogy by Robert Shea and Robert Anton Wilson. Really nice book, really strange thoug. Cheers Martin "Situation normal - all fu***d up" Illuminatus! http://www.martin-haesemeyer.de
-
Thanks for the reply, but your post is rather confusing. What in tarnation does the fourth line mean? The fifth line in your post says "by contradiction". Contradiction of what? Maybe the reason I can't understand your proof is that it's nearly 1 AM here. :Vikram stifles a yawn: I'll look into it tomorrow. Could you give me a more coherent proof, please? Preferably using "sqrt(n)" instead of n^(1/2) ? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
Vikram Punathambekar wrote: What in tarnation does the fourth line mean? The x < n^(1/2) <=> y > n^(1/2) is to sided - two separate proofs needed. => means we prove first direction - if x < n^(1/2) then y > n^(1/2). Vikram Punathambekar wrote: The fifth line in your post says "by contradiction". Contradiction of what? Assuming by contradiction is standard proof technique - you assume something wrong and contradict the assumption, thus the opposite of it is correct. The technique sometimes worded also: by way of contradiction assume that, or assuming the contrary. Vikram Punathambekar wrote: Could you give me a more coherent proof, please? The proof is formal and very mathy - minimal words:) I'll try to humanize it later.
-
leppie wrote: Induction How, man? I've been racking my brains since I saw your post, but I can't even think of where to start. Any help? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) Say: f(n) = x - n^(1/2) and g(n) = y - n^(1/2), now we need to prove f(n) < g(n) for all n > 0. But we know f(n) = x + y - n^(1/2) - y and then f(n) = x - y - g(n), so f(n) + g(n) = x - y, which is independant of n. Thus we can declare n constant, but i wont. This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1. Now with induction, rewrite f(n) as f(x) = x- n^(1/2), and g(n) as g(y) = y - n^(1/2). Now prove f(1) < g(n/1): 1 - n^(1/2) < n/1 - n^(1/2) ===> 1 < n/1 thus TRUE for n > 1 Now assume f(k) < g(n/k) TRUE, and prove f(k + 1) < g(n/(k + 1)): So from induction assumption (k + 1) - n^(1/2) < n/(k + 1) - n^(1/2) k + 1 < n/(k + 1) So for k + 1 < 0 ===> 1 > n and is not allowed. For k + 1 > 0 ===> 1 < n thus TRUE. So we can similarly show the reverse is true for values of 0 < n < 1 where f(x) > g(y). This shows that If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) PS: I hope this is the proper formal way. I'll ask my lecturer on Tuesday :) I rated this article 2 by mistake. It deserves more. I wanted to get to the second page... - vjedlicka 3:33 25 Nov '02
-
Vikram Punathambekar wrote: What in tarnation does the fourth line mean? The x < n^(1/2) <=> y > n^(1/2) is to sided - two separate proofs needed. => means we prove first direction - if x < n^(1/2) then y > n^(1/2). Vikram Punathambekar wrote: The fifth line in your post says "by contradiction". Contradiction of what? Assuming by contradiction is standard proof technique - you assume something wrong and contradict the assumption, thus the opposite of it is correct. The technique sometimes worded also: by way of contradiction assume that, or assuming the contrary. Vikram Punathambekar wrote: Could you give me a more coherent proof, please? The proof is formal and very mathy - minimal words:) I'll try to humanize it later.
Felix Gartsman wrote: Assuming by contradiction is standard proof technique - you assume something wrong and contradict the assumption, thus the opposite of it is correct. Well, I know that :-O , sorry if I sounded silly. But proof by contradiction goes like this. You're supposed to prove a statement S. You assume S is not true. Then you derive something from !S (or ~S to the more mathematical mind) that is clearly false. Now you say "this is 'cos we made a mistake in assuming !S to be true- so, S must be true". I repeat (maybe in ignorance): in the fifth line, you simply state
y<sqrt(n)which assumption does it contradict? The only assumption you've made so far is thatx<sqrt(n). I can't see how this assumption directly contradicts the statement in the fifth line. Please explain. BTW, do you think the proof I gave in my original post is accpetable? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design. -
Felix Gartsman wrote: Assuming by contradiction is standard proof technique - you assume something wrong and contradict the assumption, thus the opposite of it is correct. Well, I know that :-O , sorry if I sounded silly. But proof by contradiction goes like this. You're supposed to prove a statement S. You assume S is not true. Then you derive something from !S (or ~S to the more mathematical mind) that is clearly false. Now you say "this is 'cos we made a mistake in assuming !S to be true- so, S must be true". I repeat (maybe in ignorance): in the fifth line, you simply state
y<sqrt(n)which assumption does it contradict? The only assumption you've made so far is thatx<sqrt(n). I can't see how this assumption directly contradicts the statement in the fifth line. Please explain. BTW, do you think the proof I gave in my original post is accpetable? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.Vikram Punathambekar wrote: repeat (maybe in ignorance): in the fifth line, you simply state y<sqrt(n) which assumption does it contradict? It is the false assumption. We assume as fact that x<sqrt(n) and contradictury assume that y<sqrt(n). Then we show that those assumptions (together with xy=n) contradict each other, and since only y<sqrt(n) is additional assumption not from question it must be false. Vikram Punathambekar wrote: BTW, do you think the proof I gave in my original post is accpetable? I'll answer separatelly so I could quote.
-
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.Vikram Punathambekar wrote: Let x and y be factors of n such that xy=n ----- (1) Assume that x0 . Why you assume this? What if x=n,y=1? Although it's minor end cases, you wanted formality. Why y+d=sqrt(n), d>0? Did you mean x,y<sqrt(n)? If so you must contradictury assume y<=sqrt(n) and then d can be zero! Vikram Punathambekar wrote: We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=n From previous, d=0 and c=x and no contradiction. You didn't correctly made ~(y>sqrt(n)).
-
If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) Say: f(n) = x - n^(1/2) and g(n) = y - n^(1/2), now we need to prove f(n) < g(n) for all n > 0. But we know f(n) = x + y - n^(1/2) - y and then f(n) = x - y - g(n), so f(n) + g(n) = x - y, which is independant of n. Thus we can declare n constant, but i wont. This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1. Now with induction, rewrite f(n) as f(x) = x- n^(1/2), and g(n) as g(y) = y - n^(1/2). Now prove f(1) < g(n/1): 1 - n^(1/2) < n/1 - n^(1/2) ===> 1 < n/1 thus TRUE for n > 1 Now assume f(k) < g(n/k) TRUE, and prove f(k + 1) < g(n/(k + 1)): So from induction assumption (k + 1) - n^(1/2) < n/(k + 1) - n^(1/2) k + 1 < n/(k + 1) So for k + 1 < 0 ===> 1 > n and is not allowed. For k + 1 > 0 ===> 1 < n thus TRUE. So we can similarly show the reverse is true for values of 0 < n < 1 where f(x) > g(y). This shows that If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) PS: I hope this is the proper formal way. I'll ask my lecturer on Tuesday :) I rated this article 2 by mistake. It deserves more. I wanted to get to the second page... - vjedlicka 3:33 25 Nov '02
leppie wrote: PS: I hope this is the proper formal way. I'll ask my lecturer on Tuesday It is formal, but I don't see how it proves what you need (I'm before breakfast, so I might missed it). x,y,n are constants and you treat them as parameters, you don't use xy=n or x<sqrt(n).
-
If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) Say: f(n) = x - n^(1/2) and g(n) = y - n^(1/2), now we need to prove f(n) < g(n) for all n > 0. But we know f(n) = x + y - n^(1/2) - y and then f(n) = x - y - g(n), so f(n) + g(n) = x - y, which is independant of n. Thus we can declare n constant, but i wont. This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1. Now with induction, rewrite f(n) as f(x) = x- n^(1/2), and g(n) as g(y) = y - n^(1/2). Now prove f(1) < g(n/1): 1 - n^(1/2) < n/1 - n^(1/2) ===> 1 < n/1 thus TRUE for n > 1 Now assume f(k) < g(n/k) TRUE, and prove f(k + 1) < g(n/(k + 1)): So from induction assumption (k + 1) - n^(1/2) < n/(k + 1) - n^(1/2) k + 1 < n/(k + 1) So for k + 1 < 0 ===> 1 > n and is not allowed. For k + 1 > 0 ===> 1 < n thus TRUE. So we can similarly show the reverse is true for values of 0 < n < 1 where f(x) > g(y). This shows that If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) PS: I hope this is the proper formal way. I'll ask my lecturer on Tuesday :) I rated this article 2 by mistake. It deserves more. I wanted to get to the second page... - vjedlicka 3:33 25 Nov '02
Hey, Leppie! Your "proof" seems brilliant and absurd at the same time (sorry, no offense meant). I've outlined a few issues with your proof, all of which have to be analyzed independantly: #1 You say f(n)=x-sqrt(n) and g(n)=y-sqrt(n). Err...why do you say we have to prove f(n)<g(n) ? Where does that lead us? For all you know, this statement might be right yet both of them could be less than sqrt(n). And what if they are both equal, as in the case of x=y=3,n=9? #2 Glaring error in the very next step. You say f(n)=x+y-sqrt(n)+y. Correct. The next step is wrong. You write f(n)=x-y-g(n), while it should actually be f(n)=x-y+g(n). Therefore, f(n)-g(n)=x-y and not f(n)+g(n)=x-y. #3 Whaddaya mean by saying "We can declare n constant" ? #4 From issue #2, it follows that the statement "This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1." is ^probably^ wrong too. The stuff coming after this is correct, as far as I can see. So you have successfully proved that f(n)<g(n), that is, x-sqrt(n) < y-sqrt(n) . From this, it's obvious that x<y. SO WHAT? You have tied up only x and y. There is absolutely no mention of sqrt(n) here. IMPORTANT: I really appreciate your help in this matter, helping somebody you've never seen or don't even know well. If in the above post I sound ungrateful anywhere, please note that I did not mean to do so. I still would like you to give me a more solid proof, if possible, with your lecturer's help. All the same, please check out the proof that I have given in the original post. The thread link is http://www.codeproject.com/lounge.asp?msg=483741&mode=all&userid=55714#xx483741xx . Don't check the one that was delivered to you by mail. It contains a few small errors that have been changed now. You see, it is simple and straightforward IMHO, but I don't know if it can be accepted by a bunch of nerdy mathematicians. Thanx for your help, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Hey, Leppie! Your "proof" seems brilliant and absurd at the same time (sorry, no offense meant). I've outlined a few issues with your proof, all of which have to be analyzed independantly: #1 You say f(n)=x-sqrt(n) and g(n)=y-sqrt(n). Err...why do you say we have to prove f(n)<g(n) ? Where does that lead us? For all you know, this statement might be right yet both of them could be less than sqrt(n). And what if they are both equal, as in the case of x=y=3,n=9? #2 Glaring error in the very next step. You say f(n)=x+y-sqrt(n)+y. Correct. The next step is wrong. You write f(n)=x-y-g(n), while it should actually be f(n)=x-y+g(n). Therefore, f(n)-g(n)=x-y and not f(n)+g(n)=x-y. #3 Whaddaya mean by saying "We can declare n constant" ? #4 From issue #2, it follows that the statement "This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1." is ^probably^ wrong too. The stuff coming after this is correct, as far as I can see. So you have successfully proved that f(n)<g(n), that is, x-sqrt(n) < y-sqrt(n) . From this, it's obvious that x<y. SO WHAT? You have tied up only x and y. There is absolutely no mention of sqrt(n) here. IMPORTANT: I really appreciate your help in this matter, helping somebody you've never seen or don't even know well. If in the above post I sound ungrateful anywhere, please note that I did not mean to do so. I still would like you to give me a more solid proof, if possible, with your lecturer's help. All the same, please check out the proof that I have given in the original post. The thread link is http://www.codeproject.com/lounge.asp?msg=483741&mode=all&userid=55714#xx483741xx . Don't check the one that was delivered to you by mail. It contains a few small errors that have been changed now. You see, it is simple and straightforward IMHO, but I don't know if it can be accepted by a bunch of nerdy mathematicians. Thanx for your help, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
Vikram Punathambekar wrote: Your "proof" seems brilliant and absurd at the same time I have found my new sig :) I thought about it again after I posted it, and realised there are some holes. This time i'll do it on paper instead on keyboard. :) But I'll ask him tomorrow morning and post the findings tomorrow night, or later tonite if I get a proper proof. Later then :) Hey leppie! Your "proof" seems brilliant and absurd at the same time - Vikram Punathambekar 28 Apr '03
-
Vikram Punathambekar wrote: repeat (maybe in ignorance): in the fifth line, you simply state y<sqrt(n) which assumption does it contradict? It is the false assumption. We assume as fact that x<sqrt(n) and contradictury assume that y<sqrt(n). Then we show that those assumptions (together with xy=n) contradict each other, and since only y<sqrt(n) is additional assumption not from question it must be false. Vikram Punathambekar wrote: BTW, do you think the proof I gave in my original post is accpetable? I'll answer separatelly so I could quote.
Your post is all mixed up, undoubtedly due to using < improperly. Please repost so I can understand. Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Vikram Punathambekar wrote: Let x and y be factors of n such that xy=n ----- (1) Assume that x0 . Why you assume this? What if x=n,y=1? Although it's minor end cases, you wanted formality. Why y+d=sqrt(n), d>0? Did you mean x,y<sqrt(n)? If so you must contradictury assume y<=sqrt(n) and then d can be zero! Vikram Punathambekar wrote: We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=n From previous, d=0 and c=x and no contradiction. You didn't correctly made ~(y>sqrt(n)).
Well, I had realized that my original proof had a few typos. I have corrected them now. You should be able to see them at http://www.codeproject.com/lounge.asp?msg=483741&mode=all&userid=55714#xx483741xx Sorry for the trouble... and thanks for your help :-D Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.