1

Let $A = {1, 2, ..., 2014}$. Find the number of functions $f: A \rightarrow A$ satisfied the following properties.

  1. There exists $k \in A$ such that $f$ is non-decreasing function on $\{1, 2, ..., k\}$ and $f$ is non-increasing function on $\{k, k+1,..., 2014\}$.

  2. $|f(n+1)-f(n)| \leq 1 \;\;\forall n= 1, 2, ..., 2013$.

  3. $f(1) = f(2014) = 1$.

My attempt :

Let $f$ be function such that f(k) is the maximum value.

$f(1) \leq f(2) \leq ... \leq f(k)$.

$f(k) \geq f(k+1) \geq ... \geq f(2014)$.

Let $f(k) = l$

so $1 \leq f(i) \leq l \;\;\forall i= 2, 3, ..., k-1$.

$l \leq f(i) \leq l \;\;\forall i= k+1, k+2, ..., 2013$.

Please suggest how to proceed.

user403160
  • 3,286

1 Answers1

1

$f$ must step up to a maximum, stay at that maximum (perhaps just for one point), then decrease back to $1$. Let the maximum value be $m$, then define $p$ as the first $n$ where $f(n)=m$ and $q$ as the last $n$ where $f(n)=m.$ We have $m-1 \le p \le q \le 2015-m$. The number of functions for a given $m,p,q$ can be counted by finding the number of ways to choose $m-1$ places for the function to step up out of $p-1$ places and similarly $m-1$ places for the function to step down. Now sum over $m,p,q$

Added: a much better approach. Based on the above, there must be an even number of steps up and down. The first half must be up and the last half must be down. There are $2013$ intervals between numbers. Compute the number of ways to pick an even number of them to be steps. Once you choose which gaps to have steps, the function is determined.

Ross Millikan
  • 374,822
  • Since there are 3 variables, I don't know how to find the value of $\sum\binom{p-1}{m-1}\binom{2015-m-q}{m-1}$. Please suggest. – user403160 Apr 27 '17 at 15:42
  • Think about it with $8$ instead of $2014$. Write the values of $f$ in order. You have to go up to a maximum, then back down. The maximum might be $3$, in which case you have two steps up and two steps down. Those steps have seven places they will be. Once you choose those four, $f$ is defined, so there are $7 \choose 4$ functions with maximum value $3$. All you care about is how many subsets of $7$ or $2013$ have an even number of members. – Ross Millikan Apr 27 '17 at 18:19
  • Thank you, Ross. I can do it now. – user403160 Apr 28 '17 at 13:22