Derandomizza il problema con taglio massimo usando $ log n $ bit

Question

Considera il problema massimo. Possiamo capovolgere $ n $ monete per generare un taglio casuale e per linearità delle aspettative lo otteniamo con "buona probabilità" il nostro taglio saremo più grandi allora $ frac {n} {2} $.

Usando pseudo generatori casuali (XOR per esempio) possiamo generare $ n $ bit indipendenti a coppie da $ log n $ bit casuali. Usando questo approccio, possiamo de-randomizzare il problema massimo con la complessità polinomiale.

Con quell'algoritmo, stiamo solo controllando $ n $ possibili tagli, dove ci sono un totale $ 2^n $. È promesso che un taglio "buono" è all'interno di questi $ n $ tagli? Come mai?