I am talking on a paper by Alonso, Reingold, Schott.
Lets play the following game.
I have $n$ elements $x_1,...,x_n$, each one colored RED or BLUE.
$n$ is odd.
Clearly either RED or BLUE is in the majority.
YOU have to determine which color is in the majority
(more accurately you must produce a statement like
``$x_{17}$ is colored the same as the majority'')
and can only ask questions of the form
ARE $x_i$ and $x_j$ the same color?
HOW MANY QUESTIONS WILL THIS TAKE?
Let $v(n)$ be the number of 1's in the binary representation of $n$.
We prove that
\begin{enumerate}
\item There is an algorithm doing this in $n-v(n)$ questions
\item No algorithm does better.
\end{enumerate}
(This talk can be considered an advertisement for my course
CMSC 752 next semester.)