8
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Oleg567 Jun 18 '14 at 19:22
  • $\begingroup$ @ Oleg567 : Calculations confirm that. How to prove it? $\endgroup$ – user64494 Jun 18 '14 at 19:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Oleg567 Jun 18 '14 at 19:30
  • 2
    $\begingroup$ Why are there no gaps between these values? $\endgroup$ – user64494 Jun 18 '14 at 19:32
  • $\begingroup$ Hmm, that is the most interesting question. Don't know yet. Maybe to consider some neighboring permutations etc... $\endgroup$ – Oleg567 Jun 18 '14 at 19:35
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – George Shakan Jun 19 '14 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.