Why No Such Function? | International Mathematical Olympiad 1987 Problem 4

#IMO #FunctionalEquations #MathOlympiad
Here is the solution to IMO 1987 Problem 4!!
------------------------------------------------
Follow my Instagram page for more Maths :)
Link: / lets.think.critically
------------------------------------------------
I share Maths problems and Maths topics from well-known contests, exams and also from viewers around the world. Apart from sharing solutions to these problems, I also share my intuitions and first thoughts when I tried to solve these problems.
Subscribe: kzbin.info...
Email me (address in video) your suggestions! [e-mail]

[@ImaginaryMdA]

Yay, I finally managed to solve one of these without looking at the answer first!

[@littlefermat]

I remember solving the problem in the general case with odd and even cases in Titu Andreescu functional equations textbook. By the way I am uploading a functional equations playlist if anyone is interested 😊

[@TechToppers]

Promotion😃

[@gamingsquad7149]

@@TechToppers XD

[@spiderjerusalem4009]

Is it the one with 147 pages? Thanks

[@cosimodamianotavoletti3513]

for the final question: we have a bijection between f's that satisfy f(f(x))=x+2a, and involutions g:{0, ..., 2a-1}→{0, ..., 2a-1}, such that g doesn't have fixed points (otherwise the argument in the video still holds). The number of such g's is the number of possible pairings of the numbers in {0, ..., 2a-1}, which is (2a)!/((2^a)*a!)

[@Felissan]

This actually only gives the number of g's. But it's not a lot more work to get the result for f. If g(m) = n, and consequently g(n) = m, then there exist natural numbers k and l such that f(m) = n + 2a*k and f(n) = m + 2a*l. Then: f(f(m)) = f(n + 2a*k) = f(n) + 2a*k = m + 2a*(k+l) So, k + l = 1: either k = 0 and l = 1, in which case f(m) = n, or k = 1 and l = 0, so f(n) = m. From there, we can find a bijection between solutions to the equation and ordered pairings of {0, ..., 2a-1}, of which there are (2a)!/a!

[@cosimodamianotavoletti3513]

@@Felissan Right, for some reason I just assumed there was a bijection between f's and g's without considering both cases. Well spotted, thank you.

[@discordaccountv3155]

Definitely understanded that

[@hfs-lk5ip]

@@Felissan very cool!

[@austinconner2479]

Let S be the set of numbers not in the image of f. S is finite. The numbers not in the image of f^2 are S union f(S), which is a disjoin union because f is injective. Therefore the numbers missed in the image of f^2 are even in number. This contradicts the equation

[@EnnioEvo]

How did this 2 lines proof get unnoticed, you are great

[@foobar5809]

this is very cool! I knew there had to be an easier way, but couldnt find it!

[@dhay3982]

Why is S finite?

[@foobar5809]

@@dhay3982 because S is a subset of {0,…1986} by the equation.

[@hamzabelkhayat3511]

OK. But f injective doesnt make S union f(S) a disjoint union. ( counter example : if f=id or any permutation of S then S = f (S) )

[@ggeshundra]

WAS THAT THE FUNCTION OF 87

[@Martykun36]

Looking at the function as if it was a directed (infinite) graph made the problem rather straightforward: - The graph cannot have cycles, because f(f(x)) > x and completing the loop means that f(f...f(x)...) = x for some x and some even iteration of f. - No two different values x1 and x2 point to the same value y, otherwise we have f(f(x1)) = f(y) = x1 + 1987 and f(f(x2)) = f(y) = x2 + 1987 so x1 = x2. From the points above, the graph can only be made of infinite lines, and the first two places in each line have to be populated by values between 0 and 1986 inclusive (any other value x has a "prepreimage" y = x - 1987 s.t. f(f(y)) = x) thus the number of lines is finite (call it k). Since we have an even number of places (equal to 2k), and an odd number of values to fill them with, there is no possible f.

[@emilysort]

This is very helpful thanks

[@shreyamjha3058]

Plz make a separate playlist for functional equations if u can,it would be of great help

[@littlefermat]

Actually, I have one on my channel if you're interested.

[@mrityunjaykumar4202]

