How do you solve the functional equation ? (P2 from 2017 International Math Olympiad)
Let me take this opportunity to solve another math problem terribly.
Problem 2 in the 2017 IMO was this functional equation:
Problem 2. Let \mathbb{R} be the set of real numbers. Determine all functions f:\mathbb{R} \to \mathbb{R} such that, for all real numbers x and y,
\displaystyle f(f(x)f(y)) + f(x + y) = f(xy) \tag 1
The solution below is my own, and as per the SMPT philosophy, I’m presenting it along with my thought processes and multiple failures. A compact, clean solution can be written down in half a page.
As with any functional equation, one of the first things you do is plug in some concrete values of the variables and see what happens. I started with x=y=0 which yields
f(f(0)^2) + f(0) = f(0)
f(f(0)^2) = 0
This doesn’t seem very helpful per se, but it does say that some number is taken by f to 0. This is always a useful thing to know: 0 is in the image of f.
I also noticed that this worked because f(x+y) and f(xy) were the same thing when x=y=0, simply because x+y and xy are the same thing when x=y=0. But x+y and xy are the same thing in many other cases, too. When?
Well, given any value of x, we may wonder which value of y makes x+y=xy. Looking at x+y=xy as an equation in y, it is solved by y=\frac{x}{x-1}. Oh, interesting: x=1 does not have a partner y which makes x+y=xy (because nothing makes 1+y=1\cdot y true), but any other x does.
So there seem to be “lots of things” that are mapped to 0 by f: For any x\neq 1,
\displaystyle f\left(f(x)f\left(\frac{x}{x-1}\right)\right) = 0 \tag 2
Of course at this point we still don’t know how many different values can f(x)f(x/(x-1)) obtain, but we do know that all of those values are mapped to 0 by f.
Ok. That little detour actually saved us some work with checking special values for x and y; for example, x=y=2 is already covered (because 2+2=2\cdot 2, we know that f(f(2)^2)=0, too). Trying other specific values, like x=1,y=2, didn’t seem to be very illuminating.
I next wondered what f(0) might be, since this is also a common stage in analyzing functional equations. Could it be that f(0)=0? Let’s assume that’s true, and check the original equation (1) with y=0. We get, for every x,
f(f(x)f(0))+f(x)=f(0)
But if f(0)=0 then this says f(x) \equiv 0, meaning f is just the zero function. Does it solve our functional equation? It sure does, so we have one possible (sort of degenerate) solution. This isn’t rare for functional equations, and so we set this aside and move on – but now we know that, if there are any other solutions to our equation, they must all satisfy f(0) \neq 0.
I then looked at equation (2) again, which as you recall works for any x except 1. What happens if x is such that f(x)=0? Then (2) becomes f(0) = 0, which we now know isn’t true. Therefore f(x) cannot be 0 for any x. But wait… the first thing we discovered was that 0 is in the image of f. This apparent contradiction would have meant that we’re done – there aren’t any other solutions. But it doesn’t, since (2) excludes the value x=1.
Since there is some number which goes to 0, and no number except x=1 may go to 0, we have proven that f(1)=0, and moreover, f(x) \neq 0 for all x \neq 1. Nice: we’ve identified exactly who gets mapped to 0.
We observe that equation (2) says that f(\text{something})=0, which means that “something” must be 1. So, for any x \neq 1,
\displaystyle f(x)f\left(\frac{x}{x-1}\right)=1.
That’s an interesting functional equation in its own right. It should be an instinct to explore the dynamics of the map x \mapsto x/(x-1), in order to understand just how much rigidity this equation imposes on f. It turns out to be very little: applying this map twice yields the identity map, so really what this says is that half the numbers can do whatever they want and the other half is then determined, having the reciprocal value. This doesn’t turn out to be important, but it’s a natural exploration for anyone at this point.
At this point I recalled that f(f(0)^2)=0, which was the first thing we’ve found. So now we know that f(0)^2=1, so f(0) = \pm 1. This still leaves two options for f(0), which cost me a lot of time going forward: I kept wondering which option I should pursue first, with the belief that once I’m done with it, the other would be similar. A better person than I would simply observe immediately that -f is a solution whenever f is, so of course f(0) is going to have two legitimate values if it has any (except 0), and we can just pick f(0)=1 for convenience and remember to add -f as another solution in the end.
There are now two interesting things we can do with (1): we can see what happens when y=1, and what happens when y=0, since those are two cases where we already know f(y).
When y=1 we get
\displaystyle f(f(x)f(1))+f(x+1)=f(x)
\displaystyle f(0)+f(x+1)=f(x)
\displaystyle 1+f(x+1)=f(x)
\displaystyle f(x+1) = f(x)-1 \tag 3
that’s a nice relationship between the values of f at each point and the one +1 away. Of course it can also be run backwards:
\displaystyle f(x-1) = f(x)+1
you get this just by replacing x with x-1 in (3) and rearranging. In particular, since f(0)=1, we can conclude that f(n)=1-n for every natural number n. At this point you may guess, correctly, that f(x)=1-x is the solution we’re after (and f(x)=x-1 is the other). It’s easy to check that both of these solutions actually work, and we expect that those are the only ones. Our job, of course, is to prove this.
Going back to (1) now with y=0 we get
\displaystyle f(f(x))+f(x)=1
\displaystyle f(f(x)) = 1-f(x) \tag 4
This is interesting. It almost says what we want. It says that if w happens to be f(x) for some x, then f(w)=1-w. In other words, f acts the way we expect on its own image – but we don’t know if its own image is everything. If we manage to prove that f is onto, then we’re done.
This turned out to be easier to want to do than to do. To show that f is onto, you want to pick an arbitrary real number z and manipulate the equations until you find f(\text{blah})=z, or even f(\text{blah})=1-z or -z or 1/z or anything else that covers, or almost covers, all the real numbers. But our functional equation is all f's! There are no free-standing expressions that aren’t wrapped as an argument of some f. This made the task of proving surjectivity beyond my powers, and unfortunately it took my quite a while to realize that it’s beyond my powers.
At some point I went back to (4) and wondered what happens if I apply f to both sides. No, actually, that’s not what happened: I remembered that once you have f(f(x)) under control, it’s sometimes useful to evaluate f(f(f(x))) in two ways: one by thinking of it as f of f(f(x)), and one by thinking of it as f(f) of f(x). Using (4), this gives the two equations:
f(f(f(x))) = f(1-f(x))
f(f(f(x))) = 1-f(f(x))=1-(1-f(x))=f(x)
So those things are the same, which means that
\displaystyle f(x) = f(1-f(x)) \tag 5
This is crazy. We believe that f(x)=1-x must be true, and this equation is consistent with that, but once again it doesn’t quite imply it. In fact, if we knew that f was one-to-one (injective), then we could immediately conclude that x=1-f(x), because for a one-to-one function, if f(\text{foo})=f(\text{bar}) then foo=bar. And this is crazy because we now have two paths to complete the proof: either prove that f is surjective, or prove that it is injective! Aargh!
I spent forever jumping between these two paths. No progress on either. I was ready to give up. IMO contestants are now too smart for me. I used to solve IMO functional equations without much trouble. This one’s too hard!
Here’s where I got stuck. To show that f is injective we need to pick two arbitrary real numbers a and b, assume that f(a)=f(b), and conclude that a=b. Plugging a,b as is into (1) doesn’t seem to help at all, but I did quickly realize that what I really want is to find x,y so that x+y=a and xy=b. Why? Well because that forces f(x+y) and f(xy) to be the same, which is what served us so well in the beginning.
But I was facing two problems. The smaller issue was that you can’t always find x,y whose sum is a and whose product is b. You have to have some discriminant come out positive for that to work. I wasn’t too worried about this, because I remembered equation (3): it lets you hop over by 1’s to the right or left quite freely, so I assumed that if need be I’ll just shift a,b to an appropriate location and all will be well. That, by the way, is indeed a good strategy, as we’ll see.
The bigger issue was this: suppose I succeeded in finding x,y like that. Plugging them into (1) yields
f(f(x)f(y)) = 0
so f(x)f(y)=1. But here’s the problem: we know that f(x)f(y) is indeed 1 when y=\frac{x}{x-1}, but we don’t know the reverse. We can’t conclude, from f(x)f(y)=1, that y must be \frac{x}{x-1}. This is the same darn injectivity that we don’t have, because it is just what we’re trying to prove.
Things would have been better if we had
f(f(x)f(y)+1)=0
because then we could conclude that f(x)f(y)=0, which says that f(x)=0 or f(y)=0, meaning x=1 or y=1. This is a nice, concrete conclusion to draw about x and y themselves, rather than their images under f. But how would we get this +1 in there?
The answer, it finally occurred to me, is to use (3), and modify the definition of x,y. Instead of asking for x+y=a, xy=b, we are going to require x+y=a, xy=b-1.
Remember: a,b are just two numbers with f(a)=f(b). We are defining x,y as solutions of x+y=a, xy=b-1, which we may do because if we can’t, we will replace a,b by a-1,b-1 and keep doing so until b-1 is a negative number, at which point the equations x+y=a, xy=b-1 can be solved for real values of x,y. This “replace” step is fine because f(a)=f(b) if and only if f(a-1)=f(b-1), thanks to (3).
Ok. So now we have those x,y, and so
\displaystyle f(f(x)f(y))+f(a) = f(b-1)
\displaystyle f(f(x)f(y))+f(a) = f(b) + 1
\displaystyle f(f(x)f(y)) - 1 + f(a) = f(b)
\displaystyle f(f(x)f(y)) - 1 = 0
\displaystyle f(f(x)f(y) + 1) = 0
This is just what we wanted. We conclude that x=1 or y=1, and by symmetry it doesn’t matter which. Suppose y=1. Then x+1=a, x=b-1, meaning a=b which is (miracle of miracles!) just what we wanted. This is so stunningly pretty and unexpected, I’ve no idea how the person who came up with this problem came up with this problem.
So, to wrap up: we somehow managed to show that f must be injective, which thanks to (5) means that f(x)=1-x. This was all under the assumption that f(0)=1; the case f(0)=-1 implies that -f satisfies -f(0)=1, so then -f=1-x and so f=x-1. Overall, we have proven that there are precisely three functions satisfying equation (1):
- f(x)=0
- f(x)=1-x
- f(x)=x-1
And this is it.
QED, but I’d never have gotten this on time in an actual IMO setting.