Câu hỏi 143
Với một dãy số thực $x_1, x_2, \dots, x_n$, ta định nghĩa giá của nó là
$$
\max_{1 \le i \le n} |x_1 + \dots + x_i|.
$$
Cho $n$ số thực, Dave và George muốn sắp xếp chúng thành một dãy có giá thấp. Dave cần mẫn kiểm tra mọi cách sắp xếp và tìm được giá nhỏ nhất có thể là $D$. Còn George tham lam thì chọn $x_1$ sao cho $|x_1|$ nhỏ nhất có thể; trong các số còn lại, anh ta chọn $x_2$ sao cho $|x_1 + x_2|$ nhỏ nhất có thể, và cứ thế tiếp tục. Như vậy, ở bước thứ $i$ anh ta chọn $x_i$ trong các số còn lại sao cho giá trị $|x_1 + \dots + x_i|$ là nhỏ nhất. Ở mỗi bước, nếu có nhiều số cho cùng một giá trị thì George chọn ngẫu nhiên một số. Cuối cùng anh ta được một dãy có giá $G$.
Hãy tìm hằng số $c$ nhỏ nhất có thể sao cho với mọi số nguyên dương $n$, mọi bộ gồm $n$ số thực, và mọi dãy mà George có thể nhận được, các giá trị thu được thỏa mãn bất đẳng thức $G \le cD$.
$$
\max_{1 \le i \le n} |x_1 + \dots + x_i|.
$$
Cho $n$ số thực, Dave và George muốn sắp xếp chúng thành một dãy có giá thấp. Dave cần mẫn kiểm tra mọi cách sắp xếp và tìm được giá nhỏ nhất có thể là $D$. Còn George tham lam thì chọn $x_1$ sao cho $|x_1|$ nhỏ nhất có thể; trong các số còn lại, anh ta chọn $x_2$ sao cho $|x_1 + x_2|$ nhỏ nhất có thể, và cứ thế tiếp tục. Như vậy, ở bước thứ $i$ anh ta chọn $x_i$ trong các số còn lại sao cho giá trị $|x_1 + \dots + x_i|$ là nhỏ nhất. Ở mỗi bước, nếu có nhiều số cho cùng một giá trị thì George chọn ngẫu nhiên một số. Cuối cùng anh ta được một dãy có giá $G$.
Hãy tìm hằng số $c$ nhỏ nhất có thể sao cho với mọi số nguyên dương $n$, mọi bộ gồm $n$ số thực, và mọi dãy mà George có thể nhận được, các giá trị thu được thỏa mãn bất đẳng thức $G \le cD$.