there exists atleast 1 fixed point.. max no: of fixed points can be 1987 that is the entire set {0,1,2,...,1986}..for max no: fixed points g(x)=x=>g(g(x))=g(x)=x.

[@Calcprof]

g is a product of disjoint 2 cycles, so g has a fixed point (as the set 0,1,....,1986 is odd)

[@omazin14]

F(x) = x + 1987/2. F(f(x)) = x + 1987. Boom. Works like a charm😂

[@jollyjoker6340]

My first thought when reading the problem was "what does Z mean?"

[@amazing-qq3wi]

It took me a whole 10 secs to realize this was a joke

[@MaxTheDogAppreciator]

I don't get it, why is this invalid? I had the same exact thought. if f(x) = x + 993.5, then f(f(x)) = x + 1987 no? where's the error?

[@naveennamani2]

Why is this a joke? This same thing popup in my head when I looked at the question

[@ondrejdarmovzal4976]

@@MaxTheDogAppreciator Because the example you gave is not an integer-valued function.

[@thiagosegantinchiotti4841]

So I have a question... Is there any problem in my solution? I think is quite of simple, and because i'm not smart enough, I can't find any problem in it. Basically I've described the problem in 2 cases: case 1) f(x) is a binomial - ax +b ; case 2) f(x) is polynomial of nth degree - ax^n + ... + bx + c. Thinking in the first case, what we are going to have is f(f(x)) = a²x + b(a+1), since f(f(x)) is equal to x +1987 - comparing the coeficients - we can say that a² = 1, then a = +/-1; and b(+/-1+1) = 1987 -> what's not possible because 1987 can not be written using 2 as a factor. Just to add, b couldn't be = 1987/2, since f: Z+ --> Z+. b (1-1) = 1987 is impossible too. The other case is a little bit more confuse for me. What I thought was: If I show that it's impossible to f(x) has a nth degree, then i'm done: I started picking the easiest example, let f(x) = ax² + bx + c. After substitute and expand it ( which takes me a little bit of time) I found that the a coeficient should be equal to 0. So I tried to generalize: f(x) = ax^n + ... + bx + c f(f(x)) = a(ax^n + ... + bx + c)^n + ... + b(ax^n + ... + bx + c) + c After expanding it we will find that a^(n+1). x^2n has to be equal to 0, so the only case that it is true is when a = 0. This leave us with: f(x) is a (n -1)th degree polynomial. Substituting (n - 1) by m, and repeating the same process, we will find that f(x) is a (m - 1) degree polynomial. * here is my doubt * We can keep doing this process until the degree be equal to 1. So because of that, f(x) is a binomial - which makes sense, I guess. In the end we have that: f(x) is a first degree binomial and it's impossible to a binomial like a(ax + b) + b [ f(f(x)) ] be equal to x + 1987.

[@Alex-kp3hd]

