Hints: (1) The function $ f$ is nondecreasing. (2) Let $ a: = f(1)$. Then, show that $ f(n) \geq \left(f(a) - 1\right)n + 1$ and use this to prove that $ f(a) \geq a^{k} - a^{k - 1} + 1$ for all natural number $ k$. Thus, $ f(1) = 1$. (3) Let $ t$ be the maximum integer such that $ f(t) = 1$. Show that $ f(n) \leq n + t$ for all $ n$. (4) Suppose there exists $ b$ such that $ f(b) > b$, say, $ f(b) = b + d$. Show that $ f(kb) \geq kb + k(d - 1) + 1$ for all $ k \in \mathbb{N}$. Use this to justify that $ d = 1$. (5) From (4), $ f(n) \leq n + 1$ for all $ n$. In fact, for a given $ N$, $ f(N)$ can be anything from $ 1$, $ 2$, ..., $ N + 1$. (5.1) Let $ A < N$. Define $ f(n) = 1$ if $ n \leq A$ and $ f(n) = A$ if $ n > A$. Then, $ f$ satisfies the condition and $ f(N) = A$. (5.2) If $ f$ is the identity function, then $ f(N) = N$. (5.2) Any function in the form $ f(n) = c\left\lfloor\frac {n}{c}\right\rfloor + 1$, where $ c > 1$ is an integer, satisfies the condition. When $ c = N$, we have $ f(N) = N + 1$.

(1) $ 1 \leq f(2007) \leq 2007$ if $ f(2007) = 2007 - k$, let $ f(x) = x - k (x \geq k + 1)$ and $ f(x) = 1 (x \leq k)$. (2) $ f(2007) = 2008$ let $ f(2m) = 2m, f(2m - 1) = 2m$ (3) if $ f(n) = n + k ( k \geq 2)$ because $ f(m + n) \geq f(m) + f(f(n)) - 1 \geq f(m)$, $ f$ is increasing function. Let $ m$ is greatest integer satisfy $ f(m) = 1$ (i) If $ f(\alpha n) \geq \alpha (n + k - 1)$ then $ f((\alpha + 1)n) \geq f(n) + f(f(\alpha n)) - 1 \geq n + k + f(\alpha (n + k - 1)) - 1$ $ \geq n + k + f(\alpha n) - 1 \geq n + k + \alpha(n + k - 1) - 1 = (\alpha + 1)(n + k - 1)$ Therefore, for all a, $ f(an) \geq a(n + k - 1)$ $ f(an + a(k - 1)) \geq f(a(k - 1)) + f(f(an)) - 1 \geq f(a(k - 1)) + f(a(n + k - 1)) - 1$ $ f(a(k - 1)) \leq 1 \Rightarrow f(a(k - 1)) = 1$ for all a. Contradiction to (i) $ \therefore f(2007)$'s possible value is 1 to 2008

The author is Nikolay Nikolov

orl wrote: Consider those functions $ f: \mathbb{N} \mapsto \mathbb{N}$ which satisfy the condition \[ f(m + n) \geq f(m) + f(f(n)) - 1\] for all $ m,n \in \mathbb{N}.$ Find all possible values of $ f(2007).$ Author: unknown author, Bulgaria The function $ f(n) = n$ when $ 2007 \nmid n$ and $ f(n) = n + 1$ when $ 2007 \mid n$ satisfies the equation. The function $ f(n) = 1$ when $ n \le k$ and $ f(n) = n - k + 1$ when $ n > k$ satisfies the equation for all $ k \in \mathbb{N}$. So it is possible to archeive $ f(2007) \in \{1,2,3,...,2008\}$. First of all $ f(n + 1) \ge f(n)$, so $ f$ is non-decreasing. Assume that $ f(n) > n + 1 \iff f(n) = n + c, c \ge 2$. Then $ f(2n) \ge f(n) + f(f(n)) - 1 = n + c - 1 + f(n + c) \ge n + 2(c - 1) + 1$, and by induction we get $ f(2^rn) \ge 2^rn + 2^r(c - 1) + 1$. Therefore: $ f(2^rn + 1) \ge f(f(2^rn)) \ge f(2^rn + 2^r(c - 1) + 1)$, so $ f(2^rn + 1) = f(2^rn + 1) = \cdots = f(2^rn + 2^r(c - 1) + 1)$ For all $ m \in \mathbb{N}$ choose $ r$ such that $ 2^r(c - 1) > m$. Then: $ f(2^rn + 1 + m) \ge f(2^rn + 1) + f(f(m)) - 1$. But $ f(2^rn + 1 + m) = f(2^rn + 1)$, so we obtain $ f(f(m)) \le 1$ or $ f(f(m)) = 1 \forall m \in \mathbb{N}$. Hence $ 1 = f(f(n)) = f(n + c) \ge f(n)$ giving $ f(n) = 1$, and we obtain a contradiction. Hence $ f(n) \le n + 1 \forall n \in \mathbb{N}$, and the only possible values are from the set $ \{1,2,3,...,2008\}$ which can all be reached.

