Majority and Chip Problems

Given a set $\{x_1, x_2, \ldots, x_n\}$, each element of which
is colored either red or blue, we must determine an element of
the majority color by making equal/not equal color comparisons
$x_u : x_v$; when $n$ is even, we must report that there is no
majority if there are equal numbers of each color. How many such
questions are necessary and sufficient?
We will give answers in the worst and in the average cases and
show that this problem is closely related (in the worst case) to
the chip problem.

The ``chip problem'' is a system diagnosis problem in which we
must determine which components (chips) in a system are
defective, assuming the majority of them are good. Chips are
tested as follows: Take two chips, say $A$ and $B$, and have $A$
report whether $B$ is good or bad. If $A$ is good, the answer is
correct, but if $A$ is bad, the answer is unreliable and can be
either wrong with probability $\alpha$ or right with probability
$1-\alpha$. We show the limits of the relationship between chip
and majority problems by showing that algorithms for the chip
problem can violate lower bounds on average performance for the
(modified) majority problem and we propose an algorithm for the
biased chip problem whose average performance is better than the
average cost of the best algorithm (to our knowledge) for the
biased majority problem.