Romania TST 2013

[Phlembac Adib Hasan]

Find all injective functions $f:\mathbb N\to \mathbb N$ such that for each finite subset $\mathbb S$ of $\mathbb N$, \[\sum_{s\in \mathbb S}\frac 1 s\in \mathbb N\Longrightarrow \sum_{s\in \mathbb S}\frac {1} {f(s)}\in \mathbb N\]

[Fm Jakaria]

My solution:

Claim: For each positive integer n, there exists an infinite sequence of nonempty finite sets $A_1,A_2,….$ of positive integers with $n < min(A_1)$ and for all i;
$Max(A_i) < min(A_{i+1})$ , and $\sum_{s \in A_i}\dfrac{1}{s} = \dfrac {1}{n}$.
Proof: In fact, it is well-known that for any positive rational number r, and any positive integer a;
there exists a finite set S with $min(S) > a$ and $\sum_{s \in A_i}\dfrac{1}{s} = r$.
For a proof(with elementary construction), see the paper ‘A chain reaction process in number theory’ by Truman Botts.
The desired sequence can now easily be constructed :
Always set $r = \dfrac {1}{n}$. In step 1, set $a = n$, to get $S = A_1$.
If step i gives $A_i$; in step (i+1), set $a = max(A_i)$ to get $S = A_{i+1}$.

With the claim, we inductively establish that $f(n) = n$. $\dfrac{1}{1} \in N$, so is $\dfrac{1}{f(1)}$. So $f(1) = 1$.
In inductive step, let for some $n >1$; for all $m<n$, $f(m) = m$. As f is injective, we have
$f(n) \geqslant n$. Now as in the claim, fix the first (n) terms $A_1,…,A_{n}$ of the sequence. Here {$n$},$A_1,…,A_{n}$ are pairwise disjoint.
Then we have $n-1$ equations , for each i with $1\leqslant i \leqslant (n-1)$:
$\sum_{s \in A_i}\dfrac{1}{s} = \dfrac {1}{n}…(M_i)$.
Let us add to both side of $(M_i)$ the following term;
$\sum_{s \in A_j, 1\leqslant j \leqslant (n) , j \neq i}\dfrac{1}{s} = \dfrac{n-1}{n}$. Then
$1 = \dfrac{1}{n} + \sum_{s \in A_j , 1\leqslant j \leqslant (n), j \neq i}\dfrac{1}{s}
= \sum_{s \in A_i}\dfrac{1}{s} + \sum_{s \in A_j , 1\leqslant j \leqslant (n), j \neq i}\dfrac{1}{s}$
$\rightarrow$ both $\dfrac{1}{f(n)} + \sum_{s \in A_j ,1\leqslant j \leqslant (n), j \neq i}\dfrac{1}{f(s)}$ $\mathbb \in {N}$ and
$\sum_{s \in A_i}\dfrac{1}{f(s)} + \sum_{s \in A_j ,1\leqslant j \leqslant (n), j \neq i}\dfrac{1}{f(s)}$
$\mathbb \in {N}$.
So their subtraction, $\dfrac{1}{f(n)} - \sum_{s \in A_i}\dfrac{1}{f(s)} = S_i$ $\mathbb \in {Z}$.
Now adding equations $(M_i)$,
$1 = \dfrac{1}{n}+ \sum_{1\leqslant i \leqslant (n-1)} \sum_{s \in A_i}\dfrac{1}{s}$.
$\rightarrow \frac{1}{f(n)} + \sum_{1\leqslant i \leqslant (n-1)} \sum_{s \in A_i}\frac{1}{f(s)} = S_n$
$\mathbb \in {N}$.
Summing, $\sum_{1 \leqslant i \leqslant (n)}S_i = \dfrac{n}{f(n)}$ is integer . So $f(n) \leqslant n$.
Then $f(n) = n$, and the induction is complete.