The polynomial $1976(x+x^2+ \cdots +x^n)$ is decomposed into a sum of polynomials of the form $a_1x + a_2x^2 + \cdots + a_nx^n$, where $a_1, a_2, \ldots , a_n$ are distinct positive integers not greater than $n$. Find all values of $n$ for which such a decomposition is possible.
Problem
Source:
Tags: algebra, polynomial, Additive combinatorics, counting, combinatorics, IMO Shortlist
21.09.2010 01:03
Let $1976(x+x^2+ \ldots + x^n)$ be decomposed into the sum of the $t$ polynomials $P_i$, i.e. $1976(x+x^2+ \ldots + x^n)=\sum_{i=1} ^t P_i(x)$, where $P_k(x)=\sum_{i=1}^n a_{k,i}x^i$. Suppose fixed $k\in \{1,2,3 \ldots t\}$, and consider $P_k$. Now since $a_{k,i}$ are $n$ distinct positive integers, the set $\{a_{k,1},a_{k,2} \ldots a_{k,n} \}$ is a permutation of the set $\{1,2 \ldots n \}$. Hence $a_{k,1}+a_{k,2} \ldots +a_{k,n}=\frac{n(n+1)}{2}$. Since this is for arbitrary $k$, $\sum_{j=1}^t\sum_{i=1}^{n}a_{j,i}=\sum_{i=1}^{t}P_i(1)=\frac{tn(n+1)}{2}\implies 1976n=\frac{tn(n+1)}{2}$. Hence $2\cdot 1976=t(n+1)$ so $n+1|2 \cdot 1976=2^4\cdot 13 \cdot 19$. Case 1 $v_2(n+1)\le 3$ Set $a_{r,i}=i$ for odd $r$ and set $a_{r,i}=n-i+1$ for even $r$. Then $P_{2m-1}+P_{2m}\\ \\ =\sum_{i=1}^n a_{2m-1,i} x^i+\sum_{i=1}^n a_{2m,i} x^i\\ \\ =(x+2x^2+3x^3 \ldots + nx^n)+(nx+(n-1)x^2+(n-2)x^2\ldots + x^n)\\ \\ =(n+1)(x+x^2+x^3 \ldots + x^n)$. So $1976(x+x^2+ \ldots + x^n)=\sum_{i=1}^t P_i = \frac{t(n+1)}{2}(x+x^2+x^3 \ldots + x^n)$. Therefore $t=\frac{2\cdot 1976}{n+1}$ clearly satisfies the problem ($t$ is even since $v_2(n+1)\le 3$). Case 2 $v_2(n+1)=4$ So $t\in \{1,13,19,247\}$. Trivially $t=1$ is discarded since this is not a decomposition. The cases $t=13,19,247$ may have individual solutions, of which I have not found and I'm kind of in a rush :S So far, all solutions for $n$ are such that $n+1|1976$ and $v_2(n+1)\ge 3$ and $n>0$.
14.12.2016 12:15
Any solution? There is still a big problem remain unsolved.