Hrmm, i dunno about this.
Let x,y be your two numbers. So there are |x-y| possible "correct" guesses (a "correct" guess being one that falls between x and y).
Let z be the set from which i'm randomly picking a number n. This number can be anything (1, pi, 2^.5, e^i*pi, etc). So there's an infinite set of numbers from which i'm choosing one member. (I'm not going to get in to the infiniteness of this infinity, as it's been too many years since i've taken discrete math).
The chances of me picking a "correct" number are |x-y|/|z|, where z is infinite, which is 0.
The assumption of gaining odds based on this imagined third number assumes that there is a last number at some point. Once you can quantify infinity, you can retrieve a decimal approximation of your odds. Until that point, you are dealing with zero.
If you're going to pretend that a number is in between the other two, you might as well pretend you know what the other number is....
Update: Here's the proof in the rec.puzzle FAQ. I see two things wrong with it (i think), but i'm going to check into this before posting:-)
Pick any cumulative probability function P(x) such that a > b ==> P(a) > P(b). Now if the number shown is y, guess "low" with probability P(y) and "high" with probability 1-P(y). This strategy yields a probability of > 1/2 of winning since the probability of being correct is 1/2*( (1-P(a)) + P(b) ) = 1/2 + (P(b)-P(a)), which is > 1/2 by assumption.
Update II, Electric Boogaloo: Here's the problem with the proof. As it is written, it is correct, but the first assumption it makes is false. For this situation (picking two random numbers from an infinite set), it is impossible to create a cumulative probability function P(x) as the solution describes. The cumulative probability function is based on the probability mass function, which is always undefined in this case. The probability mass function for any value in this problem is 1/infinity, which is zero. The cumulative probability function is a sum of probability mass functions, which will be zero no matter how many you add together. So if it were indeed possible to pick a function like the proof describes, the proof would hold. However, since the initial assumption is a contradiction, the proof fails.
Here's a nice discussion on cumulative probability functions, and here's a discussion of the probability mass function. Neat-o. Has anyone seen another proof of this?
Disclaimer: This post may contain inaccurate information, be habit forming, cause atomic warfare between peaceful countries, speed up male pattern baldness, interfere with your cable reception, exile you from certain third world countries, ruin your marriage, and generally spoil your day. No batteries included, no strings attached, your mileage may vary.