Mathias_DK wrote: by induction we get $ f(2^rn) \ge 2^rn + 2^r(c - 1) + 1$. it's false for n=1

Dumel wrote: Mathias_DK wrote: by induction we get $ f(2^rn) \ge 2^rn + 2^r(c - 1) + 1$. it's false for n=1 What do you mean by that?

Mathias_DK wrote: Then $ f(2n) \ge f(n) + f(f(n)) - 1 = n + c - 1 + f(n + c) \ge n + 2(c - 1) + 1$ and by induction we get $ f(2^rn) \ge 2^rn + 2^r(c - 1) + 1$. the basis of induction is false, because for r=1 we get $ f(2n) \ge 2n + 2(c - 1) + 1$ not $ f(2n) \ge n + 2(c - 1) + 1$ as you wrote above

Dumel wrote: Mathias_DK wrote: Then $ f(2n) \ge f(n) + f(f(n)) - 1 = n + c - 1 + f(n + c) \ge n + 2(c - 1) + 1$ and by induction we get $ f(2^rn) \ge 2^rn + 2^r(c - 1) + 1$. the basis of induction is false, because for r=1 we get $ f(2n) \ge 2n + 2(c - 1) + 1$ not $ f(2n) \ge n + 2(c - 1) + 1$ as you wrote above Ok. You mean $ r = 1$. That is just a typo. I forgot the $ 2$ in front of the $ n$. So the proof is ok - I can't edit my old post though.

ok you're right sorry for talking rot

