There are $100$ people, each of whom own a number between $1$ and $100$ inclusive. Known that one number appear for more than $50$ times, they'll go to a switch in a random order. The last person should answer which number appear for so many times.
They can discuss before given the numbers. How many states at least should the switch have?
A simple solution is $10100$ states, meaning two numbers $p$ and $q$, initially $p=0$. For each person do
if p=0 or q=num:
p:=p+1, q:=num
else
p:=p-1
and finally $q$ is the answer.
However $10100$ is not the smallest solution. I can reach $5001$, but is it the end?
(not sure how to tag this question)