See all problems here

We'll prove by induction that $f(n) = n$ for all $n \in \mathbb{N}$. For the base case, setting $S = \{1\}$ in the given yields $f(1) = 1$. Now suppose the result holds for all $n < N$. Call a representation of a natural number $n$ a set $\{a_1, a_2, \dots, a_k\}$ with $n < a_1 < a_2 < \dots < a_k$ and \[\sum_{i = 1}^{k}{\frac{1}{a_i}} = \frac{1}{n}\] At least one representation $r$ of $N$ exists (see here, for instance). Furthermore, by applying the transformation $a \in r \rightarrow \{a + 1, a(a + 1)\}$ as many times as is necessary, we can generate arbitrarily many disjoint representations of $N$; in particular, we can generate $N$ of them, $r_1, r_2, \dots, r_N$. Now, let \[S_0 = \bigcup_{i = 1}^{N}{r_i}\] \[S_j = \bigcup_{i = 1}^{j - 1}{r_i} \cup \{N\} \cup \bigcup_{i = j + 1}^{N}{r_i}\] Then since the $S_j$ all satisfy the problem condition, for all $0 < a \le N$, \[\Bigg| \sum_{s \in S_a}{\frac{1}{f(s)}} - \sum_{s \in S_0}{\frac{1}{f(s)}}\Bigg| \in \mathbb{Z}\] since both sums are themselves integers. This can be rewritten \[\Bigg| \sum_{s \in r_a}{\frac{1}{f(s)}} - \frac{1}{f(N)} \Bigg| \in \mathbb{Z}\] so that \[\sum_{s \in r_a}{\frac{1}{f(s)}} = \frac{1}{f(N)} + z_a\] for some $z_a \in \mathbb{Z}$. Summing over $a = 1, 2, \dots, N$ gives \[\frac{N}{f(N)} + z = \sum_{a \in [N]}{\sum_{s \in r_a}{\frac{1}{f(s)}}} = \sum_{s \in S_0}{\frac{1}{f(s)}} \in \mathbb{Z}\] where $z = \sum_{a}{z_a} \in \mathbb{Z}$ as well. Then $N/f(N) \in \mathbb{Z}$, yet $f(N) \ge N$ by injectivity and the inductive hypothesis. It follows that $f(N) = N$.

First easy to see $f(1)=1$ now, denote $g(n)=\frac{1}{f(n)}$. Now$g(2)+g(3)+g(6)=g(2)+g(4)+g(6)+g(12)=g(2)+g(3)+g(7)+g(42)$. So that implies $\{f(2),f(3),f(6)\}=\{2,3,6\},\{f(2),f(3)\}=\{2,3\}.\{f(2),f(6)\}=\{ 2,6\}$. Clearly that implies $f(2)=2,f(3)=3,f(6)=6$. Now also $\{f(4),f(12)\} =\{4,12\}$. Again from $g(2)+g(6)+g(12)+g(5)+g(20)=1$ we get $f(12)=12\implies f(4)=4$. Similarly from above expression $\{f(5),f(20)\}=\{5,20\}$. Now from $ g(2)+g(6)+g(12)+g(5)+g(21)+g(420)=1$ we get $f(5)=5,f(20)=20$. Now observe whenever we get $f(n)=n$ then also we get $f(n(n-1))=n(n-1)$. Now certainly we can write $\sum g(a_i)+\sum g(b_i)+g(n-1)=1$, where $a_i=b_i(b_i-1)$ and $n-1>a_i$ and can't be written as $b_i(b_i-1)$ and $f(n-1)=n-1$. Now $\sum g(a_i)+\sum g(b_i)+g(n)+g(n(n-1))=1$ and that implies $\{f(n),f(n(n-1))\}=\{n,n(n-1)\}$. Also note $\sum g(a_i)+\sum g(b_i)+g(n)+g(n(n-1)+1)+g((n(n-1)+1)(n^2-n))=1$. So clearly that would imply $f(n)=n$. Otherwise we wouldn't able to write $n$ as $b_i(b_i-1)$. If that would be, then just by induction hypothesis we would be done since that comes $f(a_i)$. And so $f(n)=n$ for all $n\in\mathbb N$.