Heres my take on your solution: The problem with this is, that you can't simply describe all functions by a polynomial. For example consider this: let's say that the solution is that for every odd number it outputs a 0 and for an odd number it outputs an 1, you can't describe this function by a finite polynomial (Maybe take n+1 points and then by Lagranges interpolation construct such a function but it won't work for all points). Furthermore comparing the coefficients won't help, because that technique is used when dealing with real numbers, here you're just dealing with integers, so it is entirely possible that you have a_nx^n+...+a_0=x+1987, this will be satisfied for at most n numbers and maybe the function f is so complicated that n has to tend to infinity, thus be valid for countably infinitely many points.... For example f(f(x))=x (x can be an integer or a real number, it doesn't matter), by your method you'll find that f(x)=x,c-x but you won't find that f(x)=c/x, (a-x)/(bx+1)..., because you can't describe this function with a finite polynomial.

[@santiagoarce5672]

Hi. Neat solution. I got another solution to this problem: (following the proof that f is injective) I had f(f(f(x))) = f(x)+1987 and f(f(f(f(x)))) = f(f(x)) +1987 = x + 2*1987. Combining these two facts gives: f( f(x) + 1987)= x+2*1987 Combining this with the statement in the question, f(f(x)) = x +1987, gives: f(f(x)+1987) - f(f(x)) = 1987 This is great because it is the same statement as saying "increasing the argument of f by 1987 always increases the value of the function by 1987", which is only true for a straight line with slope 1. In other words, f(x) = x + c for some c. Now c has to be a positive integer because the function goes from the positive integers to the positive integers. For a function of this form, f(f(x)) = (x+c) +c = x+2c. This is a contradiction! Since 2c does not equal 1987 for any integer c.

[@user-lg7wv4hr2g]

Could you please explain why is "In other words, f(x) = x + c for some c."?

[@santiagoarce5672]

@@user-lg7wv4hr2g I was not rigorous about this. The idea is that you have something like f(x+c)-f(x) = c for all x. If you try to imagine a function like that on the xy plane then you might see why it has to be linear. The reason is that every time you go to the right by c on the graph, you go up by c as well. If you didn't have a straight line, this would not happen. Maybe a more rigorous way to show this is by using the definition of the derivative: f'(x) = lim (c->0) (f(x+c)-f(x))/c. Since in our case f(x+c)-f(x) =c, the limit is just lim (c->0) c/c = 1. So f'(x) = 1. This is like the easiest differential equation ever as the solution is f(x) = x+c where c is a constant. You might be confused because I just used a function of the form f(x+c) instead of f( f(x) +c), but this shouldn't make a difference to the argument.

[@cr1216]

@@santiagoarce5672 Well this is exactly what the author tried to prove using the involution + fixed point thing. It is not a continuous function so calculus is not rigorous as well. In fact it can be arbitrarily piecewisely configured so you have to use the fixed point concept to prove rigorously.

[@samuricc5747]

For sure this proof is much shorter than the other one, but shouldn't you prove that the function is surjective before saying that it's linear. Maybe I'm wrong, but you proved that the function has that property if you put in the argument a value of its image. However, the function could not have that property if calculated in other values, so the condition necessary to finish the proof would be the surjectivity of the function. As I said, maybe I'm wrong, I'm not too good at these kinds of problems.

[@santiagoarce5672]

@@samuricc5747 Yeah I think you're right.

[@johnvandenberg8883]

An involution is a function f that is its own inverse: f(f(x)) = x for all x in the domain of f.

[@moregirl4585]

Consider h=|N-f(N)| and we have 2h=1987

[@calculus-is-fun]

do i have any problem for this solution? since proven f is 1-1 and f(x+1987)=f(x)+1987, then f(x+1987)-f(x)=1987, hence f is a linear function (since the difference between every set of (x,x+1987) must be a constant), which x>0. Then, since f(f(x))=x+1987, m(mx+b)+b=x+1987, which we can get m=1,-1(rejected) and b=1987/2. considering that previously we know x>0 and f defined in Z>0, then looking back to the f(x)=x+1987/2, which firstly f is not integer for integer inputs, and it is also not defined in [0,1987/2). Therefore, we can claim that no such function.

[@user-wu3zi6wu6h]

I think that you make it complicated more than it needs. Here is my solution. It is obvious to see that f^n(x) = x + (n-1)1987. f^3(x) = f(f(f(x))) -> x + 2*1987 = f(x) + 1987 -> f(x) = x + 1987 -> f(f(x)) = x + 2*1987 Which contradicts our assumption about the function. Thus, there is no such function.Q.E.D.

[@dauletkaztay3794]

pls more IMO problems

[@digantaparai1258]

Can anyone tell me that why injectivity of function is necessary?

[@anasghazialgifari0476]

It helps you to make a proof valid. If you proved that a function is injective, whenever you obtain f(a) = b, then a is the only solution. Otherwise, you need to look for any other solutions.

[@EnriqueDominguezProfile]

Liked and subscribed. Glad the algorithm suggested this 🤘

[@ngtommy49]

I want to ask how can I learn/ what can I learn such concepts by myself? I found that I can't improve much as I don't know how should I learn these advanced knowledge, especially many these are out of syllabus in HK.

[@prithujsarkar2010]

they are meant to be hard , just keep doing problems :)

[@mohcinefallahi3270]

Same

[@nymoldinrui7117]

