\documentclass[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\usepackage{color}
\usepackage{fancyhdr}
\usepackage{multicol}
\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2570}
%TCIDATA{}
%TCIDATA{Created=Tuesday, February 26, 2013 09:35:58}
%TCIDATA{LastRevised=Saturday, September 14, 2013 14:30:52}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{ComputeGeneralSettings=0,15,15,0,0,0,0}
%TCIDATA{ComputeDefs=
%$P\left( x\right) =3x^{3}+5x^{2}+4x+1$
%$f\left( x\right) =2x^{2}+2$
%}
\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}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}
\geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in}
\pagestyle{fancy}
\lhead{\color{blue} AMATYC}
\chead{ \LARGE Spring 2013 - Solutions}
\rhead{ page \ \thepage}
\lfoot{\small \copyright $\;$ copyright Hidegkuti, 2013}
\rfoot{\small Last revised: June 14, 2013}
\cfoot{}
\textwidth 7.5in
\textheight 9.7in
\setlength{\headheight}{28pt}
\setlength{\parindent}{0pt}
\begin{document}
\begin{enumerate}
\item[14.] A binary string is a sequence of 1's and 0's, such as 10011 or
11101010. How many different binary strings of length 6 are there such that
no two are reversals of each other or add up to 111111?%
%TCIMACRO{\TeXButton{5 col begin}{\begin{multicols}{5}}}%
%BeginExpansion
\begin{multicols}{5}%
%EndExpansion
A. $22$ \
%TCIMACRO{\TeXButton{correct}{\color{black}}}%
%BeginExpansion
\color{black}%
%EndExpansion
B. $23$ \
C. $\ 24$
D. $\ 25$
E. $\ 26$ \ \
%TCIMACRO{\TeXButton{multicol end}{\end{multicols}}}%
%BeginExpansion
\end{multicols}%
%EndExpansion
Solution: \ There are $2^{6}=64$ six-long binary strings. \ We will count
the compement and subtract it from $64$. \ If we interpret these numbers as
written in base $2$, they are the numbers from $0$ to $63$. \ We can then
pair them up so that the pairs add up to 111111 - which is the same as two
numbers adding up to $63$. \ So the pairs are $0$ with 63, $1$ with $62$, \
\ and so on, $30$ with $33$, and finally $31$ with $32$. \ So if we select
one from the pair into our collection, then we cannot select the other. \
How about the reversal? \ Each number has a unique number as their reversal.
\ This is another number UNLESS the number is symmetrical and is therefore
its own reversal. \ How many such symmetrical numbers are there? \ We claim $%
8$. \ This is because we have complete freedom to select the first three
digits - giving us $8$ choice but then there is no choice but to duplicate
the triple backwards to get a symmetrical string. \ For example 110 will
give us the string 110011$.$ \ So, out of the $64$ strings 8 are symmetrical
and so the other 56 can be paired into $28$ pairs where they are each
other's reversal. \ The question is: can we pick just one from each of the $%
28$ pairs so that no two add up to 63?
Solution: \ The blue lines connect two numbers that add to 111111 and the
red lines connect strings that are reversals of each other.\FRAME{dtbpF}{%
4.2601in}{3.3572in}{0pt}{}{}{pic14.bmp}{\special{language "Scientific
Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file
"F";width 4.2601in;height 3.3572in;depth 0pt;original-width
0.1315in;original-height 0.0977in;cropleft "0";croptop "1";cropright
"1";cropbottom "0";filename 'pic14.bmp';file-properties "XNPEU";}}If we
wanted to collect numbers in a set such that no two are connected, then
- we can pick one from each pairs such as $0$-$63$ or $7$-$56$
- we can pick exactly two from each of the squares. \ For example, the first
square, containing $1$-$32$-$31$-$62,$ we can either select the pair 1 and
31 or the pair $32$ and $62$.
This means that a \ maximum of $32$ such numbers can be collected.
\end{enumerate}
\end{document}