Let $c = \max S$; there exists some $z\in\mathbb{Z}$ such that $v_2(P(z))=c$. Consider the polynomial $Q(x)\equiv P(x+z)$. $Q$ is also a monic integer-coefficient polynomial with degree $n$, and the set $B= \{ v_2(Q(m))\mid m\in \mathbb{Z}, v_2(Q(m)) \geq 1 \}$ is identical to $A$. Let $Q(x) \equiv \sum_{i=0}^n b_i x^i$, where $a_n=1$. Consider the linear function $f_i(x) \equiv v_2(b_i 2^{xi}) = ix+v_2(b_i)$ for $i\in I=\{ 0,1,2,\dots,n \}$. In particular, $f_0(x) \equiv v_2(b_0)=c$. Note that $f_i$ has gradient $i$ for each $i\in I$. Also, consider the function $g(x) \equiv \text{min}_{i\in I} f_i(x)$. Note that $g$ is piecewise linear and the gradients of each linear component are strictly decreasing among values of $I$. Plotting the graphs $y=f_i(x)$ for each $i\in I$, and $y=g(x)$, $g(x)$ is simply the lower envelope of the lines $f_i$. We call $x$ a vertex if the gradient of $g$ abruptly decreases at point $x$; since each linear component has gradient among values of $S$, so the gradient must decrease by at least $1$ past each vertex, and there can be a maximum of $n$ vertices. Note that $f_i(0) =v_2(a_i)\geq 0$ for all $i\in I$, with equality for $i=n$, so $g(0)=0$. Also, for all large $x$ (in particular, $x>c$), we have $f_i(x) \geq i > c = f_0(x)$ for all $i\in I\setminus\{0\}$, so $g(x)=c$. Therefore, there exists a minimum index $x_0$ such that $g(x_0) = c$. By minimality of $x_0$, we have $g(x_0-1)<g(x_0)$. So some component of $g$ within $[x_0-1,x_0]$ has positive gradient, so $g$ is also strictly increasing on $[0,x_0-1]$ (strictly positive gradients). Therefore, $0=g(0)<g(1)<g(2)<\dots<g(x_0-1)<g(x_0)=c$, and \[\sum_{x=0}^{x_0-1} (g(x+1)-g(x))=c\]It suffices to show that this sum is $\leq \frac{3}{2}n^2$. Consider the values of $x$ that are vertices. Then if $x$ is the $t$-th vertex from the left, then the gradient of $g$ to the right of $x$ is at most $n-t$. And there are at most $n$ vertices, so \[\sum_{x\text{ vertex}}(g(x+1)-g(x)) \leq \sum_{t=1}^n (n-t) = \frac{n(n-1)}{2} < \frac{n^2}{2}.\] Now consider the values of $x$ that are non-vertices. If $x>0$, then each non-vertex implies that $g(x) = \text{min}_{i\in I} v_2(b_i 2^{xi})$ is obtained by a unique value $g(x)=v_2(b_{j_x} 2^{x j_x})$ for $j_x\in I$; and $v_2(b_i 2^{xi}) > g(x)$ for the other indices $i\in I\setminus \{j_x\}$. Now \[P(2^x)=\sum_{i\in I} b_i 2^{xi} \equiv b_{j_x} 2^{x j_x} ]\equiv 2^{g(x)}\pmod{2^{g(x)+1}}\]so $v_2(P(2^x)) = g(x) \in B$. Since the values of $g(x)$ for $x=1,2,\dots,x_0-1$ are unique, positive, and $<c$ (by strict ordering), so each non-vertex corresponds to a unique element of $B$ smaller than $c$. But $B$ has at most $n-1$ elements smaller than $c$. Thus there are at most $n$ non-vertices $x$ (at most $n-1$ positive non-vertices, and $x=0$ might be a non-vertex). We bound $g(x+1)-g(x)\leq n$ for each non-vertex (as maximum gradient is $n$), so \[\sum_{x\text{ non-vertex}}(g(x+1)-g(x)) \leq n\cdot n = n^2.\]Thus $C\leq \frac{3}{2}n^2$, as desired.

Let $M$ be the max possible element of $A$. Shift $P$ such that $\nu_2(P(0))=M$.

The key idea is to consider $P(2^1), P(2^2), \cdots, P(2^M)$ and if $\nu_2(a)<\nu_2(a_1), \nu_2(a_2), \cdots, \nu_2(a_k)$, then $\nu_2(a+a_1+a_2+\cdots+a_k)=\nu_2(a)$. joke

Let $P(x)=\sum\limits_{i=0}^n a_ix^i$. We have $a_n=1$. Consider $g_i(t)=\nu_2(a_i (2^t)^i)=\nu_2(a_i)+ti$. Let $S_i$ be the set of REALS such that $g_i(t)<g_j(t)\forall j\ne i$. Claim: $S_i$ is an open interval. Proof: For all $j<i, g_i(t)<g_j(t)$ if and only if $t>\frac{\nu_2(a_j)-\nu_2(a_i)}{i-j}$. For all $j>i, g_i(t)<g_j(t)$ if and only if $t<\frac{\nu_2(a_j)-\nu_2(a_i)}{i-j}$. Let $\frac{\nu_2(a_j)-\nu_2(a_i)}{i-j}=C_j$, then $S_i=(\max_{j<i} C_j, \min_{j>i} C_j)$. Now, let's go back to the problem. If a positive integer is in one open interval other than $S_0$, then call this integer special. We can easily show if $x$ and $y$ are distinct special integers, then $\nu_2(P(x)) \ne \nu_2(P(y))$ Let $0=m_0<m_1<\cdots<m_{k-1}<m_k=n$ be the indices st $S_{m_i} \cap \mathbb{R}^+$ is nonempty. Suppose $S_{m_k}=[0, y_k), S_{m_{k-1}}=(y_k, y_{k-1}), \cdots, S_0=(y_1,\infty)$ Then we have $\nu_2(a_{m_{i-1}}) = \nu_2(a_{m_i}) + (a_{m_i}-a_{m_{i-1}})y_i$ Therefore, $M=\nu_2(a_0)=\sum\limits_{i=1}^k (y_i-y_{i-1})m_i$ if $y_0=0$ Rewriting, this is $ny_k-\sum\limits_{i=1}^{k-1} y_i(m_{i+1}-m_i)$ We know between $[1,y_k]$ there are at least $y_k-n$ integers that are one of the $y_i$'s, because otherwise we can consider the n $P(2^{m_i})$ along with P(0). At this point, a smoothing argument that forces the $y_i$'s to be integer works. Consider the sum $\sum\limits_{i=1}^{k-1} y_i(m_{i+1}-m_i)$. We want to minimize it to maximize $M$. Since $y_i$ is a decreasing sequence, I can keep the $m_i$'s that are integers, that is, this sum is at least $\sum\limits_{i=1}^l y_i(m_{i+1}-m_i) \ge \sum\limits_{i=1}^l y_i \ge \frac{l(l+1)}{2}$ Now the problem is a simple quadratic.

Deleted post.

FloorX wrote: So is there any typo in the problem statement? Note that $\deg P=|A|=n$ as well, so your counterexample is not quite a counterexample.