If you have a trouble to solve easy Olympiad problems such as IMO/1 (Level),I would definitely recommend to learn theory .I mean there is tons of books on the internet .Such As Titu's books(very classic) and many other MAA's books. After learning basic theory you should do random problems on Aops(do not solve easy problems.Because it doesn't improve your problem solving skill) In general learn theory then solve problems,learn Theory, then solve problems.And again,again,again. Good Luck!

[@ngtommy49]

@@nymoldinrui7117 Thanks a lot!

[@casualpasser-by5954]

I was able to solve this problem, but it take many, many efforts for me to solve it...

[@barissezer5254]

Can't you just let x be the inverse funktion of f such that f(x)-f^(-1)(x)=constant which means f(x) has to be a linear funktion and just put mx+b for f(x) to Show that it does not work?

[@user-bz1nl2bk8l]

i had exactly the same thought thanks for posting this!!

[@spiderjerusalem4009]

how does that guarantee that it's linear?

[@spiderjerusalem4009]

how does that guarantee that it's linear?

[@barissezer5254]

@spiderjerusalem4009 taking the inverse of a function is mirroring it on the x = y lane. Consider the difference between f(0) and f^(-1)(0). That has to equal c. Now if you move further right with your x values than either the slope of your function ist greater than 1 equal to 1 or less than 1. But in both cases where the slope is not equal to 1 we get a problem. If the slope of f is bigger than one that means that the difference between f and the x=y line becomes bigger. But on the other hand a slope bigger than 1 means the slope of f^(-1) is less than one so the distance between f^(-1) and the x=y lane becomes also bigger and the overall difference between f(x) and f^-1(x) becomes bigger which isn't possible because c the difference is constant likewise becomes c smaller if the slope of f is less than 1 therefore is 1 the only solution for the slope which leads us for only a linear function for f

[@spiderjerusalem4009]

f(x)=ln(coth(½x)) f(x)=f-¹(x) but f is not linear

[@giorgostarnaras5658]

I solved it differently, I played around with values until I arrived to f(f(f(0)))=f(0) which is false since using the original formula we should get f(0) + 1987.

[@user-lu5nj7yw5i]

Brilliant, subscribed!

[@lorenzosanti3164]

The solution in the video is wrong at time=12.29. f(d+1987 n) is has not to be equal to f(d) + 1987 n. Let call h a function on Z in Z such that f(d+1987 m) = f(d) + 1987 h(m). We have h(h(m)) = m+1. That means that for any m h(h(h(m))) = h(m+1) -> h(m)+1 = h(m+1). By induction h(m) = h(0)+m and m+1 = h(h(m)) = h(h(0)+m) = h(0) + h(0) + m. This hold only if 2 h(0) = 1 -> h(0) not an integer -> contradiction.

[@prithujsarkar2010]

nice problem

[@visweshshukla]

__/\__

[@HitoPrl]

So f(x) = x + 993.5 is not a valid solution because this function does not map from Z to Z. However, why can't we use condicionals? Consider f(x) = x + 993 if x is even, x + 994 otherwise. Then, with for example x=10, f(10) = 1003, f(1003) = 1997, which is 10 + 1987. What's wrong about that?

[@wkmars]

Your function does not work for odd input because adding 994 to an odd number won't change its parity for the next choice to be adding 993, for example, f(1) = 1 + 994, as 1 + 994 is odd f(f(1)) = f(1 + 994) = (1 + 994) + 994 = 1 + 1988

[@HitoPrl]

@@wkmars Oh, wow, I failed to consider such a simple thing. Thanks for your input

[@guptayush179]

very simple if u think about it for more than 10 secs

[@godowskygodowsky1155]

Here's my solution before watching the video. Lemma. It's not possible to satisfy f(f(x)) = x + 1. Let a_n = f^{2n}(0) and b_n = f^{2n + 1}(0). Then a_n = n and b_n = f(0) + n. We get that f(f(0)) = 1 and f(f(0)) = f(a_{f(0)}) = b_{f(0)} = 2f(0). This is not possible. Now split up N into its cosets mod 1987. On each coset, x + 1987 looks like the successor function. For each x, f(x) either belongs in the same coset, which is impossible by the lemma, or it belongs to a different coset so that its sequence f^n(x) alternates between two cosets. There is an odd number of such cosets. QED.

[@jamescollis7650]

Where did you actually use the fact that f was injective?

[@szymoniak75]

i don't understand why you can just do "x = f(x)" ?

[@il_caos_deterministico]

You’re not solving x=f(x) but simply “renaming” f(x) with x. If you prefer you can call f(x)=t So f(f(t))=t+1987 (by hp) Replacing t=f(x) you have f(f(f(x)))=f(x)+1987 (i) On the other hand f(f(x))=x+1987 So f(f(f(x)))=f(x+1987) (ii) Combining (i) and (ii) you have the claim f(x+1987)=f(x)+1987

[@quirtt]

Thanks

[@LoggyWD]

What if X=f(x) is a false assumption

[@timehasstoppedandthefunbeg4467]

The way you write 9 tho

[@Eknoma]

You know your handwriting is weird when you can't differentiate between g and ρ

[@AlephThree]

If it’s f(f(x))=x + 2k for some natural number k, then the only function that satisfies this is f(x)=x+k.

[@dustinbachstein3729]

There are in fact more. For example, for f(f(x))=x+4 we could have: f(x)=x+1 if x is even and x+3 if x is odd.

[@AlephThree]

@@dustinbachstein3729 good point, I’d not considered functions like that. Thanks.

[@umnikos]

@@dustinbachstein3729 I don't get it. f(f(1))=1+4 -> f(1+3)=1+4 -> (1+3)+3=1+4 -> 7=5. Can you elaborate?

[@dustinbachstein3729]

@@umnikos f(1+3)=(1+3)+1 because (1+3) is even.

[@umnikos]

@@dustinbachstein3729 Ah, that makes sense now. Thanks!

[@anneaunyme]

My solution (not sure if exact) : f² is injective , thus f is injective Let's consider f(N) (the set of all f(x) with x positive). more importantly, let's consider all the positive number which are not in f(N) (let's say this new set is E) No number in E can be greater than 1986 (otherwise x=f(f(x-1987)) Consider 0. Either 0 is in E or there is a number x such that f(x)=0 and that number is in E Consider 1, then 2, etc until 1986. That's 1987 numbers that belong to E. For any double among those numbers that's an x such that x is in E and f(x) is not in E but strictly lesser than 1987. There can't be triples. For any non-double among those numbers that's an x such that x is in E and f(x) is greater than 1987. That's a contradiction because then x=f(f(x)-1987). Thus all those 1987 can all be organized in pairs... which is impossible since 1987 is odd. For the even case 2X, we have to pick which of the 2X number that are strictly lesser than 2X are in E and which are not. Basics combinatorics tell us that's (2X !)/(X!.X!). For each of those possible choices, there's X! ways to assigns all the f(x) for all the X xs. Once this is set all functions are completely defined. That leaves us with (2X) ! / X ! functions.

[@williswcy]

Nice

[@krstev29]

This is a little bit hard for a 1987 P4, but I have a different approach than this

[@romainakinlami1193]

I found that f takes two values at 0 F(0)=0 and 1987

[@il_caos_deterministico]

Can you explain how did you show this fact?

[@romainakinlami1193]

@@il_caos_deterministico i think i made a mistake i wanted to try again later

[@angelmendez-rivera351]

@@romainakinlami1193 Well, if you showed that, then that actually works as an answer: it contradicts f being a function, which is essentially what you are being asked to do.

[@romainakinlami1193]

@@angelmendez-rivera351 yes thats true But i did make a mistake when applying the formula and got a wrong result :/ So it doesnt count My bad

[@glowstonelovepad9294]

f(x) = x+993.5

[@rumbleflockendale]

Your f is not Z->Z.

[@raffaelevalente7811]

I think you should add some intuition that lead to get your proof, because this would help the viewere to solve similar problems, thank you.

[@TyDurr1]

I think I'm missing something obvious. Wouldn't f(x) = x + 993.5 be a solution? Edit: I have thought about this for thirty minutes and saw it ten seconds after I posted my comment lol. Any integer plus 993.5 is no longer an integer.

[@justinlink1616]

Hah, I had the same reaction. I didn't take into account that f needs to always return an integer - not just that it needs to obey f(f(x)) = x + 1987.

[@ahmed-bechirbenhammouda370]

I dont get this isnt there a function as in f(x)= x+993.5 ? f(f(x)) would be x+993.5+993.5=x+1987 ?? Please explain this to me and thanks

[@low-litlight3438]

This doesn’t work because the problem is about functions that map integers to integers. If you add a .5 anywhere then you map an integer to a non-integer, so it doesn’t work. Hope that helps.

[@andronikos3389]

I found a simple solution, can someone confirm it? Here it is: f(f(x)) = x + 1987 => d/dx[f(f(x))] = d/dx(x + 1987) => f'(f(x))*f'(x) = 1 and since f: -> Z >/=0, => f'(f(x)) = f'(x) = 1 => f(x) = integral(dx) => f(x) = x + C => f(f(x)) = f(x+C) = x + 2C = x + 1987 => 2C = 1987 => C = 1987/2 witch is not an integer thereforthe function can not exist

[@incription]

prove there is no function f(f(x)) = x^2 + c, ceC

[@isaacchan8159]

pog!!

[@wikiPika]

Why doesn't the following work? Assert f(x) = ax + b due to form of f(f(x)) Then f(f(x)) = a(ax + b) + b = a^2x + ab + b = a^2x + b(a + 1) But 1987 is prime

[@vytah]

You can't just assert stuff like that. Imagine f(f(x))=x+2. Then "if x even, add 3; if x odd, subtract 1" is a valid solution for f, and yet it's not even a polynomial.

[@wikiPika]

@@vytahAh, piecewise...

[@Silicon_0014]

@@vytahwhere is it asserted that it must be a polynomial?

[@vytah]

@@Silicon_0014 wikiPika asserted it without a good reason in the first sentence of their proof attempt

[@jonaswox]

initial thought, what about f(x)=x? would that not give exactly f(f(x)) = x + 1987?

[@noice8824]

I'm not sure where I went wrong, but isn't f(x) = x+1987/2 a function that satisfies this condition? f(x+1987/2) = x+1987, so x+1987/2+1987/2 = x+1987 right?

[@awkwardhamster8541]

yes but the function f maps from integers to integers . For all x belonging to Z , f(x) doesnt belong to Z . So ,its not satisfied

[@Terszel]

Not R (real number), Z (integer)

[@barryzeeberg3672]

Seems that there is a unique solution (for domain of x in reals): by inspection, f(x) = x + 1987/2 We can check that this solution satisfies the original equation: f(f(x)) = f(x + 1987/2) = (x + 1987/2) + 1987/2 = x + 1987 But this is not valid when x is restricted to integers, since the argument (x + 1987/2) is not an integer. So no solution for integer domain.

[@Quantris]

I don't think that is correct. f(x) in reals isn't unique (prove that if you think so; hint for counter-example is think of other ways to make 1987 than just 1987/2 + 1987/2), but also it's not so obvious that a solution on positive integers must coincide with the restriction of a solution on reals. That is vacuously true in this case and I think it is probably true for functional def of the form f(f(x)) = x + k but I doubt it is true in general.

[@yjfoeg]

You'll have to prove that f(x) = x + 1987/2 is the unique function which is even more complicated.

[@dhay3982]

@@yjfoeg It is not true.

[@user-pq4dx2kc7m]

F x a 3

[@YTZMath]

I have a simpler solution: assume such f(x) exist if f(x) < x + 1987 / 2 f(f(x)) < f(x) + 1987 / 2 < (x + 1987 / 2) + 1987 / 2 = x + 1987, conflict with f(f(x)) = x + 1987 so f(x) >= x + 1987 / 2 , this is conclusion 1 if f(x) > x + 1987 / 2 f(f(x)) > f(x) + 1987 / 2 > (x + 1987 / 2) + 1987 / 2 = x + 1987, conflict with f(f(x)) = x + 1987 so f(x)

[@wheatandtares-xk4lp]

Am I dumb or is f(x) = x +1987/2 a solution?

[@pianofrik]

It would be the only solution if you were mapping from reals to reals. But you're supposed to show that no such function can map from non-negative integers to non-negative integers. (And adding 1987/2 doesn't play well with integers.)

[@user-tu7rm3ru4e]

Very Hong Kong tone

[@user-kv3jw6zc9g]

hai gum ga la

[@user-tu7rm3ru4e]

@@user-kv3jw6zc9g ngo dou hai gum wa

[@TingleCowboy]

So the video is about the fact that 1987 divided by 2 isn’t an integer, right? 😂

[@zijie-he]

Since it's expected to prove f(n) does not exist, using it to describe g(n) seems inaccurate. I will get back to you later. OK, so I come back. I think an easier problem is: there isn't a f: Z* -> Z*, make f(f(x)) = x + 3. f(f(f(x))) = f(x) + 3 = f(x+3) suppose f(0) = m 1) m >= 3 f(m) = f(m-3k) + 2k = f(f(0)) = 0 + 3 = 3 (k >= 1) but f(m-3k) >= 0, so k = 1, f(m-3) = 1, so m < 6. 2) m is in [0, 2] f(f(0)) = 0 + 3 = 3 = f(m) = f(0) or f(1) or f(2) it's expected all of these three are in [0, 2]. Sorry typing in the comment is so hard, but the basic idea looks like it.

