Priceless or Point-full(7)

Algebra Level 5

For a sequence $x_1, x_2, . . . , x_n$ of real numbers, we define its price as

$\large\ \max _{ 1\le i\le n }{ \left| { x }_{ 1 } + { x }_{ 2 } + ... + { x }_{ i } \right| }$ .

Given $n$ real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price $D$ . Greedy George, on the other hand, chooses $x_1$ such that $\left| { x }_{ 1 } \right|$ is as small as possible; among the remaining numbers, he chooses $x_2$ such that $\left| { x }_{ 1 }+{ x }_{ 2 } \right|$ is as small as possible, and so on. Thus, in the $i^{th}$ step he chooses $x_i$ among the remaining numbers so as to minimise the value of $\left| { x }_{ 1 } + { x }_{ 2 } + ... + { x }_{ i } \right|$ . In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price $G$ .

Find the least possible constant $c$ such that for every positive integer $n$ , for every collection of $n$ real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality $G \le cD$ .

The answer is 2.

1 solution

Pedro Cardoso
Feb 27, 2018

I just had an educated guess that the answer would be $2$ : consider the set of $n$ numbers $\{2^1,2^2,,...,2^{n-2},2^{n-1},-2^n\}$ where only the largest power of $2$ is negative.

Since $\sum _{ i=1 }^{ n-1 }{ 2^{ i } } =2^{ n }-1$ , George would put them into the sequence $2^1,2^2,,...,2^{n-2},2^{n-1},-2^n$ and it's price would be $2^n-1$ . But Dave would put them into the sequence $2^{n-1},-2^n,2^1,2^2,,...,2^{n-2}$ and it's price would be $2^{n-1}$ .

This means $\large c=\frac{G}{D}=\frac{2^n-1}{2^{n-1}}$ , which decreases with $n$ and goes to $2$ as $n$ aproaches infinity.

I've got no formal proof of why $2$ is the minimum, so it would be nice if someone posted one.

@Pedro Cardoso , true.

Since this is an IMO problem 5 , you would get at most 2 points for this solution.

I will wait for a day or two , to see if someone post a solution, else I will post it with full proof.

Priyanshu Mishra - 3 years, 3 months ago

It's not hard to attain the max: for any integer $k,$ suppose we've got $k$ $-1$ s, $k$ $1$ s, and then $-2k$ and $2k.$ Then $D=k$ : take the $-1$ s all first, then $2k,$ then $-2k,$ then all the $1$ s. But $G = 2k$ because George will alternate taking the $\pm 1$ values until the end.

Patrick Corn - 3 years, 2 months ago

Priceless or Point-full(7)

The answer is 2.

1 solution

0 pending reports