Assume that for a formula $F$ over $n$ variables, there are exactly $k$ allocations that satisfy it. How many random samples from the set $\{0,1\}^n$ are necessary to find an allocation satisfying the formula with a probability of at least 1/2?
Never liked this kind of questions and (un?)fortunately didn't have to answer one such in years. Let's try ...
Prob[rand. sample satisfies F] = $k\cdot 2^{-n}$
$\Rightarrow$ Prob[rand. sample does NOT satisfy F] = $1-k\cdot 2^{-n}=\frac{2^n-k}{2^n}$
Let $x$ be the amount of repetitions.
Prob[find satisfying allocation in $x$ repetitions] = $1-(\frac{2^n-k}{2^n})^x$
so
$1-(\frac{2^n-k}{2^n})^x \geq 1/2$
$\Rightarrow 1/2 \geq (\frac{2^n-k}{2^n})^x$
$\Rightarrow log_{(\frac{2^n-k}{2^n})}(1/2)\geq x$
$\Rightarrow \frac{log_2(1/2)}{log_2(\frac{2^n-k}{2^n})} \geq x$
$\Rightarrow \frac{-1}{log_2(2^n-k) - n} \geq x$
$\Rightarrow$ ???
Right, now what?
Would appreciate the help.
Since $k$ of the $2^n$ elements will work, you are considering a Bernoulli experiment where the probability $p = k/2^n$. Now, if every draw has probability $p$ of providing a correct result, the probability of having a correct result after $N$ trials is $$1- (1-\frac{k}{2^n})^N.$$ Therefore, you have to solve $$1- (1-\frac{k}{2^n})^N \ge \frac{1}{2} $$ for $N$, i.e. $$ 1/2 \ge (1-\frac{k}{2^n})^N $$ $$ \Leftrightarrow 1/2 \ge e^{\ln(1-\frac{k}{2^n}) N}$$ $$\Leftrightarrow \ln 1/2 \ge \underbrace{\ln(1-\frac{k}{2^n})}_{<0} N$$ $$ \Leftrightarrow N \ge \ln(1/2) / \ln(1-\frac{k}{2^n}).$$ The right-hand side can be computed and there you have the solution. I think what you basically got wrong is the sign of the logarithm which I highlighted.