[@suhaib143]

It's easier than what he did, just proving that the formula f(f(X)) = X + 1987 implies that f(f(X)) is a linear combination of X and 1, which implies that f(X) itself is linear This obtains that f(X) = X + (1987/2)

[@vytah]

How does that imply? f(f(x)) = x+2 has at least one non-linear solution (0->3, 1->0, 2->5, 3->2, 4->7, 5->4 etc.)

[@DFR96MusicForLife]

(2n)!/n!

[@digxx]

Why not (2n)!/(n!*2^n) ?

[@DFR96MusicForLife]

@@digxx because the fibers of the map that sends f to the involution f mod 2n have cardinality 2^n. Indeed, by the functional equation and the fact that f has to take values in the set of nonnegative integers, you can prove that for each involution g on S={0,...,2n-1} that has no fixed points and each couple of points i,j of S that are swapped by g, then either f(i)=j and f(j)=i+2n, or f(i)=j+2n and f(j)=i. Hence 2^n are the possible choices of those points y (one for each of the n couples of points that a fixed g swaps) such that f(y) = g(y).

[@gervasiociampin2062]

Se italiano?? Se si, mi spieghi chè non ho calito niente??

[@digxx]

@@DFR96MusicForLife Not sure I understand what you mean. For an even number of elements (say 2n) it is possible for it not to exist a fix-point. Now let's focus on g(x) (the function mod 2n). Now since g is an involution we have for i,j € {0,1,2,...,2n-1} that j=g(i) and g(j)=i. What this means is that we want to look for the number of different (complete) pairings in a set of 2n elements. This is (2n-1)*(2n-3)*...3*1 or (2n)!/(2^n*n!). Why should this be wrong? For example if 2n=4, then the possible pairings are {(1,2),(3,4)}, {(1,3),(2,4)}, {(1,4),(2,3)} which is consistent with 4!/(2^2*2!)=3.

