There are $m$ clauses containing a conjunction of 3 variables out of $n$ Boolean variables. (they are of the form $x_i$ $\wedge$ $x_j$ $\wedge$ $x_k$, where each $x_{i,j,k}$ is a variable or it's negation. For these $n$ variables, show that there is an assignment for $x_1,x_2,\cdots,x_n$ that satisfies at least $c*m$ clauses, for some constant $c > 0$. Indicate the value of $c$.
I am confused how to approach with this problem. A clause will be satisfied if all the variables are set to 1. This event happens with probability $\frac{1}{8}$, if we define a random variable $X_i$ which takes a value $1$ when clause $i$ is satisfied and $0$ otherwise. We can show in expectation for a random variable $X = X_1 + X_2 + \cdots + X_m$, but I am unsure that the value of $c$ we are looking for will be $\frac{1}{8}$
what am I missing? Any help is appreciated.
Thanks.
HINT
First, you shouldn't think about this in terms of probability: you need to find a $c$ so that you are certain to have that fraction of clauses satisfiable.
Second, we can easily find an upper bound to $c$ as follows. Imagine you have exactly $8$ clauses, representing all possible combinations of taking exactly $3$ variables and setting them to true of false. It is clear that in that case you can set at most one of the clauses to be true. So, we know for a fact that the upper bound of $c$ is $\frac{1}{8}$: there are cases where you can at most set $\frac{1}{8}$ of the clauses to true.
OK, but is that really the worst case scenario, i.e. Can we always make at least $\frac{1}{8}$ of the clauses true? And how do we prove that? I'll leave you to think about that some more. But again, you should not do this in terms of probability.