1

Given the function $f: \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Z}^+$

$f(a,b) = b^2 +a$, if $b>a$

or $a^2 +a + b$, if $b<a$,

which associates $a,b \to z$, find its inverse, which associates $z \to a, b$.

mathlearner
  • 903

2 Answers2

2

If you look back at the origin of the problem, this function is a bijection from $\mathbb N \times \mathbb N$ to $\mathbb N$.

To find the inverse, start by finding a $k$ so that $k^2 \leq z < (k+1)^2$.

Than see what happens depending if $z-k^2$ is larger or smaller than $k$.

N. S.
  • 132,525
  • @mathlearner I already told you what to do. Case 1: $z-k^2<k$, try to find $a,b$ in this case by checking the two options of the function (only one will work)... Case 2: $z-k^2 \geq k$, try to find $a,b$... – N. S. Oct 13 '14 at 19:26
  • @mathlearner You know that $0^2 \leq z$ and that at some point $x^2$ gets larger than $z$. Define $k$ to be the largest integer so that $k^2 \leq z$. Since $k$ is the largest $k+1$ cannot have this property. – N. S. Oct 13 '14 at 19:39
  • @mathlearner Or much simpler, pick $k = \lfloor \sqrt{z} \rfloor$. – N. S. Oct 13 '14 at 19:40
  • @mathlearner because $z^2 \geq z$ which means that when $x=z+1$, $x^2$ is already larger than $z$. – N. S. Oct 13 '14 at 19:45
  • @mathlearner If you look at the definition of the function, you should see that in the first case you have $b^2 \leq z < (b+1)^2$. In the second case you have $a^2 <z <(a+1)^2$. So, if you start by finding the last perfect square before $z$, you find $b$ or $a$ depending on which case you are.... Finding one of them is the hard part of the problem.... – N. S. Oct 13 '14 at 19:53
1

The insignt here is that, if $x < y$ then $$(y-1)^2 + (y-1) + x < y^2 < y^2 + x < y^2 + y + x < (y+1)^2$$

Sombeody calculates $f(a,b) = c$, and you are only given c. You find the bigger of the two numbers by calculating $d = \left\lfloor \sqrt{c}\right\rfloor$. Then calculate $e = c - d^2$. If $e < d$, then we are in the $a < b$ case and $(a,b) = (e, d)$. If $e > d$ then we are in the $b < a$ case, and $(a,b) = (d, e - d)$

NovaDenizen
  • 4,216
  • 15
  • 23