[@DFR96MusicForLife]

@@digxx I mean that there is NO bijection between the set of maps f and their “projections” mod 2n. The number of such projections is, as you said, the number of different pairings in a set of 2n elements; but for each projection (that is, for each different function g), there exist 2^n different maps f such that f = g mod 2n. The number of different functions f is the number of different ORDERED pairings in a set of 2n elements, hence (2n)!/n!

[@hahahaspam]

You cannot prove that there is no function, since there is such a function. The empty function satisfies the properties, and the empty function exists.

[@pandekacadiak]

f(x) = x + 993,5

[@Tulanir1]

Not an integer

[@chaosredefined3834]

If the number is even, let's call it 2k, then we can define g(x) = x+k. g(g(x)) = x + k + k = x + 2k. So, g meets our condition. Hence, such a function exists.

[@Verrisin]

ooh, it's on integers, then it's trivial. For some reason I at first interpreted it on Complex numbers, and was confused.

[@Verrisin]

I mean, what is all this? The proof is trivial: Since you have to apply it twice, you need a fn that is halved, and since ints, you cannot add odd int in two steps. -- I guess they want some rigorous proof, but that's more about speaking the lingo than any thinking.

[@Verrisin]

I mean, it doesn't matter how you implement it. Since you are not allowed any extra values in between (like negative numbers) the composed fn must be a linear shift, and because the shift is odd, there is no way to halve it...