Clearly $f(1)=1$ . Notice that $A=\sum_{i=1}^{n-1}\frac{1}{i(i+1)} +\frac{1}{n} =1 $ and $B=\sum_{i=1}^n\frac{1}{i(i+1)} +\frac{1}{n+1}=1$ $\forall n\in\left\{3,4,...\right\}$ , so $B-A$ is an integer . since $f$ is injective and $f(1)=1$ , $f(n)\geq2$ for all integers n greater than 1 . Using this inequality $0+0-\frac{1}{2} \leq \frac{1}{f(n(n+1))}+\frac{1}{f(n+1)}-\frac{1}{f(n)} < \frac{1}{2}+\frac{1}{2}+0$ . Which implies $\frac{1}{f(n(n+1))}+\frac{1}{f(n+1)}=\frac{1}{f(n)}$ (*) , and $f$ is increasing ( Remember that $n>2$ ) $\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1\Rightarrow \frac{1}{f(2)}+\frac{1}{f(3)}+\frac{1}{f(6)}=1$ ( Using $f(n)\geq2$ ) $\Rightarrow \left\{f(2),f(3),f(6)\right\}=\left\{2,3,6\right\}$ , since the positive integer solution of the equation $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$ with distinct x,y,z is $\left\{2,3,6\right\}$ . Clearly $f(3)\not=6$ ( otherwise $f(6)<f(3)$ ) . If $f(3)=2$ , $\frac{1}{f(2)}+\frac{1}{f(6)}=\frac{1}{2}$ $ \Rightarrow \frac{1}{f(4)}+\frac{1}{f(12)}=\frac{1}{2}$ $\Rightarrow \left\{f(4),f(12)\right\}=\left\{3,6\right\}$ which is a contradiction since $f$ is injective . Therefore $f(2)=2$ , $f(3)=3$ , $f(6)=6$ $\Rightarrow f(4)=4 , f(5)=5$ , because $f$ is increasing. We'll use induction to prove that $f(n)=n \forall n\in\left\{3,4,...\right\}$ Base step : $f(4)=4$ ( We finished it ) Assume that it's true for all $k<n$ , and we'll prove it for $n$ . By hypothesis and (*) . $f(n-2)=n-2$ and $f(n-1)=n-1$ $\Rightarrow f((n-2)(n-1))=(n-2)(n-1)$ , but $n<(n-2)(n-1)$ $\forall n\geq4$ . which implies $f(n)=n$ .

I don't understand! This problem very easy or i am wrong. Since given condition, $ \displaystyle\sum_{s\in S}^{}\frac{1}{s} $ is an integer then $ \displaystyle\sum_{s\in S}^{}\frac{1}{f(s)} $ is an integer , if $ S $={$n,n,...,n$} with $ \frac {1}{n}+...+\frac{1}{n}=1 $ then $ \frac{1}{f(n)}+ ...+\frac{1}{f(n)} $ is integer. Hence, \[ f(n) \le n .\] We have that $f(1)=1$ and $f$ - injective . So, $f(n)=n.$ I think this is true.

The thing is, $S$ is a set - it cannot have duplicate elements.

I understand ! Thank you, very much. Siddingss's solution is very nice!

My solution: https://www.dropbox.com/s/dwqpzgty5rlrclq/Romania%20TST%202013.docx?dl=0

We can prove for all n : $ \frac{1}{f(n)}=\frac{1}{f(n+1)}+\frac{1}{f(n(n+1))} $. and $f$ is increasing and ...

siddigss wrote: Which implies $\frac{1}{f(n(n+1))}+\frac{1}{f(n+1)}=\frac{1}{f(n)}$ (*) , and $f$ is increasing ( Remember that $n>2$ ) Sorry but we only have this if $n$ and $n+1$ don't have form $i(i+1)$. How can we show that $f$ is increasing?

@above you can use the identity $\frac{1}{x} = \frac{1}{x+1} + \frac{1}{x(x+1)}$ to fix the proof in those two cases (replace the offending duplicates as many times as needed to make all the terms distinct). For $f$ being increasing just note $\frac{1}{f(n)} = \frac{1}{f(n+1)} + [\text{a positive number}]$ for all $n > 2$.

The part when you need to show that $\frac{1}{f(n(n+1))}+\frac{1}{f(n+1)}=\frac{1}{f(n)}$ comes from the Egyptian fractions theorem by showing that $\sum\limits_{s\in S}\frac{1}{s} + \frac{1}{n}$ and $\sum\limits_{s\in S}\frac{1}{s} + \frac{1}{n+1}+ \frac{1}{n(n+1)}$ are integers.

$S={1}$ $\frac{1}{f(1)}$ is integer. $$f(1)=1$$$$S= \frac{1}{n},\frac{1}{n},\frac{1}{n},....,\frac{1}{n}$$$\frac{n}{f(n)}$ is integer. $$f(n)\le n$$$f$ is injective.By induction $f(n)=n$ $$ very easy problem for p3$$

Yea very easy bcs it's wrong. You can't take $n$ number of $n$s as set can't have duplicate elements.