# How many different values can that sum take?

Let $x_1,x_2,\dots,x_{100}$ be a permutation of $1,2,\dots,100.$ How many different values does the sum $x_1+2x_2+\cdots+100x_{100}$ take?

• It seems, that if you have sequence $x_1,x_2,...,x_n$ as permutation of $1,2,...,n$, and take sum $x_1+2x_2+...+nx_n$, then you'll obtain $$\dfrac{n(n-1)(n+1)}{6}+1$$ different values of this sum. So, for $n=100$ I expect $166651$ different values. – Oleg567 Jun 18 '14 at 19:22
• @ Oleg567 : Calculations confirm that. How to prove it? – user64494 Jun 18 '14 at 19:27
• Perhaps starting point is that smallest sum is $$1\cdot n + 2 (n-1)+3(n-2)\cdots+n\cdot 1,$$ largest sum is $$1\cdot1+2\cdot2+\cdots+n\cdot n.$$ And that there are no gaps between/among them. – Oleg567 Jun 18 '14 at 19:30
• Why are there no gaps between these values? – user64494 Jun 18 '14 at 19:32
• Hmm, that is the most interesting question. Don't know yet. Maybe to consider some neighboring permutations etc... – Oleg567 Jun 18 '14 at 19:35

## 1 Answer

Let $x_1,x_2,\dots,x_n$ be a permutations of $1,2,\dots,n.$ $(n\ge 4)$.

Then there are

$$\dfrac{n(n-1)(n+1)}{6}+1$$ different values of sums $x_1+2x_2+\cdots+nx_n$.

Smallest value is $$v_n = 1\cdot n + 2(n-1)+3(n-2)+\cdots+n\cdot 1 = \sum_{j=1}^{n}j(n+1-j)=\dfrac{n(n+1)(n+2)}{6},$$ largest value is $$V_n = 1\cdot 1+2\cdot 2+\cdots+n\cdot n = \sum_{j=1}^nj^2= \dfrac{n(n+1)(2n+1)}{6}.$$

Let's prove that there are no "gaps" between $v_n$ and $V_n$.

We'll use math. induction.

0) There are no "gaps" for $n=4$.
Really,
$(4,3,2,1)\rightarrow 20$;
$(4,2,3,1)\rightarrow 21$;
$(3,4,1,2)\rightarrow 22$;
$(3,2,4,1)\rightarrow 23$;
$(4,1,2,3)\rightarrow 24$;
$(3,1,4,2)\rightarrow 25$; ... (other cases - symmetrically).

1) Suppose that there are no "gaps" for some $n=n_0$.

2) Now prove that there are no "gaps" for $n=n_0+1$:

2.a) all sums of vectors $(n_0+1, x_1,x_2,\ldots,x_{n_0})$ have form $$1(n_0+1)+2x_1+3x_2+\cdots+(n_0+1)x_{n_0} \\= n_0+1+(x_1+x_2+\cdots+x_{n_0})+(x_1+2x_2+\cdots+n_0 x_{n_0})$$ and fill values from $$n_0+1+\dfrac{n_0(n_0+1)}{2}+\dfrac{n_0(n_0+1)(n_0+2)}{6} = \dfrac{(n_0+1)(n_0+2)(n_0+3)}{6} = v_{n_0+1}$$ to $$n_0+1+\dfrac{n_0(n_0+1)}{2}+\dfrac{n_0(n_0+1)(2n_0+1)}{6} = \dfrac{2n_0^2+4n_0+6}{6}$$ without "gaps";

2.b) all sums of vectors $(x_1,x_2,\ldots,x_{n_0},n_0+1)$ have form $$x_1+2x_2+\cdots+n_0x_{n_0}+(n_0+1)(n_0+1) \\= (x_1+2x_2+\cdots+n_0 x_{n_0}) + (n_0+1)^2$$ and fill values from $$\dfrac{n_0(n_0+1)(n_0+2)}{6} + (n_0+1)^2 = \dfrac{n_0^2+8n_0+6}{6}$$ to $$V_{n_0}+(n_0+1)^2 = \dfrac{(n_0+1)(n_0+2)(2n_0+3)}{6}=V_{n_0+1}.$$ without "gaps".

2.c) It remains to show that upper bound of 2.a) is not less than lower bound of 2.b). It is so, since $$n_0\ge 4\\ \Downarrow \\ n_0^2 \ge 4n_0 \\ \Downarrow \\ 2n_0^2 \ge n_0^2+4n_0 \\ \Downarrow \\ 2n_0^2 +4n_0+6\ge n_0^2+8n_0+6.$$

And apply it for $n=100$.

• Nice solution Oleg. This is basically a special representation of $A + \ldots + n \cdot A$ where $A$ is all the integers from one to $n$ (of size $n!$). I wonder if there are other choices for the representation that would make this problem more interesting. – George Shakan Jun 19 '14 at 5:00