[@Verrisin]

ok, I guess the real question is why can I not encode any extra information to behave differently in each pass, and the answer is ... because I have no extra bits to work with ... - but yeah, we cannot flip anything twice, if we need it flipped once at the end ... so we cannot add and then remove this additional bit of information ...

[@timangar9771]

Your proof of injection is invalid. You assume that f(x) is injective and then go on to show that this works. However, what you were trying to prove was part of your pretense so the proof is void. How you really do it is to assume that f(x) is NOT injective and then show that this leads to a contradiction.

[@dipo5533]

I think he's right. He didn't assume that f(x) is injective, but that f(a) = f(b). His assumption led to a = b, so basically f(a) = f(b) holds only if a = b, that is the injective condition. Sorry for the bad english, I'm Italian 😅😅😅

[@dipo5533]

Sorry man, maybe you're right. Looking at the equations again it seems he assumed that f(f(a)) is injective (which means that f(a) is injective). I'm not sure though, I'm getting quite confused

[@davidebic]

No, the way he did it is correct. He showed that if there are two points where the function evaluates to the same quantity, then the two points must be the same. (f(a)=f(b)=>a=b). As such there cannot be two distinct points mapping to the same quantity in the image, which is the definition of injectivity.

[@8104587]

There is an unstated assumption. f(a)=f(b) AND ab The proof then finds a=b, which is the contradiction

