Canadian Mathematical Olympiad | 2018 Q2 

I believe that f being a bijective is a key and the most important part to proceed for a solution on this question.

Some comments have asked about why the problem is posed over f: Q-->Q, instead of f: R-->R. The motivation is how difficult it is to solve f(x+y) = f(x) + f(y) (Cauchy's functional equation) over Q and R respectively. Simply put, Cauchy's functional equation has two classes of solutions: the nice, simple, linear ones and the difficult, complicated, nonlinear ones. If we restrict our scope to just Q, we're guaranteed to have only the nice, linear solutions. Loosely, since we can tidily move about through Q with just multiplication/division by integers, that extends to the solutions too, which are also tidy and linear over Q. More concretely, we can prove that f(qx) = q*f(x) for all x, for rational q, which, together with c = f(1), gives us f(q) = c*q, and therefore f is a linear function over Q. On the other hand, R has a much finer structure than Q and is microscopically vaster and more "filled out" where Q had "gaps" (i.e., R is a complete metric space). And, unlike in Q, multiplication/division by integers in R does *not* allow us to easily move about since we would miss out all the irrational numbers (which make up "most" of R, in the sense of measure). So because of that "finer detail" of R, nonlinear solutions *might* also exist. In fact, whether or not they *do* exist depends on whether our chosen logical toolbox would allow us to construct them, in particular, whether we can use the axiom of choice (AC). So the issue goes all the way down to the logical framework we're using to support our math. And what would these nonlinear functions look like? They would roughly just look like TV static or a cloud over the plane. Everywhere in the plane would have points making up the function, stippled arbitrarily close to one another or located arbitrarily far away in the plane. More technically, it would be dense and discontinuous everywhere in the plane. Likewise, the functions would also be indescribable since we would have to use AC to "pick" at least an uncountably infinite set of points in the function to form a basis. And good luck specifying the members of an uncountable set! By limiting the scope of the question to functions over Q, the question avoids those difficult, problematic solutions. Otherwise, the participants would need to be comfortable with manipulating some fairly advanced tools like AC that would be beyond what would typically be expected for an IMO (or Canadian MO). For more details, please refer to Cauchy's functional equation and see math.stackexchange question 423492 "Overview of basic facts about Cauchy functional equation".

It's one of the questions where as soon as you see it you immiedietaly know its going to be linear

7:40 to get that result one can also plug in y=0 in 2f(x)+f(y)=f(2x+y)

This is a very direct Cauchy's functional equation after f(2x)+f(y) = f(2x+y), and I believe you can directly state it for f: Q->Q.

Ur channel growth speaks how good ur videos are

at this point you re proving the cauchy equation over the rationals which I think you don't need to as your competing in the math olympiad

Congrats on the new camera angle.

Love that guy's way of ending videos :D

Easy explaination, organized that made a dificult problem sounds easy. Very very useful. Great job. Thank you very much.

Such a clear solution to a cool problem! Thanks Michael Penn!

Your videos are excellent. Thank you.

One day I’ll be able to keep up and understand what’s going on 😂

Estoy problemas son muy típicos de olimpiadas 💪💪💪 buen trabajo, Dr

I just looked at the given equation and the answers immediately jumped out to me. It's pretty obvious actually. But the problem I had was proving rigorously that these were the only solutions. Thanks Michael for the outstanding proof.

We can solve it in an easier way.. P(0,0) P(3f(0),3f(0)) yields f(0)=0 P(0,x) yields ff(x)=x P(f(x),0) yields f(2x)=2f(x) Finally P(f(x),f(y)) yields f(2x+y)=f(2x)+f(y) and its cauchy So f(x)=cx and we substitude to find that c=1,-1

Interesting. The result is the same (but the proof is a little different) if we take f: Z -> Z, but if we take f: V -> V where V is any vector space over Q (such as R), then f satisfies this equation if and only if it is a linear involution. (That is: you can pick any basis for V over Q and then allow f to swap over any pairs of basis vectors, and you can choose to negate any of the remaining basis vectors. For example, the unique linear function for which f(1) = sqrt(2), f(sqrt(2)) = 1, and all other basis vectors map to themselves, satisfies the equation.)

8:22 Well prepared students be like: *It's over!* This is Cauchy's Functional equation over Rationals.

You could see that the function is linear transformation (above Q, for course) and really make your solution a lot shorter. Great video!

It would be interesting to explore why they choose the domain of this problem to be just Q and not R.

You can clear see that f(x) = x is a solution even before you start solving the question. Now all you have to do is check if it's the only solution or you can generalise it

Once you have the involution and f(0)=0, then f(2x+y)=2f(x)+f(y) and you first set y=-x to get f(-x)=-f(x) and then set y=0 to get f(2x)=2f(x) and y=x to get f(3x)=3f(x). Inductively, y=(n-1)x gives f((n+1)x)=2f(x)+(n-1)f(x)=(n+1)f(x) i.e. f(nx)=nf(x) for all integers n, or f(x)=f(nx)/n. Letting x=m/n, this becomes f(m/n)=f(m)/n=f(1)*m/n.

Very Interesting functional equation!!

very helpful! thanks!

Fun fact: if a function "f" satisfies the equation "f(f(x))=x" for all x in its domain, then "f" is what's called an involution.

15:40 we get f(x)=ax and a^2=1, so Square the both side of f(x)=ax to get f(x)^2=a^2*x^2 and from a^2=1 we get f(x)^2=x^2 and take the square root of both side and we get f(x)=±x so, for some x we have f(x)=x and for some x we have f(x)=-x you can't just say f(x)=x and f(x)=-x are the only solutions of the equation. What if for some x , f(x)=x and for some x , f(x)=-x ? You must give a contradiction that for some x , f(x)=x and for some x , f(x)=-x is not a solutuion to the equation. We can give a contradiction for this. We have assume that for some x , f(x)=x and for some y , f(y)=-y. Now we have f(x+y)=f(x)+f(y), from our assumtion, f(x+y)=x-y , and f(x+y) is equal to x+y or -x-y , so there are 2 cases, x-y=x+y or x-y=-x-y but both of them leads to the contradiction. And from here we can say f(x)=x and f(x)=-x are the only solutions to the equation.

At the end is a Cauchy equation and I think that the bijection is sufficient to prove the claim

all of this is valid also for differentiable f(x) from R to R

It was very intuitive that the function has to be linear, as the first order function is equal to a second order function....

This is really good. You might want to consider record on a tablet a la khan academy.

This is the first of your videos where I managed to find the solution on my own. I got f(x) = x, but forgot f(x) = - x. I loved the video, thanks you professor.

Very good

I recently encountered your discrete calculus video. It made me really interested in this subject. But I’m stuck on finding the anti-difference of ttrig functions like sinx for example. Can you make a video about that? It’s really interesting! Nice video as always!

Since f and f-1 are symmetrical against y=x, equality f=f-1 immediately means that f=x or f=-x

Once you prove that f(f(x))=x, you can immediately show that f(x)=x is a solution by using the geometric interpretation of an inverse function (reflecting across y=x).

Wait couldn't we stop the solution at 5:12? Because if f is its own inverse than f can only be x or -x?

Does this strategy generalize to f(ax+by)=cx+dy?

In f(2x)+f(y)=f(2x+y) You can just put x=x/2 And boom you will get cauchy So f(x)=cx

Pretty nice video

What book would you recommend to start studying functional equations?

Great!!!

Prof Penn, I worked out y=x^x (x to the power of x) and found for x=0, y approaches 1. Also for x=1, y will be 1. For x=1/e=~0.3678, y will have its minimum which will be 0.6922. beyond x=1, y increases continuously until +infinity. Here's my problem and I need your help, perhaps a video: for x= -infinity, y=0. For all even negative integers, y>0. For all odd negative integers, y

Hey! Nice problem. When I tried solving it I used the fact that x=y implies f(3f(x)) = 3x and then proceeded with an ansatz that the equation has the form f(x) = Ax+B where A and B are rational coefficients. This implies that f(3f(x)) = ... = 3A^2+3AB+B = 3x and since the equation should be true for all x the coefficients and constants on the LHC should be equal to the coefficients and constants on the RHS, we get a system of equation which yields the same solution as you have, namely f(x) = x or f(x)=-x, which is pretty easy to check. Now, is there a problem with this solution? Is it okay to solve it using an anzats? Or is it an illegitimate solution?

Can we think about it in term of isomorphisims and homorphısims

It can be more easy by comparing of polynomial orders

Out of curiosity, are there functions over the reals that satisfy f(x+y) = f(x)+f(y) but aren't linear? -I guess you can easily define like f(x) = ax if x is rational and f(x) = 0 otherwise.- (nope nvm that doesn't hold lol). If f(x+y) = f(x) + f(y) and f is continuous, would f then need to be linear? I guess so, because every real is arbitrarily close to some rational?

