12
$\begingroup$

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}$$

$\endgroup$
  • 2
    $\begingroup$ What do you mean by $N^*$? $\endgroup$ – Erick Wong Aug 19 '15 at 13:47
  • 2
    $\begingroup$ Is $S$ necessarily a set of distinct positive integers? (that is, are you allowing things like $\frac 12 + \frac 12=1$). $\endgroup$ – lulu Aug 19 '15 at 13:52
  • 2
    $\begingroup$ @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. $\endgroup$ – Arthur Aug 19 '15 at 13:54
  • 2
    $\begingroup$ @lulu every set has distinct elements $\endgroup$ – user261263 Aug 19 '15 at 13:54
  • 3
    $\begingroup$ 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... $\endgroup$ – barto Aug 30 '15 at 16:08
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Something is wrong because $f(n)=1$ for all $n\in\mathbb{N}^*$ is a solution. $\endgroup$ – Batominovski Aug 31 '15 at 9:49
  • 1
    $\begingroup$ @Batominovski f is injective $\endgroup$ – user261263 Aug 31 '15 at 9:55
  • 2
    $\begingroup$ Sorry, didn't see that you wanted "one-to-one" functions. However, I would be interested to see all solutions, not just injective ones. $\endgroup$ – Batominovski Aug 31 '15 at 9:56
  • $\begingroup$ @barto Right, thanks $\endgroup$ – user261263 Aug 31 '15 at 10:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Colm Bhandal Sep 5 '15 at 20:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.