How to prove there exists a polynomial with degree at most $100\sqrt{nk}$ satisfying this condition 
Show that for arbitrary positive integers $n,k$,  there exists a
  polynomial $p(x)$, with degree at most $100\sqrt{nk}$, such that
  $$p(0)>(|p(1)+|p(2)|+\cdots+|p(n)|)+(|p(-1)|+|p(-2)|+\cdots+|p(-k)|)$$

This problem is problem A.511 from Problems in Mathematics, May 2010. See here. This problem doesn't have a solution posted.
Thank you. 
 A: Ah, this is a cutie. I'll not pay much attention to exactly how many zeroes are in the constant $100$ (this requires just being more accurate in the estimates than I'm currently willing to), but the general idea is simple. 
Step 1: Assume $k\le n$. Put $A(z)=\prod_{m=1}^k(1-\frac{x^2}{m^2})$. This way we need to care only of values $P(x)$ with $k<x\le n$. Note that $|A(x)|\le \frac{2^k x^{2k}}{k!^2}\le \left(2e\frac xk\right)^{2k}$ in this range.
Step 2: If for every $N\ge 1$, we could construct a polynomial $B(z)$ of degree about $\sqrt N$ such that $B(0)=1$ and $\max_{[1,N]}|\sqrt xB(x)|< \frac 1{2e}$, we could just put $N=\sqrt{n/k}$ and $P(z)=A(z)B(z/k)^{8k}$ or something like that (assuming $k>2$, say).
Step 3: To build $B(z)$, we shall, indeed, use a Taylor polynomial. However, we'll approximate not $F(z)=\frac{\sin z}{z}$, but $F(z)=\frac{\sin 2e{\sqrt z}}{2e\sqrt{z}}$ with the standard (positive on $(0,+\infty)$) branch of $\sqrt z$, which still makes sense and is entire because $\frac{\sin z}{z}$ has only even powers in its Taylor expansion. To estimate the error of approximation in the disk $|z|<N$, just notice that $|F|\le e^{8e\sqrt N}$ in the disk $|z|<2N$ and use the standard Cauchy coefficient bound to see that the terms with powers beyond some big multiple of $\sqrt N$ do not really matter.
