10
$\begingroup$

Here's my puzzle:

Write two unary functions f, g and provide an input x so that only the combination f(g(x)) will yield the result y but no other combination of them does - even if applied multiple times in any order.

The functions should use standard arithmetic operations, the numbers should be small integers, too keep it simple (so that the solution y = f(g(x)) is obvious to everyone). If that is not possible, feel free to use more advanced operations or rational numbers.

I am still trying to solve it myself. I just made it up[1], I don't think it's a well-known problem.

I have tried some simple additions and multiplications, but it proved unexpectedly hard. Maybe I just don't know the right mathematical tool or can't see the pattern. I thought about prime numbers, but they don't really seem to help here. Some (counter)examples:

  • 1, *3, *5 - but also 1 *5 *3 = 15
  • 0, +3, *5 - but also 0 *5 +3 *5 = 15
  • 1, +3, *5 - but also 1 *5 +3 +3 +3 +3 +3 = 20
  • 1, *5, +2 - but also 1 +2 +2 +2 = 7
  • 1, +3, /2 - but also 1 +3 +3 +3 /2 +3 /2 /2 = 2
  • 2, +3, ^2 - but also 2 ^2 ^2 +3 +3 +3 = 25

1: If you're curious, I am trying to write a test for a computer program that implements function composition.

$\endgroup$
4
  • 1
    $\begingroup$ If you are allowed to apply some index $j$ in how the functions are composed, you could use $f(x) = k^j\cdot x$ -- assuming that $k^j$ is greater than any input $x$. For binary $x$, we can use $f(x) = 2^j\cdot x$ to get a unique representation. $\endgroup$ Jun 27, 2016 at 6:56
  • $\begingroup$ @CarlLöndahl: no indices. You don't know how often, at which point in the sequence, or whether at all the function is used. Notice you can also choose x, it doesn't need to work on any input. $\endgroup$
    – Bergi
    Jun 27, 2016 at 6:59
  • 2
    $\begingroup$ If you use $f(x)=x+1$, $g(x)=\frac{1}{x+1}$, with the starting value of $1$, then every positive rational number is the result of exactly one sequence of $f$ and $g$. $\endgroup$
    – f''
    Jun 27, 2016 at 12:41
  • $\begingroup$ @f'' Please post that as an answer! $\endgroup$
    – Bergi
    Jun 27, 2016 at 15:58

3 Answers 3

13
$\begingroup$

How about the following for a single operator version:

Let $f(x)=x/2$, let $g(x)=x-3$, and let $x=13$, with $y=5$.

If we perform $f(g(x))$, we get $y$. If we perform $f$ before $g$, we will get a non-integer (and applying $f$ or $g$ after this will not help). If we perform $g$ more than once, then the resulting value is too low to apply $f$ to reach $y$. We cannot apply $g$ by itself any number of times to reach $y$. Once we reach $y$, using either function will make the result too low to return to $y$ (since both functions are strictly decreasing).

$\endgroup$
3
  • 4
    $\begingroup$ The reverse, 5, *2 and +3 seems to be even simpler $\endgroup$
    – Bergi
    Jun 27, 2016 at 8:21
  • 1
    $\begingroup$ @Bergi I originally avoided functions of the form *n and +m given the number of counterexamples that contained them; it seems I came full circle. I suppose the strictly increasing version is simpler, although the strictly decreasing version was easier to see the proof in my head before writing down. $\endgroup$
    – Vaekor
    Jun 27, 2016 at 8:36
  • $\begingroup$ Wouldn't $f(g(g(16))$ generate $5$? I guess that doesn't use $13$ as input. $\endgroup$
    – Yakk
    Jun 27, 2016 at 14:06
6
$\begingroup$

OK, I figured out one solution. Binary, as mentioned by Carl Löndahl in the comments, should've been obvious. It hit me though when I looked at a string concatenation.

Start with 1, use λx → x⋅2+0 and λx → x⋅2+1 as functions. Or bitshift and xor, if you want.

I'm still wondering though whether there is a solution using a single operator per function.

$\endgroup$
1
$\begingroup$

$f(n) = p^n, g(n) = q^n$ such that $\gcd(p, q) = 1, p, q \in \mathbb Z^+.$

This works for all positive $n$. Mind you, the numbers you get will be pretty big. An integer power of $p$ cannot be equal to an integer power of $q$, so there is no $h(n) \in \{\textrm{compositions of }f, g\}$ such that $(f\circ h)(n) = (g \circ h)(n)$.

$\endgroup$
2
  • $\begingroup$ p, q > 1 :-) $\endgroup$
    – Bergi
    Feb 4, 2018 at 16:46
  • $\begingroup$ Right, I seem to have backspaced that portion... $\endgroup$
    – Martin
    Feb 4, 2018 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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