Prove that $\exists$ a Boolean Assignment that satisfies at least $\Sigma_{3\leq i \leq 15}$ $ m_{i} \dfrac{2^{i}-1}{2^{i}}$ clauses Suppose that we have a boolean formula which is conjunction of $\Sigma_{3\leq i \leq 15}$ $ m_{i} $ clauses. 
The clauses consists of $m_{3}$ disjunction of length 3, $ m_{4}$ disjunction of length 4, ..., $m_{15}$ disjunctions of length 15.


*

*Prove that there exists an assignment which satisfies at least $\Sigma_{3\leq i \leq 15}$ $ m_{i} \dfrac{2^{i}-1}{2^{i}}$ clauses.

*Sketch a polynomial time algorithm to produce such assignment. 

I don't understand how to approach this problem. I have written the clauses, but I still don't see it. Any help?
 A: For a disjunction of $i$ variables and/or negations of variables, a random choice of truth values for the variables has probability $\displaystyle \frac{1}{2^i}$ of failing to satisfy the clause, so a probability of $\displaystyle \frac{2^i-1}{2^i}$ of satisfying it.  By linearity of expectation, the expected value of the total number of clauses satisfied is $\displaystyle \sum_i m_i \frac{2^i-1}{2^i}$, and so (as mentioned in the comments) this is the average number of clauses satisfied when averaging over all possible assignments of the variables.  Since at least one such assignment has to do at least as well as the average, this proves that an assignment satisfying $S := \displaystyle \sum_i m_i \frac{2^i-1}{2^i}$ clauses exists.  (Note that there's nothing special about the bounds $3$ or $15$ here.)
Now let's find an algorithm using this idea.
We know from above that the average number of clauses satisfied over all assignments of the variables is $S$. Choose one of the variables $v$.  Consider $A_T$, the average number of clauses satisfied when $v$ is true, and $A_F$, the average number of clauses satisfied when $v$ is false.  We know that $S = \frac{1}{2}(A_T + A_F)$, so at least one of $A_T$ and $A_F$ is at least $S$.  We can find which one by substituting in both True and False for $v$, reducing the clauses (remove "False"s from the disjunctions and observe that disjunctions containing "True" must be always true) and applying the above computation to the reduced problem.
Now, choose the value of $v$ to be whatever yields an average number of clauses satisfied to be greater than $S$.  Repeat for each variable in turn; one can show by induction that the final selection for all variables must satisfy at least $S$ clauses.  The algorithm runs in $O(n^2)$ time where $n$ is the length of the input.
