# Determine all one to one functions $f:\mathbb{N}^* \rightarrow \mathbb{N}^*$ having the following property:

Determine all one to one functions $f:\mathbb{N}^* \rightarrow \mathbb{N}^*$ (where $\mathbb{N}^*$ means all positive integers) having the following property:

For all $S$, where $S$ is a finite set of positive integers so that: $$\sum_{s \in S} \frac{1}{s} \in \mathbb{N}^*$$ it implies: $$\sum_{s \in S} \frac{1}{f(s)}\in \mathbb{N}^*$$

Of course, the identical function is a solution, but how about other solutions?

Update

I was able to prove (with help from a friend) that $f(n)=n, \forall n$ using induction and:

Egyptian fractions theorem. For every positive rational r and positive integer N, there exists a set $\{ n_1, . . . , n_k\}$ of positive integers such that $n_i > N$ for every $i = 1, 2, . . . , k$ and $$r = \sum_{1\le i \le k}\frac {1}{n_i}$$

• What do you mean by $N^*$? – Erick Wong Aug 19 '15 at 13:47
• Is $S$ necessarily a set of distinct positive integers? (that is, are you allowing things like $\frac 12 + \frac 12=1$). – lulu Aug 19 '15 at 13:52
• @lulu A set, more or less by definition, has only distinct elements. If you want to allow more than one of any given element, then it's usually called a multiset. – Arthur Aug 19 '15 at 13:54
• @lulu every set has distinct elements – user261263 Aug 19 '15 at 13:54
• Note that $f(1)=1$. The only non-trivial solution to $\frac1a+\frac1b+\frac1c\in\Bbb N$ is $(2,3,6)$ and permutations, so that gives us some information to start with... – rabota Aug 30 '15 at 16:08

We have $f(1)=1$ and $f(n) \ge 2, \forall n \ge 2$.

Let $n ≥ 2$ be un integer. Using Egyptian fractions theorem, we can write: $$1 − \frac {1}n = \sum_{s \in S} \frac{1}{s}$$ where $S$ is a set of integers greater than $n(n + 1)$. Therefore: $$1=\frac {1}n + \sum_{s \in S} \frac{1}{s} =\frac 1{n+1} + \frac 1{n(n+1)} + \sum_{s \in S} \frac{1}{s}$$ From f property, we have: $$\frac {1}{f(n)} + \sum_{s \in S} \frac{1}{f(s)} \in \mathbb{N}$$ and $$\frac 1{f(n+1)} + \frac 1{f(n(n+1))} + \sum_{s \in S} \frac{1}{f(s)} \in \mathbb{N}$$ therefore $$\frac 1{f(n+1)} + \frac 1{f(n(n+1))} - \frac {1}{f(n)} \in \mathbb{Z}$$ But: $$\frac {-1}2 \le - \frac {1}{f(n)} \lt \frac 1{f(n+1)} + \frac 1{f(n(n+1))} - \frac {1}{f(n)} \lt \frac 1{f(n+1)} + \frac 1{f(n(n+1))} \le \frac1{2} + \frac1{2}$$ so $$\frac 1{f(n+1)} + \frac 1{f(n(n+1))} = \frac {1}{f(n)} \tag 1$$ It follows that f is increasing and $f(n) \ge n$. To conclude, it's easy to show, using induction, that $f(n)=n, \forall n$.

Disclaimer

This prove has been sent to me, in a hand written form, by a friend who allowed me to post it here.

Update

I was requested to continue the prove (the induction part). First, because f is increasing and f injective, we have: $f(n) \ge n, \forall n$.

Now suppose $f(k) = k$ and $f(k + 1) > k + 1$ for some $k$. From (1) we have: $$\frac 1{f(k+1)} + \frac 1{f(k(k+1))} = \frac {1}{k} \tag 2$$ and, because $f(n) \ge n, \forall n$: $$\frac 1{k+1} + \frac 1{k(k+1)} \gt \frac {1}{k} \tag 3$$ From (3): $$\frac {1}{k} \gt \frac {1}{k} \tag 4$$ Therefore $f(k+1) = k+1$ if $f(k) = k$.

• Something is wrong because $f(n)=1$ for all $n\in\mathbb{N}^*$ is a solution. – Batominovski Aug 31 '15 at 9:49
• @Batominovski f is injective – user261263 Aug 31 '15 at 9:55
• Sorry, didn't see that you wanted "one-to-one" functions. However, I would be interested to see all solutions, not just injective ones. – Batominovski Aug 31 '15 at 9:56
• @barto Right, thanks – user261263 Aug 31 '15 at 10:07
• I don't quite follow the very last step: the proof by induction. If you have the time, could you add this at the end of the question? Cheers. Otherwise, nice work. Kudos to your friend. – Colm Bhandal Sep 5 '15 at 20:44