3
$\begingroup$

Let $x_1, x_2,...,x_{2008}$ are numbers such that $|x_1|=999$ and for all $n=2,...,2008$
$$|x_n|=|x_{n-1}+1|$$ Find the smallest possible value of the sum
$$x_1+x_2+...+x_{2008}$$

My work:

Let $S=x_1+x_2+...+x_{2008}$.

If $x_1=-999, x_2=-998, ..., -1,0,-1,0$ then I think the answer $-500004$.

But I don't know how to prove that:

$\endgroup$
  • $\begingroup$ Finding the smallest possible value of $|x_1+x_2+\cdots+x_{2008}|$ is also an interesting problem. (In fact, it's how I interpreted the problem on first reading.) $\endgroup$ – TonyK Jan 16 '19 at 12:58
  • $\begingroup$ The minimization problem can be understood as a multi-staging process in which the transition to a new staging, from $\sum_{k=1}^N x_k$ to $\sum_{k=1}^{N+1} x_k$ is constrained by the condition $ |x_{k+1}| = |x_k+1|$ so the procedure to solve it can be successfully handled with a Dynamic Programming algorithm. $\endgroup$ – Cesareo Jan 17 '19 at 11:04
  • $\begingroup$ On a side note, @Roman, let me ask you this: aren't you going to create an OEIS entry for the sequence from math.stackexchange.com/questions/2469058/…? IMHO, it more than deserves one. $\endgroup$ – Ivan Neretin Jan 17 '19 at 22:46
  • $\begingroup$ @IvanNeretin: No! I do not know how do it. But if you want you will can do it. $\endgroup$ – Roman83 Jan 18 '19 at 8:08
  • $\begingroup$ @Roman So I will. May I know your full name, at least? I don't want to claim it in my name, as the idea is yours. $\endgroup$ – Ivan Neretin Jan 18 '19 at 8:39
2
$\begingroup$

Hint.

Calling

$$ S_1(x_1) = \{-m,m\} $$

and

$$ S_k(x_k) = \min_{x_k}\left(S_{k-1}(x_{k-1})+x_k\right)\ \ \mbox{s. t. }\ \ |x_k|=|x_{k-1}+1| $$

we have after $N$ steps the sought min as $\min S_N(x_N)$

$\endgroup$

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.