Let $[$n$]=\{1,2,...,$n$\}$ and g : $[$n$]7\{1,1\}$ be a function and let $<0\mathrm{.}1.$

We say that g is $-$good for S $[$n$]$ if $|$ Pi in S g$($i$)|$ n$1$$.$ Give a randomized

algorithm that finds g such that for a set S$,$ the probability that g is not $-$good is

at most $1.$ Note that your algorithm does not know the sets S ahead of time n$12$

$($otherwise it is trivial$).$ Give a randomized algorithm that finds g such that for fixed setsS$1,...,$St witht$=$n gis$-$goodforallsetswithprobability$1$o$(1).$Note that your algorithm does not know the sets S$,$ S$1,...,$ St ahead of time.