\problemdata                                                             
        {Weighing} % latex-friendly label for the prob.
        {Weighing ball} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 1, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
You are given 12 identical looking balls, and told that
one of them is of different weight from the other 11, but you don't
know in advance whether it is heavier or lighter. Can you
find the ball that is of different weight using only 3 weighings on a balance scale?

\solution{ 
The answer is Yes. 
Step 1. Divide into groups of 4 balls. Place two of these groups
on two pans.

Two possible outcomes:
\begin{enumerate}                                                             
\item Equal. So the 8 balls that were weighed must be of the same weight,     
label them N (for ``normal'') and one of the other 4 is of different weight,  
call them D.                                                                  
                                                                              
  Step 2. Place 3 D balls on one side and 3 N balls on the other side for     
the second weighing.                                                          
Three possible outcomes again:                                                
\begin{enumerate}                                                             
 \item Equal. The remaining D must be the ball of different weight.           
 \item DDD side is heavier. So the ball of different weight is among these    
three and heavier. Now we can finish in one more weighing using               
the following approach: \\                                                    
Place a ball on each pan of the balance. There are 3 possible outcomes:       
\begin{enumerate}                                                             
\item The left pan is heavier. Then the ball in the left pan is the answer.   
                                                                               
\item The right pan is heaver. Then the ball in the right pan is the answer.   
                                                                               
\item The pans are equal. Then the third ball must be the heavy one.           
                                                                               
\end{enumerate}                                                                
 \item DDD side is lighter. Similar to previous case.                          
\end{enumerate}                                                                
                                                                               
\item Not Equal.  Call the heavier side balls H and the lighter side balls L.  
Then there are 4 H's , 4 L's and 4 N's (the 4 that we didn't weigh are of      
the same weight).                                                              
                                                                             
  Step 2. Place 3 H's and 1 L on one side and 1 H and 3 N's on the other side
for the second weighing. There are 3 possible outcomes:                      
                                                                             
\begin{enumerate}                                                            
\item Equal. The ball of different weight is among the remaining 3 L's       
and is lighter. We can find it in one more weighing.                         
                                                                             
\item 3 H's , 1 L side is heavier. Then one of the three H's must be         
heavier than the rest. We can find it in one more weighing.                  
                                                                             
\item 3 H's , 1 L side is lighter. Then either the L on this side is         
lighter than the rest or the H on the other side is heavier than the rest.   
We can compare one of them with an N ball and find the ball of different     
weight!                                                                      
                                                                             
\end{enumerate}                                                              
\end{enumerate}                        
                                       
\textbf{Alternative solution:}         
\medskip                               
                                       
\textbf{Key:}                          
\begin{table}[h]                       
\begin{tabular}{|c|c|}                 
\hline                                 
R&put ball on right tray \\ \hline     
L&put ball on left tray  \\ \hline     
N&leave ball out \\ \hline             
\end{tabular}                          
\end{table}                            
                                       
{\bf Assignments on the scale}
\medskip 
\begin{table}[h]
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}

\hline 
Balls&         1& 2& 3& 4& 5& 6& 7& 8& 9& 10 &11 &12\\ \hline 

Weighing 1&    R &R &R &R &L &L &L &L &N &N &N &N \\  \hline                    
Weighing 2&    R &R &L &L &L &R &N &N &R &L &N &N \\  \hline                    
Weighing 3&    R &L &L &R &N &N &L &R &N &R &L &N \\   \hline                   
\end{tabular}                                                                   
\end{table}                                                                     
We observe what happens to the scale at each of the three weighings (balance, leans to the left, leans to the right). For example, if Ball 10 is Heavy, the scale will first balance, then lean to the right, then lean to the left. If Ball 10 is Light, the balance will behave in the ``opposite'' way: it will first balance, then lean to the left and then lean to the right. Notice that in all cases, on

\paragraph{Conditions:}
\begin{enumerate}
\item At each weighing, number of R = number of L (for balance)

\item Each triple (column) should be distinct. Moreover, its ``mirror image'' (L-R) should not be present since we don't know whether the ball is heavier or lighter.

\end{enumerate}
}
\end{problem} 


