Hey, this is Presh Talwalkar reminding you to Mind Your Decisions The International Mathematical Olympiad, or IMO for short, is an annual competition for pre-college students. More than 100 countries participate and each country sends a team of its 6 elite Math competitors. On the first day, students solve 3 questions in 4 1/2 hours, and on the second day, they solve another 3 questions in 4 1/2 hours.
Each problem is worth 7 points for a total of 42 points In 2019, the individual mean score was about 16 points, but there were students who got a perfect paper with 42 points. This problem comes from day 1 question 1: Let Z be the set of integers: Determine all functions f going from Z to Z, such that for all integers a and b f(2a) + 2f(b) = f(f(a+b)).
Now while this is an incredibly challenging problem for most of us, about 60% of these competitors scored a perfect 7 points on this problem. For them, this was an easy problem, but for the rest of us, this is a very challenging problem, and in this video, I want to give some indication of how you can solve it.
Pause the video if you’d like to give it a try, and when you’re ready, keep watching to learn how to solve this problem. [Theme Music] So I’ll admit I wasn’t able to solve this problem myself, so I want to thank the Art of Problem Solving community, Beni Bogoşel’s blog, and the RedPig YouTube Channel.
I read solutions on these places, and it helped me understand how to present it for you. So how can we solve for all functions over the integers, such that this equality is true. Now solving this problem is a little bit like giving directions from point A to point B, you’re gonna have to calculate a lot of different routes, until you figure out a good way to go from A to B.
Just like a GPS will show you the shortest path or a path that’s easier to understand, I’m going to just present the solution to you, as if we’ve already done all the experimentation There may be other easier ways, but this is just one way that I hope you’ll understand. So we’ll get started by trying some special values:
Suppose a = 0: we’ll take this equation and we’ll substitute in a = 0.
We get f(0) + 2f(b) = f(f(0+b)). 0+b simplifies to be b.
Next, we’ll consider that this is true for all integers b. Therefore we can substitute the variable x here, and say it’s true for all integers x Now let’s try the special value a = 1, so we take our identity and then substitute a = 1. 1+b will be b+1 because addition is commutative.
We’re now going to take this f(f(b+1)) and simplify it. How can we do that? Well, look at our first identity. We have a composition of f(f(x)). So we substitute in b+1 wherever we see x. And we end up with f(0)+2f(b+1).
So this will become another identity. Now recall that this is true for all integers b. So we’ll substitute x here, and we’ll just write that it’s true for all integers x Now we’re going to manipulate this equation: We have a x term on the left and a constant term on the right.
So we’ll switch them to the other side, We’ll bring the constant term to the left side, and the x term to the right side Now we’ll divide both sides of this equation by 2, Notice the right-hand side of the equation, will be the difference of consecutive terms.
This is f(x+1)-f(x). The left-hand side of the equation will be the value of the f(2) – f(0) all divided by 2. Therefore this will be a constant value and it’s true for all integers x, This means we have an arithmetic progression, because the difference of consecutive terms will be some constant value, This means f(x) can be written as the linear equation: mx+n. We now take this form and substitute it back into the original equation, We start with f(2a), then we go to 2f(b), and finally we have a composition.
So first let’s do f(a+b), Then let’s do another evaluation of the function. When we do that we end up with the following equation, We simplify both sides, and now how are we going to figure out m and n? We’re going to match coefficients of like terms, so here we have the term a+b on the left, and a+b on the right, and this has to be true for all integers a and b.
The only way this is true is if we match the coefficients 2m and m² Now we also match the constant terms. So we have 3n=mn+n. We have a system of equations. We’re going to solve this by considering each case. So how do we solve 2m=m²? Well one solution is m=0, We’re going to substitute that into our second equation.
We have 3n=n and that’s only true if n=0. The other possibility is that m=2, and in this case, we substitute it in and get 3n=3n, so n can be any integer. And we now have two possibilities for our solution, one will be f(x)=0, and the other is that f(x)=2x+n for some integer n in Z.
We want to verify that these actually are true and substitute them back into our original equation. We can do that and we’ll see that we’ll get equality for both cases. Therefore these are the only solutions either f(x) is identically 0.
Or f(x)=2x+n for some constant n. I hope this video gave you some sense of how to solve an Olympiad problem, and I hope it gave you some idea of how challenging these problems are, because the competitors found this problem to be on the ‘easy side’. Thanks for watching and for making Mind Your Decisions one of the best channels on YouTube. Thanks for watching and thanks for your support.
