Pigeonhole Principle question - sum of natural numbers

Question

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?

Answer 1

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.

Answer 2

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$.