Câu hỏi 26
Với một dãy số thực $x_1,x_2,\ldots,x_n$, định nghĩa giá của dãy là
$$\max_{1\le i\le n}|x_1+\cdots+x_i|.$$
Cho $n$ số thực, Dave và George muốn sắp chúng thành dãy có giá thấp. Dave chăm chỉ thử mọi cách và tìm được giá nhỏ nhất có thể $D$. Ngược lại, George tham lam chọn $x_1$ sao cho $|x_1|$ nhỏ nhất; trong các số còn lại, chọn $x_2$ sao cho $|x_1+x_2|$ nhỏ nhất, và cứ thế. Tức ở bước thứ $i$, George chọn $x_i$ trong các số còn lại để $|x_1+x_2+\cdots+x_i|$ nhỏ nhất. Nếu nhiều số cho cùng giá trị, George chọn ngẫu nhiên một số. Cuối cùng George được dãy có giá $G$.
Tìm hằng số nhỏ nhất $c$ sao cho với mọi số nguyên dương $n$, mọi bộ $n$ số thực và mọi dãy George có thể thu được, luôn có $G\le cD$.
$$\max_{1\le i\le n}|x_1+\cdots+x_i|.$$
Cho $n$ số thực, Dave và George muốn sắp chúng thành dãy có giá thấp. Dave chăm chỉ thử mọi cách và tìm được giá nhỏ nhất có thể $D$. Ngược lại, George tham lam chọn $x_1$ sao cho $|x_1|$ nhỏ nhất; trong các số còn lại, chọn $x_2$ sao cho $|x_1+x_2|$ nhỏ nhất, và cứ thế. Tức ở bước thứ $i$, George chọn $x_i$ trong các số còn lại để $|x_1+x_2+\cdots+x_i|$ nhỏ nhất. Nếu nhiều số cho cùng giá trị, George chọn ngẫu nhiên một số. Cuối cùng George được dãy có giá $G$.
Tìm hằng số nhỏ nhất $c$ sao cho với mọi số nguyên dương $n$, mọi bộ $n$ số thực và mọi dãy George có thể thu được, luôn có $G\le cD$.