[@Minty_MH]

It seems fine to me. All he did was assume f(a) = f(b) so that the argument inside the outermost f was the same in both lines. Then he used that f was single valued to conclude that their images were equal aka a+1987=b+1987 and so a=b. Seems like a standard direct proof to me?

[@Tehom1]

Neat, but it depends on how you are allowed to construct a function. (Sorry to be that guy) If I'm allowed to construct a function from Z>=0 -> Z>=0 as a limit of functions from Z_(2n+1) -> Z_(2n+1) as n goes to infinity, then it can be done. The simplest example is x -> x + n+1 + 993 (mod 2n + 1).

[@andrewfeng3403]

Don’t understand your logic. Everything he did in the solution seems legal to me.

[@Tehom1]

@@andrewfeng3403 In the face of a counterexample, you can't just say that you can't see a bad step. Anyways, you may be missing the crucial part, that it's dependent on whether you allow constructing the function as the limit of functions to/from finite sets.

[@andrewfeng3403]

@@Tehom1 I don’t think you’re right. First, he didn’t assume anywhere in the proof that the function f is not of the type you mentioned. The proof is for any function that potentially satisfies the functional equation. So the proof covers all cases. Second, your function doesn’t make sense, for example, fixing x = 0, the limit doesn’t even exist as n goes to infinity. Finally, since Z>=0 isn’t a dense set, if you define f(x) as a limit of f_n(x) as n -> infty where f_n is of the type you mentioned, then for large enough n, f_n(x) shouldn’t change. So there’s really no point for such a complicated construction.

[@Tehom1]

@@andrewfeng3403 No, that's not how counterexamples work. As to your criticisms, (a) no, you are just denying the premise. "It depends on how you are allowed to construct a function". (b) No, work thru the example. Holding x fixed, f_n(x) changes as n changes.

[@andrewfeng3403]

@@Tehom1 I don't understand your point at all now. Are you saying it is false that there does not exists a function satisfying f(f(x)) = x + 1987? Is your counterexample there to disprove the theorem in question? And b) is exactly the problem I have with your example: f_n(0) as n goes to infinity doesn't even exist because it always changes, how do you define f(x) = lim_{n -> infty} f_n(x) then?