At 7:35 you state that f is it's own inverse because it is the case on the left side, but on the right side you use different cobditions. Why must f in the second case also be it's own inverse? And for 2f(x) = 2x to be the case you have to assume linearity and therefore can not conclude it or am I mistaken?

Is that a door handle to the left of the board?

What is the issue if you consider the real numbers as range and domain? Is the result incorrect or just harder to prove?

How about f(x) = k (k is the constant value)

Did any part of the argument at 11:30 depend on the fact that the rational was positive?

Mine wasnt very rigorous, i derivated two times and got that f"(2f(x)+f(y))=0, f(x)≠0, f(y)≠0. That let me think that f is linear. Since i assumed 2f(x)+f(y) could give you any number. Then plugged the general linear f(x)=ax+b in the original ecuation and got that a=1 and b=0. Then f must be the identity function f(x)=x.

Amazing video ! I have a doubt. How to prove that the function is always linear ?

At 2:40 why does x=3f(0)?

hello! I have a question. I solved it, but I used something else. I said that any polyonimic function of degree n when composed to itself will yield a polynomial of degree n^2. So I let y be equal to x and said that since the right hand side is a linear function the composition must yield a linear polynomial and the only way for this to happen is when f is of the form f(x)= ax +b . So I substituted that in and solved a system of a and b and found the same result. Is this way correct?

