4

let sequence $a_{n}$ such $a_{1}=0$,and such $$|a_{n+1}|=|a_{n}+1|,\forall n\in N^{+}$$ find the minimum of the value ( )

$$f=|a_{1}+a_{2}+\cdots+a_{11}|$$ $A:3$ $~~~~~~~~$ $B:2$ $~~~~~~~~$ $C: 1 $ $~~~~~~~~$ $D:0$

I try: since $|a_{2}|=|a_{1}+1|=1$,so $a_{2}=1or -1$ if $a_{2}=1$,then $$|a_{3}|=|a_{2}+1|=2$$,so $a_{3}=2$or $-2$,$\cdots,\cdots $

Following I fell ugly,can you help me How to deal this problem? Thanks

if $a_{2}=-1$,then $a_{3}=0$

math110
  • 93,304

2 Answers2

1

It's 1, according to my short Python 3 script which did a random search, not a brute force search. However, after 1 million runs in a few seconds, it found 1 as the minimum.

minimum_value = 10000

for i in range(1000000):

  moves = np.random.choice([0, 1], 11)
  value = 0

  for move in moves:
    if value == 0:
      value = -1 * value - 1
    else:
      value += 1

  absolute_value = np.abs(value)
  if absolute_value < minimum_value:
    minimum_value = absolute_value
    print (minimum_value)

>> 1
Ryan Rudes
  • 345
1

The key to this problem is to notice what choices don't actually change the sum and can therefore be normalized away.

  1. Whenever a number is negative, the next number decreases in magnitude, so the only way to increase magnitudes is by adding positive numbers.
  2. Indeed, $0$ and $-2$ create the same choices next round: $\pm1$, and so does $1$ and $-3$ ($\pm2$).
  3. The way to keep a magnitude stable is to alternate between a positive and a negative number: $+n,-(n+1),+n,-(n+1),\dotsc$. This pairs off, with each pair contributing a net $-1$ to the total.
  4. Now notice that if we change the sequence to $+n,+(n+1),-(n-2),-(n-1),\dotsc$ the sum did not change. You can still pair off, just further away.

From all of the above, the normalization is as follows:

  1. Whenever a negative number immediately follows a positive number, pair them up, and they must contribute $-1$ to the sum.
  2. Whenever multiple consecutive negative numbers are chosen, pair them up with the nearest preceding positive number which exists by (1), and must also contribute $-1$ to the sum.

As an illustration, take the sequence $$0,+1,+2,+3,-4,-3,-2,+1,-2,+1,+2\text{.}$$ We pair them up into: $$0^*,+1_a,+2_b,+3_c,-4_c,-3_b,-2_a,+1_d,-2_d,+1^*,+2^*$$ and notice this is equivalent to $$0_a,-1_a,0_b,-1_b,0_c,-1_c,0_d,-1_d,0^*,+1^*,+2^*$$ so the sum is simply $-4$ for the four pairs and $+3$ for the sum $\sum_{i=0}^2i$.

This leaves us with exactly one dimension of choice: how long of an increasing sequence of nonnegative integers to add. By parity, this has to be an odd length.

  1. Length $1$: that's a sequence of $0,-1,0,-1,\ldots$, with five pairs and a $0$ at the end for $-5$
  2. Length $3$: four pairs against $\sum_{i=0}^2i$ for $-1$
  3. Length $5$: three pairs against $\sum_{i=0}^4i$ for $+7$
  4. Obviously length $7,9,11$ are worse.

Thus the answer is $1$.

obscurans
  • 3,422