f(g(x)) decreases while g(f(x)) increases

Question

For this challenge you need to implement two functions, f and g, on the integers, such that f ∘ g is a strictly decreasing function while g ∘ f is a strictly increasing function. In other words, if you take any two integers a < b, then f(g(a)) > f(g(b)) and g(f(a)) < g(f(b)). There are no restrictions on f and g individually, except that they must each map one integer to another integer.

Please include a short description of f and g and an argument for why they have the required property.

^{Credit: This challenge was inspired by a problem in the 2011 Romanian Master of Mathematics competition (which asks the same thing but on the real numbers, instead of integers). If you really want spoilers, you now know what to search for.}

Rules

• The word "function" in this challenge should be taken in the mathematical sense of mapping one integer to another: you may either write two programs or two functions and use any of the standard methods of receiving input and providing output, as usual. You may use string representations of integers instead of actual integer variables, but the types of input and output should be identical, so that the functions can be composed without manually converting types in between. Remember that conceptually, f and g still need to be functions on ℤ, so you can't cheat by using two different string representations of the same number or anything like that.

• Remember that functions may be unnamed, as long as their name isn't needed by itself or another function you define. If you do name one or both of the functions, you may assume that they exist in the same program, so that they may refer to each other in their implementation (e.g def f(x): return -g(x) in Python).

• The usual integer overflow rules apply: your solution must be able to work for arbitrarily large integers in a hypothetical (or perhaps real) version of your language in which all integers are unbounded by default, but if your program fails in practice due to the implementation not supporting integers that large, that doesn't invalidate the solution.

• You may use any programming language, but note that these loopholes are forbidden by default.

• This is code-golf, so your score is the sum of the number of bytes of both functions and the shortest valid answer wins.

Answer 1

Python, 68 characters

f=lambda x:(1-x%2*2)*(2*x*x+(x<0))
g=lambda x:(1-x%2*2)*(2*x*x+(x>0))

f maps negative numbers to odd numbers and positive numbers to even numbers, and even numbers to positive numbers and odd numbers to negative numbers, with the output magnitude increasing strictly with the input magnitude.

g does the same, except it maps negative numbers to even numbers and positive numbers to odd numbers.

f ∘ g maps negative → even → positive and positive → odd → negative.
g ∘ f maps negative → odd → negative and positive → even → positive.

Therefore f and g have the desired properties.

Answer 2

Python, 40 bytes

f=lambda x:x*(-1)**x
g=lambda x:3*f(x)+1

Try it online! Some outputs are floats that equal integers because (-1)**(-3) gives a float for instance.

Based off ideas from Peter Taylor. The function f negates odd numbers and leaves even ones unchanged. The function g does the same, then applies the monotonic parity-switching map x -> 3*x + 1.

Since f(f(x)) = x, we have g(f(x)) = 3*f(f(x))+1 = 3*x+1 increasing.

For f(g(x)) = f(3*f(x)+1), the idea is that exactly one of the inner and outer f flips sign, making it decreasing.

• For even x, f(x) = x, but f(3*x+1) = -3*x-1 because 3*x+1 is odd.
• For odd x, f(x) = -x, and f(-3*x+1) = -3*x+1 because -3*x+1 is even.

We now only need the even and odd inputs interleave in a decreasing way, which holds because -3*x±1 is decreasing regardless of how the signs are chosen. This is why the 3* is needed.

A Haskell port is 25 bytes:

f x=x*(-1)**x
g x=1+3*f x

Try it online!

Answer 3

CJam (17 bytes)

Function f (named F because CJam only allows upper-case names):

{W1$2b,#*}:F

Function g (anonymous):

{F2*}

Online demo

This saves a byte by relying on a implementation detail of CJam which is arguably a bug: when doing base conversions it uses absolute value. 2b, therefore gives the number of bits in the absolute value of its argument, so f negates precisely those numbers whose absolute value has an odd number of bits. g applies f and then doubles (changing the parity of the number of bits).

So applying f and then g leaves sign unchanged and doubles, mapping x to 2x. Applying g and then f changes the sign exactly once and doubles, mapping x to -2x.

Answer 4

Pyth, 34 Bytes

This is just a direct translation of my Python answer.

*-1*2%Q2+*2*QQ<Q0
*-1*2%Q2+*2*QQ>Q0