Let $P(m,n)$ be the assertion that $f(m+n) \ge f(m) + f(f(n))-1$. We claim that $f(2007) \in \{ 1,2,\dots,2008 \}$. For all $k \in \{1,2,\dots, 2007 \}$ a function such that $f(2007)=k$ can be given by $f(n)=1$ for $1 \le n \le 2006$, $f(2007)=k$ and $f(n)=n$ for $2008 \le n$. A function such that $f(2007)=2008$ can be given by $f(n)=n$ for $2007 \not | n$ and $f(n)=n+1$ for $2007 |n$. Now we will prove that $f(n) \le n+1$. Assume for contradiction that there exists $k$ such that $f(k) = k+c$ where $c>1$. By $P(n,m-n)$ where $m>n$, it follows that $f(m) \ge f(n) + f(f(m-n))-1 \ge f(n)$. Hence $f$ is nondecreasing. Now we will prove by induction that $f(ik) \ge ik+i(c-1)+1$ for all $i \in \mathbb{N}$. Note that we have shown the case where $i=1$. Now assume that the claim holds for $i=1,2,\dots, n$. By $P(nk, k)$, it follows that $f((n+1)k) \ge f(nk)+f(f(k))-1=f(nk) + f(k+c)-1$ which since $f$ is nondecreasing satisfies that $f(nk) + f(k+c)-1 \ge f(nk)+k+c-1=(n+1)k+(n+1)(c-1)+1$. This implies that for any $m$, there exists $p \in \mathbb{N}$ such that $f(p)-p \ge m$. Now let $q$ be such that $f(q)-q \ge k$. By $P(f(q)-q, q)$, it follows that $f(f(q) \ge f(f(q)-q)+f(f(q))-1$ which implies that $f(f(q)-q) \le 1$. However, since $f$ is nondecreasing $f(f(q)-q) \ge f(k) = k+c > c > 1$ which is a contradiction. Hence $f(n) \le n+1$, which implies that $f(2007) \in \{ 1,2,\dots,2008 \}$.

thank you very much, NIKOLAI NIKOLOV for wonderful problems. Someone know official solution of the problem? [which in shortlist or by autor!]

Please check my construction

We claim that for any such function $f,$ we have $f(2007)\in \{1,2,\dots, 2008\}.$ We first show everything is achieveable: - In particular, $f(2007)=2008$ is witnessed by taking $f(2007k+m)=2007k+1,\ (0\leq m < 2007),$ and - $f(2007)=k\leq 2007$ is achieved by taking $f(1)=\dots=f(2008-k)=1,f(2009-k)=2,f(2010-k)=3,\dots$ Now we show that we cannot have $f(n_0)\geq n_0+2$ for any $n_0,$ which will imply that these are the only possible values. We first claim that $f$ is nondecreasing. Indeed, $P(n, m-n)$ for $m>n$ shows that $f(m)\geq f(n)+f(f(m-n))-1\geq f(n).$ Now assume FTSOC that we have $f(n_0) = n_0+d, d\geq 2.$ We can show with induction that $f(kn_0)\geq kn_0+(k-1)d-(k-1):$ \[f((k+1)n_0)\geq f(kn_0)+f(f(n_0))-1= f(kn_0)+f(n_0+d)-1\geq f(kn_0)+f(n_0)-1\geq (k+1)n_0+kd-k.\]In particular, this shows that $f(x)-x$ can be arbitrarily large. Then \[P(f(x)-x,x)\implies f(f(x))\geq f(f(x)-x)+f(f(x))-1\implies f(\text{big})=f(f(x)-x)=1,\]whence from the nondecreasing property we conclude that $f$ must be constant at $1.$ This contradicts $f(n_0)\geq n_0+2,$ and we conclude with the solutions stated at the beginning.

Here's a solution sketch: You get these series of things using an inductive-like telscoping procedure: $\bullet f(1) = 1$ $\bullet$ For $r \neq 0$, if you have f(a) = qa+r, then - $q = 1 \rightarrow f(r) = 1$ - $q \geq 2 \rightarrow f(r) = 1 \text{ and } f(qa+r) = 1$ $\bullet$ For $r = 0$, f(a) = 1 for $q \geq 2$. $\bullet$ Otherwise, $f(a) \leq a$. So let N be the largest integer for which $f(N) = 1$. This is a thing because not how $\forall n \leq N, f(n) = 1$. Hence, if N was arbitrarily large, all values under N would have a value of 1, which implies that N is the constant function. So we assume otherwise. It follows that $f(n) \leq n+r_N \leq n+N$ for $0 \leq r_N \leq N$ and all $n \in \mathbb{N}$ from the above. Then you use fact that f is nondecreasing and induction to get: If $f(b) = b+d$, then $f(kb) \geq kb + k(d-1)+1$. But for large enough k if $d \neq 1$, it breaks down from my thing. So d = 1. So $f(a) \leq a+1$. For construction, look at Generic_Username ^. So answer is f(2007) = {$1, 2, \dots 2008$}

Can anyone verify whether my solution is correct? We claim that $f(2007) \in \{1,2,\dots , 2008\}$. Firstly, assume that $f$ is non-constant, otherwise $f\equiv 1$. Denote by $P(m,n)$ the given assertion: $$f(m+n) \ge f(m) + f(f(n))-1$$Now, $P(1,1) \implies f(2) \ge f(1)+f(f(1))-1 \ge f(1)$. Also, $P(2,1) \implies f(3) \ge f(2) + f(f(1))-1 \ge f(2)$. Inductively we see that $$f(m+1) \ge f(m) \ \forall m \in \mathbb{N}.$$This shows that $f$ is a non-decreasing function. Also, $f(1) = \text{min} \{f(1),f(2),\dots\}$. Now, we proceed with the following claim: Claim: $f(1)=1$. $\rightarrow$ Let $f(1)=k$, for some $k>1$. Then, $P(1,1) \implies f(2) \ge (k-1) + f(k) > f(k)$. Since $f$ is non-decreasing, it follows that $2>k$, contradiction. Hence, $f(1)=1$. Now, $P(1,n) \implies f(1+n) \ge f(1) +f(f(n)) -1 =f(f(n))$. Again, non-decreasing nature of $f$ implies $n+1 \ge f(n) \forall n \in \mathbb{N}$. Thus, $f(n) \le n+1$. Now, we give a construction which shows that all values up to $n+1$ are achievable (for $n=2007$).

Suppose there existed some $x$ such that $f(x) \ge x+2$. Claim 1: $f$ is nondecreasing. Proof: Since $m+n>m$ and $f(m+n)\ge f(m)$, we get $f$ is nondecreasing. $\square$ Claim 2: $f(k)-k$ grows arbitrarily large as $k$ increases. Proof: Since $f(x)>x$, we know $f(f(x)) > x$. Then \[ f(2x) \ge f(x)+f(f(x))-1 \ge 2f(x)-1 \ge 2x+3,\]and similarly, \[f(3x) \ge f(2x)+f(f(x))-1 \ge 2x+3+f(x)-1 \ge 3x+4, \]and so on. In general, we can prove by induction that $f(nx) \ge nx + (n+1)$. In particular, $f(nx)-nx = n+1$ for any $n$, which means $f(k)-k$ can grow arbitrarily large over all $k$. $\square$ Claim 3: $f$ is identically 1. Proof: $P(f(x)-x,x)$ gives $f(f(x)) \ge f(f(x)-x) + f(f(x))-1$, so $f(f(x)-x) \le 1$, which means $f(f(x)-x)=1$. Since $f(x)-x$ can grow arbitrarily large by claim 2, we conclude $f(N)=1$ for arbitrarily large $N$. But since $f$ is nondecreasing, $f\equiv 1$. $\square$ But now $1=f(x)\ge x+2$, contradiction. Hence, we cannot have an $x$ such that $f(x)\ge x+2$, and therefore $f(2007)\le 2008$. We can actually get $f(2007)=k$ for any $1\le k \le 2008$. If $k\le 2007$, just take $f(1)=f(2)=\cdots=f(2006)=1$, $f(2007)=k$, and $f(2008)=2008, f(2009)=2009, \ldots$. If $k=2008$, then let $f(x)$ be the greatest number at most $x$ that is 1 mod 2007.

Answer. $f(2007)\in\{1,2,\ldots,2008\}$. Let $P(m,n)$ be the assertion. $P(m,1)\implies f(m+1)\geq f(m)+f(f(1))-1$. By induction, $f(m)\geq (m-1)f(f(1))+f(1)-(m-1)$ for all $m$. Thus, $f(f(m))\geq (f(m)-1)f(f(1))+f(1)-(f(m)-1)$. Taking here $m=1$, we get $$f(f(1))\geq (f(1)-1)f(f(1))+f(1)-(f(1)-1)\implies 0\geq 1+(f(1)-2)f(f(1))\implies f(1)=1.$$Thus, $f(m+1)\geq f(m)\forall m\in\mathbb{N}$. Hence we have $f(n)\geq f(m)$ for all $n\geq m$. $P(1,n)\implies f(n+1)\geq f(f(n))\implies n+1\geq f(n)$. Thus, $2008\geq f(2007)$. Now, we claim that every such value is achievable. For $f(2007)=1$, we can just use function $f(m)=1\forall m\in\mathbb{N}$. For $2\leq f(2007)=a\leq 2007$, we can just use function $f(m)=1\forall m\leq 2007-a$ and $f(m)=m-(2007-a)\forall m\geq 2008-a$. For $f(2007)=2008$, we can use $$ f(m) = \begin{cases} m & \text{if } m\not\equiv 0\pmod{2007}\\ m+1 &\text{if } m\equiv 0\pmod{2007} \end{cases} .$$We are done.

The answer is $1\le n\le 2008$. The construction for $n<2007$ is $f(x)=1$ for $1\le x\le n$ and $f(x)=n$ otherwise. The construction for $n=2007$ is the identity. The construction for $n=2008$ is $f(2007m)=2007m+1$ and $f(x)=x$ otherwise. It is easy to verify that the above functions work. We will proceed to prove that $n>2008$ is impossible. Note that the function is nondecreasing by $f(1,x)$. Now, suppose that $f(2007)=n>2008$; then, $f(m,2007)$ gives that $f(m+2007)\ge f(m)+f(n)-1\ge f(m)+2008$. Let $N=1991104216969$; we know that $f(2007N)\ge 2008N+1$, then $f(1,2007N)$ gives that $f(2007N+1)\ge f(f(2007N))\ge f(2008N+1)>f(2007N+1)$.

Lowkey finding construction is hard We claim that $f(m)\le m+1$ for all $m\in \mathbb{N}.$ Note that $f(m+1)\ge f(m)+f(f(1))-1\ge f(m)$ so the function is non-decreasing. Assume for the sake of contradiction that $f(m)\ge m+2.$ Then substitute $m=f(m)-m$ and $n=m$ We get $f(m+f(m)-m)\ge f(f(m)-m)+f(f(m))-1,$ so $f(f(m)-m)=1.$ We claim that there must exist an integer $k$ such that $f(k)\ge k+c$ for any finite positive integer $c.$ Our proof is as follows, using induction: Base Case: Our assumption proves $c=2$ and note that $f(2m)\ge f(m)+f(m+2)-1\ge m+2+f(m)-1\ge 2m+3$ so $c=3$ also is true. Induction Hypothesis: Suppose $f(k)\ge k+d$ for some $k,d.$ Induction Step: Note that $f(2k)\ge f(k)+f(f(k))-1\ge k+d+f(k+d)-1\ge 2k+2d-1,$ so if the statement is true for $c=d$ then it is true for all $c\le 2d-1.$ Taking this induction step enough times we can find that there must exist an integer $k$ such that $f(k)\ge k+c$ for any finite positive integer $c.$ Now, if $f(k)-k\ge c$ then $f(f(k)-k)\ge f(c)$ so $1\ge f(c)$ which implies $f(c)=1$ ... for all $c$ which is clearly a contradiction. Therefore, $f(m)\le m+1$ which proves $f(2007)\le 2008.$ We provide the construction $f(1)=f(2)=\dots=f(2006)=1,$ which satisfies the equation, and then $f(2007)=k,$ $f(2008)=k+1,$ $f(2009)=k+2$ and so on $f(2007+c)=k+c.$ If both $m,n\le 2006$ obviously this works, and if $m\ge 2007>n$ then $f(m+n)=m+n+k-2007,$ $f(m)=m+k-2007,$ and $f(f(n))=1$ so the function works. If $n\ge 2007>m$ then $f(m+n)=m+n+k-2007$ and $f(f(n))=n+2k-4014$ while $f(m)-1=0$ so this is satisfied as long as $m\ge k-2007.$ If both are $\ge 2007$ then we have $f(m+n)=m+n+k-2007,f(m)+f(f(n))-1=m+n+3k-6022$ which is satisfied as long as $2k\le 4015$ or $k\le 2007.$ Then $m\ge k-2007$ is made true anyway. Finally, we need to find a construction for $f(2007)=2008,$ so we provide $f(m)=2\lceil\frac{m}{2}\rceil$ which is easy to test that it works.

Note that $f$ is non decreasing. The identical 1 function obviously works. Hence assume $f$ is not identically 1. Let $M$ be the maximum such that $f(x)=x+M.$ It follows that $2x+M\geq 2f(2x)\geq f(x)+f(f(x))-1=f(x+M)+x+M-1\geq f(x)+x+M-1=2x+2M-1.$ Thus $M\leq 1\implies f(x)\leq x+1.$ So $f(2007)\in [1,2008].$ We can indeed construct such a function. For any $k\in [1,2008)$ let $f(x)=\max\{\lfloor kx/2007 \rfloor, 1\}$ and for $k=2008$ let $f(x)=x+1$ if $2007\nmid x$ or $f(x)=x,$ otherwise. Clearly these work.

mathleticguyyy wrote: Let $N=1991104216969$; Any motivation behind this number? TheCosineLaw wrote: Now, $P(1,n) \implies f(1+n) \ge f(1) +f(f(n)) -1 =f(f(n))$. Again, non-decreasing nature of $f$ implies $n+1 \ge f(n) \forall n \in \mathbb{N}$. rafaello wrote: Hence we have $f(n)\geq f(m)$ for all $n\geq m$. Am I being silly or non decreasing means $f(x)\geq f(y)~\forall x>y$ not $x\geq y.$

The answer is all integers from $1$ to $2008$, inclusive. For $f(2007)=2008$ take $f(x)=2007\left\lfloor \frac{x}{2007}\right\rfloor + 1$ and for $f(2007)=k\le 2007$ take the function $f$ such that $f(2007-k+c)=c$ for all $c\ge 1$ and $f(n)=1$ for all $1\le n\le 2007-k$. Now we show that $f(2007)<2009$ and in general that $f(n)<n+2$. Suppose FTSOC that $f(n)\ge n+2$. Note that \[f(2n)\ge f(n)+f(f(n))-1\ge 2n+3\]and continuing inductively we find that \[f(2^kn)\ge f(2^{k-1}n)+f(f(2^{k-1}n))-1\ge 2^kn+2^k+1\]where we make use of the fact that $f(n+1)-f(n)\ge f(f(1))-1\ge 0$ so that $f$ is nondecreasing. Then note that if $f(x)=x+k$ then we obtain $f(x+k)\ge f(k)+f(f(x))-1$ so that $f(k)=1$, where $k\ge 1$. Using this, we see that $f(2^kn)\ge 2^kn+2^k+1$ implies that $f(2^k+1)=1$ for arbitrarily large $k$, a contradiction. $\blacksquare$

Doing this problem assuming N is positive integers not nonnegative, because someone clarified for me. Also can someone check my solution? After perusing the others it seems like mine is way too short and simple.. Honestly the hardest part was construction which is just intuition lol We claim the answer is all integers from 1 to 2008. First notice f is nondecreasing. $$1,n\implies f(1+n)\ge f(1)+f(f(n))-1\ge f(f(n))\implies 1+n\ge f(n).$$It remains to show that these values all work. For f(2007)=1 take f as constant 1. For $2\le f(2007)\le 2007$ we're motivated to let the inequality hold easily by just making the f() 1s, since they'll cancel out. Indeed, let $f(n)=1\forall n\le 2007-f(2007)$, which evidently has no "bad" impact on the condition, while $$f(n)=n+f(2007)-2007\le n\forall n\ge 2008-f(2007)\implies f(m+n)=m+n+f(2007)-2007\ge f(m)+f(f(n))-1=1\forall m+n\ge 2008-f(2007),m,n\in\mathbb{N},$$while the inequality has equality case for $m+n\le 2007-f(2007)$ since it's just ones on both sides. Finally, for $f(2007)=2008$ take $f(n)=n+1\forall 2007\nmid n$ and $f(n)=n\forall 2007|n$. We can easily check that this works by simply caseworking on whether or not m,n divisible by 2007 in the given condition to see that the ineq holds. $\blacksquare$

Not really hard it's just that there are so many details that it makes this really annoying. We claim that the answer is $f(2007) \in \{1,2,\dots , 2008\}$. To see that these values are achievable, consider the below functions, \[ f(n) = \begin{cases} 1 & n<i+1\\ i & n \ge i+1 \end{cases} \]for $i \le 2007$. To check that this works, we make the simple observation that since $f(n) < i+1$ for all positive integers $n$, $f(f(n))=1$ for all positive integers $n$. Thus, we simply need to check, \[f(m+n) \ge f(m)+f(f(n))-1=f(m)\]which is clear since $f$ is non-decreasing from the nature of the definition. Finally, consider the function, \[ f(n) = \begin{cases} n & 2007 \nmid n\\ n+1 & 2007 \mid n \end{cases} \]To check that this works, we have 4 cases. First, when $2007 \mid n,m$, since it follows that $2007 \mid n+m$, we have \[f(m+n) = m+n+1 \ge m+1 + n+1 -1 =m+1+ f(n+1)-1=f(m) + f(f(n))-1\]when $2007 \nmid n,m$ we have \[f(m+n) \ge m+n = m + n -1 = f(m)+f(n)-1=f(m)+f(f(n))-1\]when $2007 \mid n$ but $2007 \nmid m$, since $2007 \nmid n+m$, \[f(m+n)=m+n \ge m+1 + n+1 -1 =f(m)+f(f(n))-1\]and finally when $2007 \nmid n$ and $2007 \mid m$, we check \[f(m+n) \ge m+n = m+1 + n - 1= f(m)+f(f(n))-1\]so we have checked all cases and indeed these functions work. Now, we shall show that these are indeed the only possibilities of $f(2007)$. We first start off with some bounding. First of all, note that $f$ is increasing. Claim : For all positive integers $n$, $f(n) <2n$. Proof : Say there exists some $n_0 \in \mathbb{N}$ such that $f(n_0)=n_0+m>2n_0$. But then, \begin{align*} f(m+n_0) & \ge f(m) + f(f(n_0)) -1 \\ f(m+n_)) & \ge f(m) + f(m+n_0) - 1\\ 1 &\ge f(m) \end{align*}which due to the domain of $f$ implies $f(m)=1$. But since $f$ is increasing, $f(1)=\dots = f(n) = \dots = f(m) =1$ which is a clear contradiction. Thus, our claim is proved. Now, say $f(2007)=2007+c$. Then, we prove the following result via induction. Claim : For all positive integers $k$, $f(2007\cdot 2^k) \ge 2007\cdot 2^k + 2^kc - (2^k-1)$. Proof : The base case is clear. Now, say the claim is true for some positive integer $k$, note that, \begin{align*} f(2007\cdot 2^{k+1}) &\ge f(2007\cdot 2^k)+f(f(2007\cdot 2^k))-1 \\ &\ge (2007\cdot 2^k + 2^kc - (2^k-1)) + f(2007) -1\\ & = 2(2007\cdot 2^k + 2^kc - (2^k-1))-1\\ & = 2007 \cdot 2^{k+1}+2^{k+1}c-(2^{k+1}-1) \end{align*}But, note that if $c\ge 2$, \[2^{k+1}c-(2^{k+1}-1 \ge 2^{k+1}+1)\]So, \[f(2007 \cdot 2^{k+1}) \ge 2007 \cdot 2^{k+1} + 2^{k+1}+1 \ge 2 \cdot 2007 \cdot 2^{k+1}\]for sufficiently large $k$, which contradicts our previous result. Thus, $c<2$ which finishes the proof.

The answer is $f(2007)$ can be any integer in $\{1,2,\dots,2018\}$. First let's lay out the constructions. Let $T:=f(m+n)+1-f(m)-f(f(n))$. Consider the function $f(n)=\begin{cases} n+1 & 2007\mid n \\ n & 2007\nmid n\end{cases}$. The function works because: If $2007$ doesn't divide both $m,n$ then $T=m+n+1-m-n=1$ if $2007\nmid m+n$ or $T=m+n+1+1-m-n=2$ if $2007\mid m+n$. If $2007$ divides $m$ only then $T=m+n+1-m-1-n=0$. If $2007$ divides $n$ only then $T=m+n+1-m-n-1=0$. If $2007$ divides both $m$ and $n$ then $T=m+n+1+1-m-1-n-1=0$. For this function, $f(2007)=2008$. Let $k\geq 0$ be an integer. Consider the function $f(n)=\begin{cases} n-k & n>k \\ 1 & n\leq k\end{cases}$. This works because: If $m>k$ and $n>k$ then $T=m+n-k+1-m+k-n+k=k+1>0$ or $T=m+n-k+1-m+k-1=n>0$. If $m>k$ and $n\leq k$ then $T=m+n-k+1-m+k-1=n>0$. If $m\leq k$ and $n>k$ then $T=m+n-k+1-1-n+k=m>0$ or $T=m+n-k+1-1-1=m+n-k-1\geq 0$. If $m\leq k$ and $n\leq k$ then $T=m+n-k+1-1-1=m+n-k-1\geq 0$ or $T=1+1-1-1=0$. Now, it's clear that we can pick a $k$ so that $f(2007)$ is any fixed number $\leq 2007$. To conclude the problem, we need to show that $f(2007)\leq 2008$. This follows from the following lemma. Lemma: If $f$ satisfies $f(m+n)\geq f(m)+f(f(n))-1$ for all integers $m,n\geq 1$, then $f(n)\leq n+1$ for all $n\geq 1$. Proof. Indeed, $f(m+n)\geq f(m)$, so $f$ is monotonically increasing. Now, $$f(1+n)\geq f(1)+f(f(n))-1\geq f(f(n)).$$ Suppose $f(k)>k+1$ for some $k$ then $f(f(k))\geq f(k+1)$ by monotonicity, so $f(f(k))=f(k+1)$. Suppose that $f(2^n k)\geq 2^n k+2^n+1$ then $$f(2^{n+1}k)\geq f(2^n k)+f(f(2^n k))-1\geq 2f(2^nk)-1=2^{n+1}k+2^{n+1}+1.$$So by induction $f(2^n k)\geq 2^n k+2^n+1$ for all $n$. In particular this implies that, for every $n$ there is a $x_0$ such that $f(x_0)\geq x_0+n$. Now take $t>1$ such that $f(f(t))>1$. Let $x\geq y+t$ then $$f(x)\geq f(y+t)\geq f(y)+f(f(t))-1>f(y).$$Take $x_0$ such that $f(x_0)\geq x_0+t$ then the previous observation implies that $f(f(x_0))>f(x_0)$ i.e. $f(x_0+1)>f(x_0)\geq x_0+t$. Thus $f(x_0+1)\geq x_0+1+t$, and so by induction $f(n)\geq n+t$ for all $n\geq x_0$. Also this implies $f(n+1)>f(n)$. Thus $f(x)>f(y)$ if $x>y\geq x_0$. Now for large $N$ we have $f(N)>N+1>x_0$ but then $f(f(N))>f(N+1)$, a contradiction. This proves the claim. ////

huashiliao2020 wrote: Also can someone check my solution? After perusing the others it seems like mine is way too short and simple.. Honestly the hardest part was construction which is just intuition lol ... First notice f is nondecreasing. $$1,n\implies f(1+n)\ge f(1)+f(f(n))-1\ge f(f(n))\implies 1+n\ge f(n).$$ Hi! I think this part of your proof isn't completely correct. This is because non decreasing means "$m\geq n\implies f(m)\geq f(n)$" whose contrapositive is "$f(m)<f(n) \implies m<n$". This is subtle because there's no equality here.

Claim: $f(2007)\in \{1, 2, \dots, 2008\}$. Proof: First I will prove that $f(n)\leq n+1$. I will first prove that $f$ is monotonic. As $f$ is a function from positive integers to positive integers, this means $f(k)\geq 1$ for all $k$. Thus $f(n+1)=f(n)+f(f(1))-1\geq f(n)$. Thus $f$ is monotonic. Now suppose that $f(k)= k+c$ for $c\geq 2$. Suppose \[f(2^{m-1}k)= 2^{m-1}k+2^{m-1}c-2^{m-1}+1\]Thus by applying the fact that $f(n)\geq f(n-1)$ and that $c\geq 2$ so $2^{m-1}k+2^{m-1}c-2^{m-1}+1>2^{m-1}k$ we get: \[f(2^mk)=f(2^{m-1}k)+f(f(2^{m-1}k))-1\geq 2f(2^{m-1}k)-1=2^mk+2^mc-2^m+1\]Thus as we have the base case that $f(k)=k+c$, this must hold for all values of $m$ by induction. Thus we can find an $m$ where $f(2^mc-2^m+1)\> 1$. Thus for that $m$ we get: \[f(2^mk+2^mc-2^m+1)=f(2^mc-2^m+1)+f(f(2^mk))-1=f(2^mc-2^m+1)+f(2^mk+2^mc-2^m+1)-1>f(2^mk+2^mc-2^m+1)\]This is clearly a contradiction, thus $c\leq 1$. Thus $f(n)\leq n+1$ for all $n$. Now I will provide a construction for all the values in: \[\{1, 2, \dots, 2008\}\]Consider the functions: \[ f(n) = \begin{cases} 1 & n<i+1\\ i & n \ge i+1 \end{cases} \]Clearly these work for $i\leq 2007$. To obtain $f(2007)=2008$ consider: \[ f(n) = \begin{cases} n+1 & 2007\mid n \\ n & 2007 \nmid n \end{cases} \]This clearly works.