2
$\begingroup$

I have the function $f:\mathbb{N}\to \mathbb{N}$ defined by

$$f(i) = i\cdot a + \left\lfloor\frac{i\cdot a}{b-1}\right\rfloor$$

for integers $a,b\geq2$, and I'm trying to find an inverse, so that given $f(i)$ I will be able to extract $i$. My best progress so far was rewriting as

$$\lfloor f(i)\rfloor = \left\lfloor i\cdot\frac{b\cdot a}{b-1}\right\rfloor$$

and then attempting to divide both sides by $b\cdot a / (b-1)$, which I thought I found a simple proof for, but was actually wrong, and the counter example of $\lfloor 1 \rfloor=\lfloor1\cdot 1.5\rfloor$. Now I'm stuck, not sure how to proceed (or if it's even possible). Any advice?

$\endgroup$
1
$\begingroup$

Note that we can express $$f(i)= \left\lfloor i\cdot\frac{b\cdot a}{b-1}\right\rfloor;$$ i.e. the floor function is unnecessary on the left hand side. More generally, we have a function $$f(i) = \lfloor i \cdot r \rfloor$$ where $r > 1$. This makes for a strictly increasing function, as $$f(n + 1) = \lfloor (n + 1) \cdot r \rfloor \ge \lfloor n \cdot r \rfloor + \lfloor r \rfloor \ge f(n) + 1 > f(n).$$ Therefore $f$ is injective, and hence it is invertible on its range (it won't be invertible more generally, unless $r = 1$). It also means we can find a left-inverse $g : \mathbb{N} \to \mathbb{N}$, that is, a function such that $g \circ f$ is the identity on $\mathbb{N}$ (but not necessarily $f \circ g$).

In particular, the following is such a $g$: $$g : \mathbb{N} \to \mathbb{N} : i \mapsto \left\lceil\frac{i}{r}\right\rceil.$$ Suppose $i \in \mathbb{N}$. Then $$(g \circ f)(i) = g(\lfloor i \cdot r \rfloor) = \left\lceil\frac{\lfloor i \cdot r \rfloor}{r}\right\rceil \le \left\lceil\frac{i \cdot r}{r}\right\rceil = i.$$ If $(g \circ f)(i) \le i - 1$, then \begin{align*}\left\lceil\frac{\lfloor i \cdot r \rfloor}{r}\right\rceil \le i - 1 &\implies i - \left\lceil\frac{\lfloor i \cdot r \rfloor}{r}\right\rceil \ge 1 \\ &\implies i + \left\lfloor-\frac{\lfloor i \cdot r \rfloor}{r}\right\rfloor \ge 1 \\ &\implies \left\lfloor\frac{i \cdot r - \lfloor i \cdot r \rfloor}{r}\right\rfloor \ge 1 \\ &\implies {i \cdot r - \lfloor i \cdot r \rfloor} \ge r > 1, \end{align*} which is a contradiction. Hence $(g \circ f)(i) = i$ for all $i$.

$\endgroup$
  • $\begingroup$ This makes perfect sense, thank you! $\endgroup$ – Nescio Jun 11 '18 at 17:08

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.