Vote

The trick is to notice that the number of people on stage is simply the difference between people voting for Alice and for Bob, and those on stage are voting for whichever is greater. Once we notice this, the answer immediately follows; since people on stage are voting for Alice, this means Alice wins.

---

At any time, suppose that there have been $a$ voters for Alice and $b$ voters for Bob. We will show that the number of people on stage is $|a-b|$ , and they are all voting for Alice if $a > b$ and for Bob if $a < b$ . (And if $a = b$ , then there's nobody on stage.) We will prove this by induction on $a+b$ .

For $a+b = 0$ , we have $a = b = 0$ , and the statement is obvious. Suppose we have proven the claim for $a+b = k$ , and we will now prove the claim for $a+b = k+1$ .

Suppose the next voter votes for Alice. Before this, there were $a-1$ voters for Alice and $b$ voters for Bob. Then,

• If the stage is currently voting for Alice, then we get one additional person on stage. There were $|(a-1)-b| = a-b-1$ people on stage, and we have one more, so now there are $a-b = |a-b|$ people on stage, as claimed.
• If the stage is currently voting for Bob, then one person from stage is lost. There were $|(a-1)-b| = b-a+1$ people on stage, and one person is lost, so now there are $b-a = |a-b|$ people on stage, as claimed.
• If the stage is empty, then the stage now has one person. Since the stage was empty, we have $a-1 = b$ or $a = b+1$ , so now there is $1 = a-b = |a-b|$ person on stage, as claimed.

In all cases, we have proven the claim. If the next voter votes for Bob, it goes in a very similar way. Thus we have proven the claim for $a+b = k+1$ , and by induction, for all $a,b$ .

Now, there are people on stage, and they are voting for Alice. Among the possible outcomes we have, the only way this is achieved is if $a > b$ . Thus there are more people voting for Alice than Bob; this means Alice has majority.