This week I solved the following PEN-problem:

Find out which pairs of real numbers have the property that: for all natural numbers , where denotes the largest integer

At first glance, this problem looked quite easy to me. While I’m not sure if that’s a good sign in general, in this case it was advantageous. Because some problems that are stated in the form ‘find all x such that y’, are only solvable by providing a way of finding those x, where that way of finding, immediately shows that you’re right. This might be vague, so let me give you an example. Consider the problem of finding all primes less than 10000. I guess that no one will just write down the list of primes. No, probably everyone will just use the sieve of Eratosthenes. And not only will that sieve give you all primes below 10000 it is/should be immediately clear *why* it works and generates all these primes. So using the sieve of Eratosthenes gives the answer and proves you`re right in one blow. While that’s awesome, in general it’s not that easy to straightforwardly find a solution that strong. Going back to the problem at hand, you may feel that it begs for an impossibility proof, except for trivial or ‘degenerate’ cases. In other words, we already ‘found’ our solution, we only have to prove it’s right. In still other words, we already know how or where to start (for example: assume a true non-degenerate case) and where to end (in contradiction). And knowing how a proof could reasonably look like, before you even started, is a big advantage, I think.

Ok, so far the preliminary remarks. To concretise the above part, the degenerate cases are:

1)

2)

3)

It’s a trivial matter to show that all these cases indeed solve . Now, I kind of simplified things in the above paragraph. Because there is definitely not 1 way to prove we’re right that these cases are the only ones that solve the above equation. We could assume that 1), 2) and 3) all don’t hold and end up in contradiction, we could assume and try to prove , we could (since proving that is integral iff is, is trivial), assume that and show that must hold, etc. There are tons of distinct ways to end up where we want to end up. But, in a way, they’re all the same too, of course.

One of the first things I did was assuming that both and are positive. This is something I do a lot, because, well, I’m just not that fond of negative numbers. Moreover, usually the general case quite easily simplifies to the positive case and in here I felt it was a natural thing to do. Although it turned out that we actually do lose generality, without an extra argument, by assuming positivity, it was still a useful pet problem, so let’s assume positivity for now anyway. The next thing I tried was dividing both sides by to get our first result: is rational! While this is not much, it accounts for something. This inspired me to do a few things; First of all I filled in and found out for which real numbers this equation holds by letting: , for integral such that , . Second of all I noticed that this argument doesn’t work if , because then we just have , and there’s not much to conclude from that. So I tried to prove , in which I succeeded (see below). Third of all, since we know that , it seems natural to (try to) show that and can’t be distinct, rational, non-integral numbers. As it turns out, this is quite straightforward, so to solve our problem, the following suffices:

Let be distinct, irrational numbers. Then for at least 1 positive integer .

Like I said, proving that (while assuming positivity and distinctness), is possible, so here is its proof: Let . If , as well, otherwise we would have: , which is a contradiction. So we may assume . Let be the smallest integer such that . Then must be larger than 1 as well, because otherwise we would have the same contradiction as above. But we now have: , which implies . So if and are distinct and positive (although I hardly used the positivity condition), can’t hold for all natural numbers .

Now that we showed that, we can definitely say we are on our way. A cool way to go further is by using induction. When you see an (moderately easy) equation that should hold for all natural numbers , it’s often possible to show that it indeed holds by using induction on . However, here it might be possible to go the other way around, by using induction on ! More precisely; assume that for some natural number . Show that a natural number exists for which (except degenerate cases). And since we proved our base case (), this suffices. I must say I think this way of attacking our problem is both weirdly awesome and awesomely weird. But when I first tried it, the computations didn’t make any sense, so I chose a different approach. Although I might give it some thought again, since I have a better understanding of the problem now. Anyway, for me this wasn’t the way to go, so let’s try something else.

The good part is: we didn’t use the, to me, most obvious way of approaching this problem, extensively yet. So let’s do that. I believe that, whenever you’re dealing with the ‘greatest integer smaller than’-function, it’s usually a great idea to split that what’s inside the gist-function in two parts: an integer part and a rest part. For example: . So let’s, like I said above briefly, assume with and . Then we have:

We know that this must hold for all . In particular, it should hold for . When , the above equation simplifies to:

So we know that this must be the case. But then and always cancel each other out, so the equation becomes:

And the great news is that we basically solved this equation already, when we showed the impossibility of distinct, positive integers such that for and smaller than 1. But, for completeness’ sake; let be the smallest positive integer such that . Then as well, because otherwise we would have on one side of the equation while the other side is non-zero. Since our equation is true for all , it must be true for too. And for this , it further simplifies to:

And we’re done.

October 10, 2010 at 18:31 |

[…] my post ‘only integers behave nicely’, I came up with another proof (and another variation of it) of the following […]