WakeUp wrote: Define a function $f:\mathbb{N}\rightarrow\mathbb{N}_0$ by $f(1)=0$ and \[f(n)=\max_j\{ f(f)+f(n-j)+j\}\quad\forall\, n\ge 2 \] Determine $f(2000)$. In the max expression : 1) what is the range of $j$ ? 2) what is the meaning of $f(f)$ ?

pco wrote: WakeUp wrote: Define a function $f:\mathbb{N}\rightarrow\mathbb{N}_0$ by $f(1)=0$ and \[f(n)=\max_j\{ f(f)+f(n-j)+j\}\quad\forall\, n\ge 2 \] Determine $f(2000)$. In the max expression : 1) what is the range of $j$ ? 2) what is the meaning of $f(f)$ ? Woops! Edited. But I don't know what the range of $j$ is. This is the exact wording of the problem and it had me confused also; but I'm guessing $j\in\mathbb{N}$ and $j<n$. But this is only a guess!

Ok, then. Let us consider $f(n)=\max_{k\in[1,n-1]}(f(k)+f(n-k)+k)$ Choosing $k=n-1$, we get $f(n)\ge f(n-1)+n-1$ and so $f(n)\ge (n-1)+(n-2)+...+1+f(1)=\frac{n(n-1)}2$ And it is easy to see that $f(n)=\frac{n(n-1)}2$ indeed fits : $f(k)+f(n-k)+k=\frac{k(k-1)}2+\frac{(n-k)(n-k-1)}2+k$ $=\frac{n(n-1)}2-k((n-1)-k)\le f(n)$ with equality when $k=n-1$ So $\boxed{f(2000)=1999000}$

Dear mathlinkers, You can find the problems from Taiwan Olympiad 2000 at the book of Titu: Mathematical Olympiads Contests Around the World 2000-2001 . I have looked for the statement of j and the true range of j is: 0 < j < (n+1)/2 . So the solution of pco is false with this statement and for solution the author used a very complicated method. The answer is f(2000)=10864. A hint for the solution from the book: For each positive integer n, we consider the binary representation of n. Consider the substrings of the representation formed by removing at least one digit from the left side of the representation, such that the substring so formed begins with a 1. We call the decimal values of these substrings the tail-values of n. Also, for each 1 that appears in the binary representation of n, if it represents the number 2^k, let (2^k).(k/2) be a place-value of n. Let g(n) be the sum of the tail- and place-values of n. We prove by induction on n that f(n) = g(n). For convenience, let g(0) = 0. It is clear that g(1) = 0....

One of the best problems I encountered in my Math Olympiad career (which was ~8 years ago). Claim: $f(2n)=2f(n)+n$ and $f(2n+1)=f(n)+f(n+1)+n$. Proof: Go by induction; suppose this is true for smaller $n$. We know $f(2n)$ is the maximum of \[f(2k)+f(2n-2k)+2k,\,\,\,1\leq k\leq n/2,\] and \[f(2k-1)+f(2n-2k+1)+2k-1,\,\,\,1\leq k\leq (n+1)/2.\] The first expression equals\[2(f(k)+f(n-k)+k)+n\leq 2f(n)+n\] by induction hypothesis and the definition of $f$. As for the second, if $k=1$ we get \[f(2n-1)+1=f(n)+f(n-1)+n< 2f(n)+n\] since by definition we have $f(n)>f(n-1)$; if $k=(n+1)/2$ we get exactly $2f(n)+n$ again, and when $2\leq k\leq n/2$ we get\[f(k)+f(k-1)+f(n-k)+f(n-k+1)+(2k+n-2),\] which equals\[(f(k)+f(n-k)+k)+(f(k-1)+f(n-k+1)+(k-1))+(n-1)\leq 2f(n)+n-1.\] Similarly, $f(2n+1)$ is the maximum of \[f(2k)+f(2n-2k+1)+2k,\,\,\,1\leq k\leq n/2,\]and \[f(2k+1)+f(2n-2k)+(2k+1),\,\,\,0\leq k\leq (n-1)/2.\] The first expression equals \[2f(k)+f(n-k)+f(n-k+1)+n+2k,\] which then equals \[(f(k)+f(n-k)+k)+(f(k)+f(n+1-k)+k)+n\leq f(n)+f(n+1)+n.\] For the second, if $k=0$ we get\[f(2n)+1=2f(n)+n+1\leq f(n)+f(n+1)+n\] due to what we just proved; if $2\leq k\leq (n-1)/2$ we get \[f(k)+f(k+1)+2f(n-k)+(n+2k+1),\] which is just\[(f(k)+f(n-k)+k)+(f(k+1)+f(n-k)+(k+1))+n\leq f(n)+f(n+1)+n.\] Finally: \[f(1)=0,f(2)=1,f(3)=2,f(4)=4,f(7)=9,f(8)=12,f(15)=28,f(16)=32,f(31)=75,f(32)=80,f(62)=181,f(63)=186,f(125)=429,f(250)=983,f(500)=2216,f(1000)=4932,f(2000)=10864.\]