Inequality with a rational polynomial Let $$P(x)=x^{n-1}+a_{n-2}\,x^{n-2}+a_{n-3}\,x^{n-3}+\cdots+a_0\in\mathbb{Q}[x]$$ be a monic rational polynomial of degree $n-1$. 
I want to show that, for every set of $n$ distinct integers $\{x_1,x_2,\cdots,x_n\}$, there exists $i\in\{1,2,\cdots,n\}$ such that 
$$\big|P(x_i)\big|\ge\frac{(n-1)!}{2^{n-1}}\,.$$
I don't know how approach this problem.
Note that the degree is $n-1$ yet there are $n$ integers. 
 A: This problem is true for any monic polynomial $P(z)\in\mathbb{C}[z]$ of a given degree $n-1$, where $n\in\mathbb{N}$, and for any pairwise distinct $x_1,x_2,\ldots,x_n\in\mathbb{C}$ such that $x_i-x_j\in\mathbb{Z}$ for all $i,j=1,2,\ldots,n$.  Without loss of generality, we shall assume that $\text{Re}\left(x_1\right)<\text{Re}\left(x_2\right)<\ldots<\text{Re}\left(x_n\right)$.
We note from the Lagrange Interpolation Theorem that
$$P(z)=\sum_{i=1}^n\,P\left(x_i\right)\,\prod_{j\in[n]\setminus\{i\}}\,\left(\frac{z-x_j}{x_i-x_j}\right)\,,$$
where $[n]:=\{1,2,\ldots,n\}$.  Since $P$ is monic, 
$$\sum_{i=1}^n\,\frac{P\left(x_i\right)}{\prod_{j\in[n]\setminus\{i\}}\,\left(x_i-x_j\right)}=1\,.$$
Using the Triangle Inequality and the assumption that the $x_i$'s are mutually distinct with integral differences, we conclude that $$\prod_{j\in[n]\setminus\{i\}}\,\left|x_i-x_j\right|\geq (n-i)!\,(i-1)!$$ for all $i\in[n]$, and that
$$\sum_{i=1}^n\,\binom{n-1}{i-1}\,\frac{\big|P\left(x_i\right)\big|}{(n-1)!}\geq 1\,.$$
I leave the rest to you.  

 A final hint is that $$\sum_{i=1}^n\,\binom{n-1}{i-1}\,\frac{1}{2^{n-1}}=1\,.$$  Note also that this bound is sharp by taking $x_i=i$ and $$P(i)=(-1)^{n-i}\,\frac{(n-1)!}{2^{n-1}}$$ for each $i=1,2,\ldots,n$. 

