Math Olympiad Second Stage Training Camp, 2015

Answer: $c = 2$

Solution: If initially we have $1, -1, 2, -2$, then Dave will arrange them as $1, -2, 2, -1$, and George will arrange them as $1, -1, 2, -2$, so $D = 1, G = 2$, hence $c \ge 2$.

Next we prove that $G \le 2D$. Let the initial numbers be $x_1, x_2, \dots, x_n$, and suppose Dave and George arrange them respectively as $d_1, d_2, \dots, d_n$ and $g_1, g_2, \dots, g_n$. Let
$$M = \max_{1 \le i \le n} |x_i|, \quad S = |x_1 + \dots + x_n|, \quad N = \max\{M, S\}.$$
Then the following hold
$$D \geq S, \tag{1}$$
$$D \geq \frac{M}{2}, \text{ and} \tag{2}$$
$$G \leq N = \max\{M, S\} \tag{3}$$
From these three inequalities we obtain
$$G \leq \max\{M, S\} \leq \max\{M, 2S\} \leq 2D$$

Inequality (1) is a direct consequence of the definition of price.

To prove (2), consider an index $i$ such that $|d_i| = M$, then we have
$$\begin{aligned} M &= |d_i| = |(d_1 + \cdots + d_i) - (d_1 + \cdots + d_{i-1})| \\ &\leq |d_1 + \cdots + d_i| + |d_1 + \cdots + d_{i-1}| \leq 2D, \end{aligned}$$

It remains to prove (3). Let $h_i = g_1 + \cdots + g_i$; we will prove by mathematical induction on $i$ that $|h_i| \leq N$.

When $i=1$, $|h_1| = |g_1| \leq M \leq N$. Note also that $|h_n| = S \leq N$.

Suppose $|h_{i-1}| \leq N$. We consider two cases:

Case (1). Suppose that among $g_i, \cdots, g_n$ no two numbers have opposite signs.
Without loss of generality assume they are all non-negative, then we have $h_{i-1} \leq h_i \leq \cdots \leq h_n$, and therefore
$$|h_i| \leq \max\{|h_{i-1}|, |h_n|\} \leq N.$$

Case (2). Among $g_i, \cdots, g_n$ there are both positive and negative numbers, so there exists $j \geq i$ such that $h_{i-1}g_j \leq 0$. Then by the definition of George's sequence we obtain
$$|h_i| = |h_{i-1} + g_i| \leq |h_{i-1} + g_j| \leq \max\{|h_{i-1}|, |g_j|\} \leq N.$$

This completes the proof by mathematical induction.