\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\mod}{ \mbox { mod }}

\begin{document}

{\bf Tutorial 1 solutions. }

\date{}
 
\begin{enumerate}
\item A hundred soldiers are standing in an array of 10 columns and 10 rows.
Let $T_i$ be the tallest soldier in the $i^{th}$ column and 
$S_j$ the shortest soldier in the $j^{th}$ row ($i,j$ run from 1 to 10).
Who is taller: the tallest of the $S_j$'s or the shortest of the 
$T_i$'s? Prove your answer taking care of all the cases.


Let $X$ be the shortest among the $T_i$'s and let $Y$ be the tallest 
among the $S_j$'s. Then we will show that $S \geq Y$ in height.
Let $Z$ be the soldier at
the intersecion of the column of $X$ and the row of $Y$.
Then since $X$ is the tallest in his column, $X \geq Z$, and
since $Y$ is the shortest in his row, $Z \geq Y$. Hence $X \geq Y$.

\item Now 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?

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 approach done in the tutorial.
 \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}
\end{enumerate}


\end{document}


