Function Logic

Algebra Level 5

There are $2$ strictly increasing functions $f$ and $g$ that map positive integers to positive integers. It is known that $f(f(x)) = g(x)$ for all positive integers $x$ . It is given that $g(x) = ax+b$ .

Jasmine and Luke and perfect logicians and functional experts. Jasmine is told the value of $a+b$ . Luke is given $b$ .

Jasmine: If you tell me $a$ , I would know infinitely many values of $f(x)$ .
Luke: If I told you $a$ , and you were given a random positive integer $y$ , could you determine $f(y)$ .
Jasmine: It depends.
Luke: Then, if I were given any $y$ , I could determine $f(y)$ .
Jasmine: Then so could I.

Jasmine is then given $y = 2019$ . What value of $f(2019)$ does she give?

Based on the topic of this question .

The answer is 3016.

1 solution

Alex Burgess
Mar 25, 2019

First we can note that if $g(1) \neq 3,4$ we cannot uniquely determine $f(1)$ or any other value of $f(x)$ .

Hence "Jasmine: I know infinitely many values of $f(x)" \implies a + b = 1, 3, 4$ .

Second, we can work out that for all strictly increasing, linear $g(x)$ we can uniquely determine ALL values of $f(x)$ .

"Jasmine: It depends." $\implies k \neq 3$

"Luke: Then, if I was given $y$ , I could determine $f(y)$ " means that Luke, from knowledge of both $a$ and $b$ , can uniquely determine all values of $f(x)$ . There is only one linear $g(x)$ , with $g(1) = 4$ , that does this, and that is $g(x) = 2x + 2$ . With \g(1) = 1, b = 0, -2) uniquely determines all values of $f(x)$ . $b = 2$ is the only value that is only present in one of $n = 1,4$ .

Using this, one can determine that $f(f( 2^n + 2^{n-1} - 2))) = f(2^{n+1} - 2)) = 2^{n+1} + 2^n - 2$

For $x = (2^n - 2) + c < 2^n + 2^{n-1} - 2, f(x) = (2^n + 2^{n-1} - 2) + c$ , as $f(x)$ is strictly increasing.

From these values we can determine that, for $x = (2^n + 2^{n-1} - 2) + c < 2^{n+1} - 2, f(x) = (2^n + 2^{n-1} - 2) + 2c$ .

$2019 = (1024 + 512 - 2) + 485 < 2048 - 2$ , Hence $f(2019) = (2048 - 2) + 2*485 = 3016$ .

Where does the form of the argument x come from?

glenn perilpaddock - 2 years, 2 months ago

Do you mean the $2^n + 2^{n-1} - 2$ and $2^n - 2$ part? This can be determined by working through the values we already know: $\begin{matrix} x: & 1 &2&4&6 &10& ... & 2^n - 2 & 2^n + 2^{n-1} - 2 & 2^{n+1} - 2\\ f(x): & 2&4&6&10 &14 & ... & 2^n + 2^{n-1} - 2 & 2^{n+1} - 2 & 2^{n+1} + 2^{n} - 2\\ g(x): & 4&6&10&14 &22 & ... & 2^{n+1} - 2 & 2^{n+1} + 2^{n} - 2 & 2^{n+2} - 2 \end{matrix}$

In binary, this is: $\begin{matrix} x: & 1&10&100&110&1010& ... & 111...110& 1011...110 & 1111...110\\ f(x): & 10&100&110&1010&1110 & ... & 1011...110 & 1111...110 & 10111...110\\ g(x): & 100&110&1010&1110 &10110 & ... & 1111...110 & 10111...110 & 11111...110 \end{matrix}$

Alex Burgess - 2 years, 2 months ago

f(x) need not be a linear function. It can be any function. This is where I got stuck

Srikanth Tupurani - 2 years, 2 months ago

f(x) needs to be linear because of that f(f(x)) is also linear

Matteo Bianchi - 1 year, 10 months ago

$f(x)$ Linear $\implies f(f(x))$ Linear.

But

$f(f(x))$ Linear $=\not\implies f(x)$ Linear.

We are given the latter, and hence can't claim $f(x)$ is linear.

Alex Burgess - 1 year, 10 months ago

Function Logic

The answer is 3016.

1 solution

0 pending reports