The weight of a sequence \(a_0,a_1, \dots, a_{n-1}\) of real numbers is…
2010
The weight of a sequence \(a_0,a_1, \dots, a_{n-1}\) of real numbers is defined as \(a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}\). A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let \(X\) denote the maximum possible weight of a subsequence of \(a_o,a_1, \dots, a_{n-1}\) and \(Y\) the maximum possible weight of a subsequence of \(a_1,a_2, \dots, a_{n-1}\). Then \(X\) is equal to
- A.
\(max(Y, a_0+Y)\) - B.
\(max(Y, a_0+Y/2)\) - C.
\(max(Y, a_0 +2Y)\) - D.
\(a_0+Y/2\)
Attempted by 97 students.
Show answer & explanation
Correct answer: B
Key insight: when you include a_0 in the subsequence, every chosen element from a_1,a_2,... has its weight halved because indices in the subsequence shift by one.
If you do not take a_0, the best subsequence is from a_1,a_2,... and has weight Y.
If you do take a_0, then the best contribution from the remaining elements equals half of the best subsequence weight from a_1,a_2,..., i.e. Y/2, so the total is a_0 + Y/2.
Hence the maximum possible weight X is the larger of these two possibilities: X = max(Y, a_0 + Y/2).