42
\$\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\$
  • \$\begingroup\$ May the functions return a string? \$\endgroup\$ – Matthew Roh Apr 6 '17 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\$ – Martin Ender Apr 6 '17 at 12:12
  • \$\begingroup\$ Aww darnit, I tried conversion to string to make the other function unable to edit the results further. \$\endgroup\$ – Matthew Roh Apr 6 '17 at 12:13
  • 1
    \$\begingroup\$ @Fatalize Correct. Each must be a function of type ℤ → ℤ. \$\endgroup\$ – Martin Ender Apr 6 '17 at 12:17
  • 1
    \$\begingroup\$ @Bijan both positive and negative. \$\endgroup\$ – Martin Ender Apr 8 '17 at 17:07
18
\$\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\$
  • 2
    \$\begingroup\$ f and g can be unnamed functions, so you can drop four bytes. \$\endgroup\$ – Martin Ender Apr 7 '17 at 9:15
  • \$\begingroup\$ You can define (1-x%2*2) as a variable to save a few bytes. \$\endgroup\$ – OldBunny2800 Apr 10 '17 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\$ – Stéphane Gourichon Apr 21 '17 at 14:33
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\$
  • \$\begingroup\$ In Haskell, (^) is integer exponentiation. \$\endgroup\$ – user1502040 Apr 7 '17 at 7:43
  • 1
    \$\begingroup\$ @user1502040 It can't handle negative exponents. \$\endgroup\$ – xnor Apr 7 '17 at 8:34
  • 1
    \$\begingroup\$ Since you're not calling g yourself you can save two bytes by making it unnamed. \$\endgroup\$ – Martin Ender Apr 7 '17 at 9:14
14
\$\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\$
  • \$\begingroup\$ Nice, this is exactly the reference solution provided in the competition this is from. (I assume you came up with it independently?) \$\endgroup\$ – Martin Ender Apr 6 '17 at 14:21
  • \$\begingroup\$ @MartinEnder, I've seen this problem somewhere before. Possibly on math.SE. \$\endgroup\$ – Peter Taylor Apr 6 '17 at 14:30
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.