47
\$\begingroup\$

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 , so your score is the sum of the number of bytes of both functions and the shortest valid answer wins.

\$\endgroup\$
9
  • \$\begingroup\$ May the functions return a string? \$\endgroup\$ Apr 6, 2017 at 12:11
  • \$\begingroup\$ @SIGSEGV I'd say yes, but only if they also take a string as input, so they can be composed without having to insert any type conversion. \$\endgroup\$ Apr 6, 2017 at 12:12
  • \$\begingroup\$ Aww darnit, I tried conversion to string to make the other function unable to edit the results further. \$\endgroup\$ Apr 6, 2017 at 12:13
  • 1
    \$\begingroup\$ @Fatalize Correct. Each must be a function of type ℤ → ℤ. \$\endgroup\$ Apr 6, 2017 at 12:17
  • 1
    \$\begingroup\$ @Bijan both positive and negative. \$\endgroup\$ Apr 8, 2017 at 17:07

4 Answers 4

20
\$\begingroup\$

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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ f and g can be unnamed functions, so you can drop four bytes. \$\endgroup\$ Apr 7, 2017 at 9:15
  • \$\begingroup\$ You can define (1-x%2*2) as a variable to save a few bytes. \$\endgroup\$
    – AAM111
    Apr 10, 2017 at 21:27
  • \$\begingroup\$ Here's a complete code to play with import numpy as np; import matplotlib.pyplot as plt; xrange=np.arange(-3,4); f=lambda x:(1-x%2*2)*(2*x*x+(x<0)); g=lambda x:(1-x%2*2)*(2*x*x+(x>0)); plt.plot(xrange, map(f, xrange), 'ro'); plt.plot(xrange, map(g, xrange), 'go'); plt.plot(xrange, map(f, map(g, xrange)), 'b--'); plt.plot(xrange, map(g, map(f, xrange)), 'y--'); plt.show(); You can replace ; with linefeeds for readability. \$\endgroup\$ Apr 21, 2017 at 14:33
16
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Nice, this is exactly the reference solution provided in the competition this is from. (I assume you came up with it independently?) \$\endgroup\$ Apr 6, 2017 at 14:21
  • \$\begingroup\$ @MartinEnder, I've seen this problem somewhere before. Possibly on math.SE. \$\endgroup\$ Apr 6, 2017 at 14:30
16
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ In Haskell, (^) is integer exponentiation. \$\endgroup\$ Apr 7, 2017 at 7:43
  • 1
    \$\begingroup\$ @user1502040 It can't handle negative exponents. \$\endgroup\$
    – xnor
    Apr 7, 2017 at 8:34
  • 1
    \$\begingroup\$ Since you're not calling g yourself you can save two bytes by making it unnamed. \$\endgroup\$ Apr 7, 2017 at 9:14
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.