$A$ is an random algorithm that decide membership to language $L$.
It outputs on input $x \in \{0,1\}^n$ and a string of random bits $r \in \{0,1\}^n$ in the following way:
$if \{x \in L\} \Rightarrow Pr[A(x,r)=Accept] \ge 1-\frac{1}{2n}$ and
$if \{x \notin L\} \Rightarrow Pr[A(x,r)=Reject] \ge 1-\frac{1}{2n}$
Given that $y_i,z \in \{0,1\}^n$ and that $r_i=y_i\oplus z$ for $1 \le i \le n$. where $\oplus$ is bit by bit xor operation:
I need to prove that if $\{x \notin L\}$ then for every set of n vectors $y_1, y_2,...,y_n$ there must be a vector $z$ for which all runs $A(x,r_1),A(x,r_2)...A(x,r_n)$ output $Reject$.
I think that i should use probabilistic method, so i tried to show that given any set of $n$ vectors $y_i$, i can randomly select $z$ so that the probability that all runs are rejected is greater than zero.
I can't figure what to do from here...
Am i thinking about this right? Help would be very appreciated, even a hint.
Thank you!