Online generation of uniform samples
Due to the dubious nature of the question, I only provide hints.

Have you tried the obvious? With probability $\frac{1}{n}$, add the new element to the sample. If it is added, choose one of the elements already in the sample uniformly at random and drop it. Sounds about fair, does it not?

For a proof, you will have to proceed inductively. In the step, you assume that $S_{n-1}$ is indeed a uniform sample. From this and the way you choose whether to include $x_n$ and which element to drop, you have to get that $S_n$ is a uniform sample, too.

Try if you can prove above idea correct. If it is not, find out where the problem is and fix it. See this answer to a similar question for a detailed application of this technique.