SELECTION TESTS OF THE BELARUSIAN TEAM TO THE IMO

If the polynomial $P(x)=x^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$ is expandable, then it can be represented as $$P(x)=(x^m+b_{m-1}{x}^{m-1}+\cdots +b_{1}x+b_0)\cdot (x^k+c_{k-1}{x}^{k-1}+\cdots +c_{1}x+c_0),$$ where $m\ge k\ge 1$, $m+k=n$ and numbers $b_i,c_i$ are all non-negative integers. Since the coefficients of the polynomial $P(x)$ are not greater than $100$, all these numbers do not exceed $100$ and, moreover, $b_i\cdot c_i\le 100$ for any $i$ from $0$ to $k-1$. This means that for a fixed $i$ from $0$ to $k-1$ the number of possible pairs $(b_i,c_i)$ does not exceed $$2\cdot 11\cdot 101<\frac{101^2}{4},$$ because at least one of $b_i$ and $c_i$ is not greater than $\sqrt{100}=10$. Thus, the numbers $b_{m-1},b_{m-2},\dots ,b_k$ can be chosen in no more than $101^{m-k}$ ways, and the numbers $b_0,c_0,b_1,c_1,\dots ,b_{k-1},c_{k-1}$ you can select no more than ${\left(\frac{101^2}{4}\right)}^k$ ways. We find that the number of expandable polynomials can be estimated from above by the expression $$\sum _{k=1}^{[n/2]}101^{m-k}{\left(\frac{101^2}{4}\right)}^k=101^n\sum _{k=1}^{[n/2]}\frac{1}{4^k}<101^n\frac{1/4}{1-1/4}=\frac{1}{3}\cdot 101^n$$

Since the number of polynomials $P(x)=x^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$ with non-negative integer coefficients not exceeding $100$ is equal to $101^n$, then there are more than $\frac{2}{3}\cdot 101^n$ non-expandable polynomials, that is, at least twice as many as expandable ones.