\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{geometry}
\usepackage{hyperref}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2570}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{Created=Tuesday, September 21, 2004 06:51:08}
%TCIDATA{LastRevised=Sunday, January 08, 2006 14:30:39}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{CSTFile=40 LaTeX article.cst}

\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}
\geometry{left=0.6in,right=0.5in,top=0.4in,bottom=0.5in}

\begin{document}


\begin{center}
\bigskip {\Large Puzzle 3 - SOLUTIONS}

\bigskip
\end{center}

\begin{problem}
A king has his birthday. So he decides to let go some of his prisoners. He
actually has 100 prisoners at the moment. They are each in a separate cell,
numbered from 1 to 100. Well, he is a high tech king. He can close or open
any prison door by a single click on the cell's number on his royal laptop.
When he clicks at a locked door, it opens. When he clicks at an open door,
it locks. \ At the beginning, every door is locked. First the king clicks on
every number from 1 to 100 (therefore opening every door). Then he clicks on
every second number from 1 to 100, (i.e.2, 4, 6, 8, 10, . . . ). \ Then he
clicks on every third number.(i.e. 3, 6, 9, 12, . . . ) \ Now he is opening
some doors, locking others. \ Then he clicks on every fourth number. (i.e.
4, 8, 12, 16, \ . . . .) \ Then on every fifth.... \ And so on, every sixth,
every seventh, etc. \ Until every 100th; finally, he only clicks on the
number 100. Then he orders that the prisoners that find their door open may
go free. \ Who gets to go and who has to stay?
\end{problem}

\bigskip

\begin{solution}
Instead of mentally repeating all steps, focus on a single cell. Say we are
in cell $48$. What happens to our door?

We will get a click whenever the king clicks

on every 1st cell

on every 2nd cell

on every 3rd cell

on every 4th cell

on every 6th cell

on every 8th cell

on every 12th cell

on every 16th cell

on every 24th cell

on every 48th cell

$10$ clicks. It appears, we're staying. We make the following observations.

\begin{enumerate}
\item Every click corresponds to a factor of the cell's number. Thus the
number of clicks on a cell equals the number of factors the cell's number.

\item An even \ number of clicks means staying in prison. An odd number of
factors means we're free.
\end{enumerate}

So the question can be rephreased: What numbers under $100$ have an odd
number of factors?

The question can be settled by just checking all numbers. We find that these
numbers are%
\[
1,4,9,16,25,36,49,64,81,\text{ \ and }100 
\]

In other words, the square numbers.

It is true: Every number has an even number of divisors, except for the
square numbers that have an odd number of divisors. The reason for that is
that divisors always come in pairs. For example, $4$ is a divisor of $48$
because also $12$ is: because $4\cdot 12=48$. The way of obtaining an odd
list is when one number is a pair with itself. Two examples are $98$ and $81$

\begin{tabular}{|l|l|l|l|l|l|l|}
\cline{1-3}\cline{5-7}
& $98$ &  &  &  & $81$ &  \\ \cline{1-3}\cline{5-7}
$1$ &  & $98$ &  & $1$ &  & $81$ \\ \cline{1-3}\cline{5-7}
$2$ &  & $49$ &  & $3$ &  & $27$ \\ \cline{1-3}\cline{5-7}
$7$ &  & $14$ &  &  & $9$ &  \\ \cline{1-3}\cline{5-7}
\end{tabular}
\end{solution}

\end{document}