Browse · MathNet
PrintXX OBM
Brazil algebra
Problem
Let . Find all functions which satisfy for all .
Solution
First of all, is injective: indeed, .
Moreover, takes all integer values bigger than : if then for some and .
Notice that the values of such that are all even; since is injective, can't be bigger than for every odd. This means that all odd numbers are taken by to numbers not exceeding . By the pigeon hole principle, there are two different odd numbers and such that , contradiction. So there is no such function.
Moreover, takes all integer values bigger than : if then for some and .
Notice that the values of such that are all even; since is injective, can't be bigger than for every odd. This means that all odd numbers are taken by to numbers not exceeding . By the pigeon hole principle, there are two different odd numbers and such that , contradiction. So there is no such function.
Final answer
no function exists
Techniques
Injectivity / surjectivityPigeonhole principle