Recently, I came across the following problem:
It is known that $k$ and $n$ are positive integers, and that $k+1 \le \sqrt{\frac{n+1}{\ln(n+1)}}.$ Prove that we can find a polynomial $P$ of degree $n$, whose coefficients belong to $\{-1,0,1\},$ such that $(x-1)^k$ divides $P$
(Some background: This was proposed to me by a colleague, who stated it was from an Ukrainian IMO team selection test. I have taken a look around, but never succeeded in the task of finding an actual solution. Also, the colleague who proposed it to me did not know himself how to solve it either.)
At first, I thought a simple construction would suffice: namely, one relatively 'naive' idea is to consider products of the form
$$ (x^{\alpha_1} - 1)(x^{\alpha_2} -1) \cdots (x^{\alpha_k} -1),$$
where $\alpha_1 + \alpha_2 + \cdots + \alpha_k = n.$ Indeed, this works and yields a non-trivial result through an algorithmic method, but only when $k \lesssim \ln(n).$ One can improve $\ln(n)$ slightly in the construction - which is not at all sophisticated -, but not so that one can reach the $n^{1/2}/\ln(n)^{1/2}$ type of upper bound, which is asked.
Therefore, I guess the 'hint' here is that we should not be looking for a 'constructive' proof, but rather for an 'existence' one. Therefore, with that in mind, we write our desired polynomial as
$$P(x) = \sum_{a \in A} x^a - \sum_{b \in B} x^b.$$
Then, $(x-1)^k$ dividing $P$ means that $P(1) = P'(1) = \cdots = P^{(k-1)}(1) = 0.$ But this implies, after some manipulations, that
$$ \sum_{a \in A} 1 = \sum_{b \in B} 1, $$ $$ \sum_{a \in A} a = \sum_{b \in B} b, $$ $$ \sum_{a \in A} a^2 = \sum_{b \in B} b^2,$$ $$ \vdots $$ $$ \sum_{a \in A} a^{k-1} = \sum_{b \in B} b^{k-1}.$$
Let then $s_k(A) = \sum_{a \in A} a^k,$ where $A \subset \{0,1,...,n\}.$ The problem can therefore be restated as follows:
There are two subsets $A,B \subset \{0,1,...,n\}$ such that $|A| = |B|$ and $s_j(A) = s_j(B), \,j=1,...,k-1.$
Notice that $A$ and $B$ need not necessarily be disjoint, as any possible overlap is 'cancelled' in the definition of $P.$
In order to solve this problem, I have been trying to use continuity arguments, like 'keep the sum unchanged by changing two elements, and the difference between the squares decreases' or something of this kind. This might indeed be helpful, but I cannot see how to take it on further than that, that is, how to use this construction for $k > 2.$
Actually we can prove this by the pigeon-hole principle and some (rather loose) estimation.
As written in your post, $(x-1)^k \ | \ P(x)$ if and only if $P(1) = P'(1) = \cdots = P^{(k-1)}(1) = 0$. Therefore, the original problem holds true if we can guarantee that, denoting $\mathcal S = \{P = \sum_{i=0}^n a_ix^i \ | \ a_{i} \text{ is 0 or 1}\}$, there exists $P_1$ and $P_2$ in $\mathcal S$ such that $P^{(i)}_1(1) = P^{(i)}_2(1)$ for $i = 0, 1, \cdots, k-1$.
How many elements are there in $\mathcal S$? Clearly, there are $2^{n+1}$ of them.
How many possible values can those $P^{(i)}(1)$ take? Well, that is a bit more subtle. Let us look at different $i$'s. In particular, since $P$ has integral coefficient, denote by $P_0(x) = x^n + x^{n-1} + \cdots + x + 1 \in \mathcal S$ the "greediest polynomial", then $P^{(i)}(1)$ has to take integral value in the region $[0, P_0^{(i)}(1)]$.
So, we need to compute $P^{(1)}_0(1)$. It is not hard to show (by induction or some combinatoric equality) that
$$ \begin{aligned} P^{(0)}_0(1) &= 1 + 1 + \cdots + 1 = n+1;\\ P^{(1)}_0(1) &= n + (n-1) + \cdots + 1 = \frac{(n+1)n}{2};\\ P^{(2)}_0(1) &= n(n-1) + (n-1)(n-2) + \cdots + 2\cdot 1 = \frac{(n+1)n(n-1)}{3};\\ &\vdots\\ P^{(k-1)}_0(1) &= \frac{(n+1)n\cdots(n-k+2)}{k}. \end{aligned} $$
So there are at most $$ \left((n+1)+1\right)\left(\frac{(n+1)n}{2}+1\right)\cdots\left(\frac{(n+1)n\cdots(n-k+2)}{k} + 1\right) $$ possibilities in the combination of the derivatives.
So, in order to use the pigeon-hole, it suffices to prove that $$ \left((n+1)+1\right)\left(\frac{(n+1)n}{2}+1\right)\cdots\left(\frac{(n+1)n\cdots(n-k+2)}{k} + 1\right) < 2^{n+1}. $$
Somehow I am too lazy and sloppy to prove this, but I hope you believe that "trading the $+1$'s in the products with the denominator" is fair enough, that is:
$$ \left((n+1)+1\right)\left(\frac{(n+1)n}{2}+1\right)\cdots\left(\frac{(n+1)n\cdots(n-k+2)}{k} + 1\right) \leq\\ \left(n+1\right)\Big((n+1)n\Big)\cdots\Big((n+1)n\cdots(n-k+2)\Big) = (n+1)^kn^{k-1}\cdots(n-k+2). $$
Therefore, it suffices to prove that $$ (n+1)^kn^{k-1}\cdots(n-k+2) < 2^{n+1}. $$
Taking natural logarithm, it suffices to prove that $$ \ln\Big((n+1)^kn^{k-1}\cdots(n-k+2)\Big) \leq (n+1)\ln 2. $$
This is true, since $$ \begin{aligned} \ln\Big((n+1)^kn^{k-1}\cdots(n-k+2)\Big) &\leq \ln\Big((n+1)^k(n+1)^{k-1}\cdots(n+1)\Big)\\ &= \ln (n+1)^{\frac{(k+1)k}{2}} = \frac{(k+1)k}{2}\ln(n+1)\\ &< \frac{(k+1)^2}{2}\ln(n+1) \leq \frac{\ln(n+1)}{2}\frac{n+1}{\ln(n+1)}\\ &= \frac{n+1}{2} < 0.69(n+1) < (n+1)\ln2. \end{aligned} $$