Pigeonhole Principle question - sum of natural numbers Let $f:\{1,2,...,15\} \rightarrow \Bbb N$ be a function such that $\sum_{i=1}^{15} f(i) =100$.
$f(15+1)$ is defined to be $f(1)$.
I have shown that $14\leq f(i)+f(i+1)$ for some $1\leq i \leq15$ using the pigeonhole principle.
Now I need to show that $21\leq 2f(i)+f(i+1)$ for some $1\leq i \leq15$. 
Any ideas?
 A: We have 
$$f(1)+f(2)+f(2)+f(3)+f(3)+f(4)+...+f(15)+f(16)=2(f(1)+f(2)+f(3)+...+f(15))=200$$
This implies
$$2f(1)+f(2)+2f(2)+f(3)+2f(3)+f(4)+...+2f(15)+f(16)=200+f(1)+f(2)+...+f(15)=300$$
If $2f(i)+f(i+1)<21$ for every $i$ with $1\le i\le 15$, then the second sum can
only be $300$, if $2f(i)+f(i+1)=20$ for all $i$ with $1\le i \le 15$.
This implies $$2f(1)+f(2)=2f(2)+f(3)=2f(3)+f(4)+...+2f(14)+f(15)=2f(15)+f(1)=20$$
So, we have $f(3)-f(2)=2(f(2)-f(1)) , f(4)-f(3)=2(f(3)-f(2)) ...$
If $|f(3)-f(2)|\ge 1$, then $|f(15)-f(14)|\ge 2^{12}$ which is not possible
because the $f(i)$ are non-negative and $f(15)$ or $f(14)$ would be larger than $100$, the
sum of the $f(i)$
So, $f(3)=f(2) , f(4)=f(3) ... f(15)=f(14)$ and finally $f(1)=2f(15)-f(2)=f(2)$
because of $f(2)=f(15)$. But this is also not possible because of
$2f(1)+f(2)=3f(1)=20$, which has no solution in the natural numbers.
A: Let $g(i)=2f(i)+f(i+1)$; then $\sum_{i=1}^{15}g(i)=300$, so the mean of the numbers $g(i)$ is $20$. To show that one of them is at least $21$, it suffices to show that they cannot all be $20$.
If $g(i)=20$, then $f(i+1)$ is even; thus, if all $g(i)=20$, then all $f(i)$ are even. This rules out all combinations except the following:
$$\begin{array}{rcc}
f(i):&10&8&6\\
f(i+1):&0&4&8
\end{array}$$
Thus, we must have $f(i)\in\{6,8,10\}\cap\{0,4,8\}$, or $f(i)=8$, for $i=1,\ldots,15$, and this clearly isn’t a solution. Thus, it’s impossible that all $g(i)=20$, and we must have some $g(i)\ge 21$.
