edited by
17,705 views
67 votes
67 votes

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

  1. $max(Y, a_0+Y)$
  2. $max(Y, a_0+Y/2)$
  3. $max(Y, a_0 +2Y)$
  4. $a_0+Y/2$
edited by

2 Answers

Best answer
114 votes
114 votes

$$\begin{align}
&S = \langle a_0, S_1 \rangle\\
&S_1 = \langle a_1, a_2, a_3 \ldots a_{n-1} \rangle
\end{align}$$

Two possible cases arise:

  1. $\bf{a_0}$ is included in the max weight subsequence of $\textbf{S:}$

            In this case, $X = \text{weight} \Bigl( \langle a_0, S_1 \rangle \Bigr) = a_0 + \dfrac Y 2$
     
  2. $\bf{a_0}$ is not included in the max weight subsequence of $\textbf{S:}$

            In this case, $X = \text{weight}(S_1) = Y$

Since the value of $a_0$ can be anything (negative or $<\frac Y 2$ in general) $\{ \because a_i \in \mathbb{R} \}$, it is possible that $Y > a_0 + \frac Y 2$.

The maximum possible weight of a subsequence of $S$ is given by: $$X = \max \left ( Y, a_0 + \frac Y 2 \right )$$

Thus, option B is correct.

edited by
10 votes
10 votes

The weight of a sequence $a_{0},a_{1} , ............. , a_{n-1}$ of real numbers is defined as $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$.

$X$ denote the maximum possible weight of a subsequence of  $a_{0},a_{1} , ............. , a_{n-1}$ and

$Y$ the maximum possible weight of a subsequence of $a_{1} , ............. , a_{n-1}$

As the weight of the sequence  $a_{0},a_{1} , ............. , a_{n-1}$ of real numbers is defined as $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$. 

so similarly for  the subsequence   $a_{1} , ............. , a_{n-1}$  the weight can be defined as ($a_{1}+\frac{a_{2}}{2}+.......... + \frac{a_{n-1}}{2^{n-2}}$)… 

CASE 1: Now suppose the maximum possible weight of the subsequence  is $Y$ only then it will be also maximum weight for the subsequence $a_{0},a_{1} , ............. , a_{n-1}$.

                          i.e     $X=weight(Y)$

CASE 2: if the weight $Y$ is not the maximum then we have to also include $a_{0}$ in it. and as it is given in the question that the maximum weight of the sequence $a_{0},a_{1} , ............. , a_{n-1}$ is  $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$.  .

but we have the weight $Y$ as   ($a_{1}+\frac{a_{2}}{2}+.......... + \frac{a_{n-1}}{2^{n-2}}$)…  so before adding $a_{0}$ to it we have to divide this weight by $2$ . so after dividing by $2$ we will get ( $\frac{a_{1}}{2}+ .......... + \frac{a_{n-1}}{2^{n-1}}$).

now after including $a_{0}$ we will get the maximum weight of subsequence $X$ = $a_{0}+\frac{a_{1}}{2} + ..............+ \frac{a_{n-1}}{2^{n-1}}$. where $\frac{a_{1}}{2}+ .......... + \frac{a_{n-1}}{2^{n-1}}$  = $Y$

                           i.e   $X = a_{0} +\frac{Y}{2}$ 

which is the maximum weight in this case.

so from both CASE 1 and CASE 2 we can conclude that  $X$ will be

                                                            $X  = max( Y, a_{0} + \frac{Y}{2})$

ANS is $option$ $B$ !!

edited by
Answer:

Related questions

37 votes
37 votes
5 answers
1
43 votes
43 votes
8 answers
2
26 votes
26 votes
4 answers
3