I found out f was linear before I figured out that f(0) = 0... lol. It was a pain, especially compared to this solution!

Hi, could you please make a video on the fifth problem of the 2020 Canadian Mathematical Olympiad? As a competitor who couldn't solve it at all (0/7), I would love to see how you tackle it as you do in all your other videos! Here is the problem statement for your convenience: There are 19,998 people on a social media platform, where any pair of them may or may not be friends. For any group of 9,999 people, there are at least 9,999 pairs of them that are friends. What is the least number of friendships, that is, the least number of pairs of people that are friends, that must be among the 19, 998 people?

What if the domain and range are both the set of real numbers?

It's "Canadian Mathematical Olympiad 2008" NOT 2018.

15:45 Why do we still have to show that the solutions satisfy the functional equation? Hasn't it already been proven that they satisfy all the necessary conditions? If that's not the case could you give a counterexample? Is there a functionalequation for which you could deduce a "false" solution? Great video! The explanation was so clear and easy to follow!

The board says that the question is from 2008 and the title says 2018 which one is it?

at 4:56, why f (0) = 0, if x is now assumed not to be equal to y? how do you infer that value? Good video btw

Professor, I understand you prove f(x)=0, f is bijective and f(x+y)=f(x)+f(y) My question is how do u prove that f(x)=ax is the only possible family of function that can satisfy this ? Thanks

You could just say f is an odd function

putting f(0)=c may make things look easier...

At 6:26, can't you now say that f is linear? And f(0) = 0 so you can just say f(x) = a.x with some rational a

x=y would give f(f(3x))=3x so now u can conclude f^-1t=ft. and the only solution is x=+_y

Why f(r+s) = f(r) + f(s) ??? consider function x^2 + 3 and f (1+4) is not equal f(1)+f(4) because 5^2+3 is not 1^2+3+4^2+3

I wonder why it matters that f goes from Q to Q. If f would go from R to R, what are the solutions for f then?

Wait for around 4:09, if x=y=0 and x=y=3f(0) then couldn’t you have skipped all of the stuff you did because 3f(0) = 0, so f(0) must = 0?

Unless I am very much mistaken then 9:37 holds for almost anything satisfying commutative multiplication. A tautology All very amateurishly speculative on my part and putting it naively as professional as my abilities allow: Principle of nested sub-spaces supra-spaces. - all have a common zero of various dimensions so what has solution in a subspace remains a solution in all of its sub-spaces and all of its supra-spaces. Note: I think there may be something topologically interesting going on there. As stated in problem collapsing a 2-space problem to a 1-space solution actually generates a topological thing in those spaces. That is tautological property holding in all supra-spaces holding those events. Interim conclusion: set X and Y= as some polynomials of any rank then the solution will also hold including for quotients reals but not sure about complex numbers or non-commutative algebras So it should work for spaces ℚ ℝ ℕ and ℤ maybe for ℂ but not sure about ℍ

But, Micheal sir, you did not check if f(a)=a for some a in the rationals and f(b)=-b for some b in the rationals happening at the same time.

I don't get it. He's claiming a linear function is a solution in Q (and N) and he proves this, and even calculates which linear function (he calculates a). But he never proves there are no other solutions. What am I missing?

How do you know that solution is unique?

damn... After like 5 min I was like... well it must be unity! But how to proof it is the only solution? I too me unti 11:55 to see the other solution

F(X) = X

❤❤❤❤❤❤❤

Aren't f(x)=× and f(x)=-x the only functions that are equal to their inverses? Then the proof would be much shorter

if f:R->R would be continuous then it would work for R

A very great video. !! Hey can u make a video on Ramanujan Master theorem ? U can get the proof on academia.edu .

Oblivious student, with a very general question here: Why can we set a variable to one number, arrive at an identity using that resolution, but then conclude that said identity is true for all values of the aforementioned variable?

Isomorphism!

Couldn't you just make a system of equations assuming the solution is of the form f(q)=aq+b of the following form: 2a^2=1 a^2=1 b(3a+1)=0

somebody tell me why am i wrong? domain and range of f are the same. So we can conclude 2f(x)+f(y)=2x+y ; f(x)=x ; f (y)=y so f =x=y.

Can someone explain me why it s must that function to be linear? 10:30

8:43 can someone explain this step to me? I dont understand. what if f(x) = x^2, then f(r+s) =! f(r) + f(s). where does he get the proof from?

At 7:35 you say f is bijective, but at that point you had only shown that result in the special case of x=0, which is not the case here.

Don't you need to prove there are no other functions that satisfy the equation as well?

Can't we partial differentiate top right equation in 9:30 to prove for all real numbers?

Me before watching the video: identity, duh! Me after watching the video: f(x) = -x, yeah I kind of missed that. Also I never proved anything. :(

Don’t you have to prove that this is both necessary and sufficient? I think you only proved that your solution is a sufficient condition and not necessary.

But plz don't use side camera

Ur channel growth speaks how good ur videos are