        \problemdata       % Takes 5 *mandatory* arguments
        {coin-weighings}             % latex-friendly label for the prob.
        {graphs}  % The topic(s) of the problem content.
        {Rosen 8.2 exercise 8}               % Source (if known)
        {F01 PS5-3, F00 PS4} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).


\begin{problem}
%--------------------------------------
% source: Fall 2000  Problem Set 4, Rosen 8.2 exercise 8
% topic: decision trees


How many weighings using a balanced scale are needed in order to
find a counterfeit coin among eight coins if the the counterfeit coin
is either heavier or lighter than the others?  Describe an algorithm
to find the counterfeit coin using this number of weighings.

\solution{
Decision tree theory applied naively says that at least $log_{3}8=2$
weighings are needed, but in fact at least 3 weighings are needed. To
see this, consider what the first weighing might accomplish. We can
put one, two or three coins in each pan. If we put one in each pan,
and the scale balances, what we know is that the counterfeit must be
among the remaining 6. Similarly, if we put 2 and the scale balances,
we narrow down our list of suspects to the remaining 4. If we put 3 in
each pan and the scale balances, we are in really good shape, but what
if it doesn't? Then our list of suspects will be the 6 coins in the
scale. What this means is that however many coins we choose to put on
each pan (1,2 or 3), there's always a case where the list of suspects
after the first weighing will be $\geq 4$. One weighing is not enough
to distinguish the counterfeit from among a list of 4 suspects.

% In Tutorial 1, we showed that we can solve a bigger problem (12 coins)
% with three weighings, so we should be able to solve this one with the
% same number of weighings. So if we are lazy and we want to just use
% the algorithm we came up with in Tutorial, we just add 4 good coins to
% our collection and apply that algorithm.

However, a solution is available: Put two coins in each pan. If the
scale balances, then the search is reduced to the other four coins. If
the scale does not balance, then the counterfeit is among the four
coins on the scale. In both cases, after 1 weighing we have cut down
our list of suspects to 4. Call them A, B, C, D. First compare coins A
and B. If they balance, then the counterfeit must be among the other
2. In this case, compare C with A (which we now know must be good). If
they balance, then D is counterfeit. If not, C is counterfeit. On the
other hand, if A and B do not balance, then one of them is the
counterfeit. Compare A with C (which we know must be good). If they
balance, B is the counterfeit. If they do not, A is the counterfeit.
}



\end{problem}