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$ – punctured dusk 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 agree to our terms of service, privacy policy and cookie policy