There are $1000$ people in a hall. One person had their hand painted. Every minute everyone shake their hand with someone else. 
There are $1000$ people in a hall. One person had their hand painted. Every minute everyone shake their hand with someone else.
How much time is needed to paint all the hands? What is the best scenario? What is the worst scenario?
Scenarios are asking for max and min time to complete this task

Here is what I was thinking:
Assuming we start from one person and time $0$
$\frac{1}{1000}$ -one minute $\rightarrow$ $\frac{2}{1000}$ -one minute  $\rightarrow$ $\frac{4}{1000}$ -one minute $\rightarrow$ $\frac{8}{1000}$
Seems like pattern here is that the number of handshakes will double with every minute, so I would just need to find how long it takes to get to $\frac{500}{1000}$
$2n = 500 \implies n = 250$ times?
Feels very wrong and definitely don't know how to approach.
 A: At time zero, only one person has their hand painted. At minute one, two people have their hands painted. At minute two, two people paint two more people's hands, so there are four hands painted. At minute three, four people paint four more people's hands for a total of eight painted hands.
So for every minute that passes, $2^t$ people have their hands painted assuming people are only shaking with their right hand.
You need to find when $2^t=1000$. You may have to round your answer.
Hopefully this helps you get started on some case work.
A: I assume two people can't shake hands twice.  Then it must stop by minute 999.
Sort them into 25 bubbles of 40 people each. In 25 rounds of 39 minutes each, one bubble shakes its own hands, and the other bubbles are paired up.
Suppose the first paimted hand is in Bubble 25, and the last unpainted hand is in Bubble 24.  In round $k$, Bubble $b$ shakes hands with Bubble $24+k-b\pmod{25}$.  After round $k$, the dirty hands are in Bubble 25 and 1 to $k-1$.  So Bubble 24 isn't painted until the start of round 25, in minute $937$.
A: There are some ambiguities in the question, so I am going to make some assumptions

*

*All the hands painted means that all people must have atleast one of their hands painted, or everyone has just one hand(ouch)

*Two people who have already shook hands can do so however many times they want to

Also, for the purposes of this answer, I am going to refer to people with paint on their hands as coloured people(don't get offended please)
Best Case
Best case would be that every coloured person shakes hands with another person who:-

*

*Has never shook hands before with a coloured person

*Will only shake hands with non-coloured people after he has become coloured

This will result in doubling of cases after every minute.
In general,
Total number of cases $= T_n = 2^n$
Since there are 100 people in the room, you will need atleast 1000 handshakes
$$\therefore 2^t = 1000\\
\implies t = \lfloor{log_2(1000)}\rfloor + 1 \because t \in \mathbb{N} \\
\therefore t = 10  $$
Worst Case
Worst case would be that the person whom the first person shook hands with, will continue to shake hands with the same person. Therefore, it will theoretically take $\infty$ time for the worst case scenario.
