Let $k$ be a fixed positive integer. Find all functions $f :\mathbb{N}\to\mathbb{N}$ such that for any distinct positive integers $a_1,a_2,\ldots,a_k$, there exists a permutation $(b_1,b_2,\ldots,b_k)$ of $\{a_1,a_2,\ldots,a_k\}$ such that $f(a_1)/b_1+ f(a_2)/b_2+\ldots+ f(a_k)/b_k$ is a positive integer.

Please help, I'm really stuck here, I guess $f$ must be constant or linear, I tried induction on $k$, but the permutation mess everything, the case $k=1$ is trivial, idk how to deal with $k>1$.

  • $\begingroup$ Constants don't work. If $f(n)=c$ for all $n$ then, for large $a$ $\frac {f(a)}a$ is not an integer. $f(n)=cn$ works for $c\in \mathbb N$. $\endgroup$
    – lulu
    Nov 3 '20 at 9:47
  • 1
    $\begingroup$ More broadly, if, for every $n$ we have $n\,|\,f(n)$ then $f(n)$ works. thus $f(n)=n^m$ works but so do "piecewise" functions like $f(n)=n^2$ if $n$ is even and $f(n)=n^5$ if $n$ is odd. $\endgroup$
    – lulu
    Nov 3 '20 at 9:51
  • $\begingroup$ @lulu and OP I wrote a solution last night but it was messy. Just cleaned it up. Please let me know if you find anything wrong. Thanks. $\endgroup$
    – Neat Math
    Nov 4 '20 at 12:55

Lemma: If $p$ is a prime number, $A, B, M \in \mathbb{N}$, $p \nmid B$, $M$ and $p$ are coprime, then the sum $\frac{A}{M} + \frac{B}{p}$ cannot be a positive integer.

Proof of the lemma is straightforward: $\frac{A}{M} + \frac{B}{p}=N \Rightarrow pA + MB=NMp \Rightarrow p | MB$, a contradiction.

Now we prove $\forall n \in \mathbb N$, we must have $n|f(n)$. We construct a sequence $a_1, a_2, \ldots, a_k$ in the following fashion: $a_1=n$, and $\forall 2\leqslant j \leqslant k$,

$$ a_j > \max\{a_m, f(a_m) , \forall 1\leqslant m<j\}, \text{ and } a_j \text{ is a prime number}. $$

Then there's a permutation $\{ b_j, 1\leqslant j \leqslant k \}$ of $\{ a_j, 1\leqslant j \leqslant k \}$ such that $S \equiv \sum_{j=1}^k f(a_j)/b_j$ is a positive integer. Assume $b_i = a_k$ for some index $i$, we have

$$ S = \frac{A}{\prod_{j=1}^{k-1} a_j} + \frac{f(a_i)}{a_k}. $$

From the lemma, since $\gcd(\prod_{j=1}^{k-1} a_j, a_k)=1$, we know $a_k | f(a_i)$. By construction $a_k > f(a_j), \forall j<k$, therefore $i=k, a_k | f(a_k)$.

It follows that $\sum_{j=1}^{k-1} f(a_j)/b_j$ is also a positive integer. By the same reasoning we have $b_{k-1} = a_{k-1}, a_{k-1} | f(a_{k-1})$. We repeat this process until finally we have $f(n)/n$ as a positive integer.

On the other hand if $n|f(n), \forall n\in \mathbb{N}$, the identity permutation guarantees that $\sum f(a_j)/a_j$ is a positive integer. $\blacksquare$

  • $\begingroup$ I don't understand "we pick prime number $p_2, p_2, \cdots, p_k$ in the following manner, $p_2>\max (n,f(n))$. Should the first $p_2$ be a $p_1$? $\endgroup$
    – lulu
    Nov 4 '20 at 13:36
  • $\begingroup$ No it's $p_2$. The first number is $n$. $\endgroup$
    – Neat Math
    Nov 4 '20 at 13:39
  • $\begingroup$ Why does $p_2$ appear twice on your list? $\endgroup$
    – lulu
    Nov 4 '20 at 13:40
  • $\begingroup$ Ah, I see. Your goal is to define the numbers $a_i$ and $a_1=n$. It's confusing to write $p_2, p_2, \cdots, p_k$ though. $\endgroup$
    – lulu
    Nov 4 '20 at 13:41
  • $\begingroup$ Yes I agree. I want to emphasize all numbers are prime except for $n$. Later I used $a_j$ instead. $\endgroup$
    – Neat Math
    Nov 4 '20 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.