\documentclass{amsart}

\author{JC}

\title{Homework 1 solutions}

%
%    Comments on TeX included
%


\begin{document}

\maketitle


\begin{enumerate}


\item A brute force attack (trying the 25 possible decryption keys)
   gives ``no business like show business''.

\item As many of you pointed out, this is only true for $m > 0$.

%
%   Each math formula should be enclosed in dollar signs
%


   Here is the proof in case that $m > 0$. By definition,
   $N = q m + r$ where $q, r \in \mathbb{Z}$ and
   $0 <  r < \vert m \vert =m$. 
%
%  \mathbb is a font changing command to use the ``blackboard bold''
%  font. the parentheses { and } are used to form ``groups'' in TeX,
%  in this case the group just contains the letter Z --- see below for more
%  examples of grouping
%
   So $-N = - q m -r = - (q + 1) m + (m -r)$.
   Since $0 < r < m$, $0 < m - r < m$. 
   So by definition $m - r$ is $N \mod m$  
%
%  If I had written $N mod m$ I would have got an undesirable result (try it!).
%  The problem is that TeX reads this as a math formula in which the product
%  of some variables N, m, o, d, and m is being formed. \mod is a ``control
%  sequence'' which sets the letters m, o and d in roman type and spaces
%  the formula appropriately. Note that \mod can only be used in math formulae,
%  if you remove the $ signs round the ``N \mod m'' you get an error
%

\item  First we count the number of {\em ordered pairs} of disjoint three
    element sets.  
%
%   \em changes the font for emphasis. The parentheses are used to limit the
%   scope of the font change to the phrase ``ordered pairs''. Try removing the
%   parentheses
%
    We have $8 \choose 3$ choices for the first pair, and since we have used up
    $3$ elements we have $5 \choose 3$ choices for the second pair. 
    Each unordered pair corresponds to two ordered pairs so we get
\[
    \frac  { {8 \choose 3} \times {5 \choose 3} }{2} = \frac{56 \times 10}{2} = 280
\]
   unordered pairs.
%
%   Note how I formed groups to make sure that my fractions were built with the
%   correct numerators and denominators. 
%   
%   The \choose is handy for building binomial coefficients
%

\item  Solution One: it is easier to start by finding the probability that no two people
    have the same birthday. This is easily seen to be
    $\prod_{i =1}^{22} \frac{365 - i}{365}$.
%
%   Here I use grouping to make the subscript ``i=1'' and superscript ``22'' 
%
 Doing a Maple calculation with the command

\smallskip

\begin{verbatim}
evalf(product( (365-i)/365, i =1..22));
\end{verbatim}
 
\smallskip
%
%   smallskip inserts a small vertical space
%
%   the verbatim environment sets what is inside exactly as you typed it
%   in a distinctive typeface
%
\noindent   gives us a result about $0.507$. 
%
%   I am not starting a new paragraph so I use \noindent to kill the indentation
%

\medskip


\noindent Solution Two: Using the Proposition on Page 28, we evaluate the
   expression $\sqrt {2 \ln 2} \sqrt{365}$ with the Maple command
\smallskip 
\begin{verbatim}
evalf( sqrt(2 * ln(2)) * sqrt(365) );
\end{verbatim}
\smallskip
  and get an answer about $22.49$


\medskip

\noindent Solution Three (by special request): We ignored leap years. Do they make a difference?
  Pope Gregory XIII ruled that leap years occur in years whose dates are multiples of four, except
  for years whose dates are multiples of one hundred but not multiples of four hundred. So
  in a typical stretch of four hundred years we get ninety seven leap years; if we let
  $N = 365 \times 400 + 97 = 146097$ then the probability of having a birthday which is not
  Feb 29 is $400/N$, and the probability of having Feb 29 as a birthday is $97/N$. 
   
  Now it is easier to phrase the solution as a counting argument. Let us enumerate our 23
  people in some order and let $b_i$ be the birthday of person $i$. There are
  $M_0 = \prod_{i=0}^{22} (366 - i)$ (about $4.5 \times 10^{58}$) sequences of birthdays with
  no repetitions, and of these 
  $M_1 = \prod_{i=0}^{22} (365 - i)$ (about $4.2 \times 10^{58}$) do not contain Feb 29.
  The probability of a sequence which does not contain Feb 29 is $(400/N)^{23}$,
  the probability of a sequence which does contain one Feb 29 is $(97/N) (400/N)^{22}$. 
  
  Putting it all together we have that the probability of not two birthdays being the same
  is
\[
   (M_0 - M_1) (97/N) (400/N)^{22} + M_1 (400/N)^{23}
\]
  or about $0.493$, so the probability that two are the same is about $0.507$.



\item  R is the most common letter in the ciphertext and so we make the hypothesis that
      R = E. Now note that QJ appears in the ciphertext, and that Q also appears 
      at the end of a word in the ciphertext. The only vowel which appears commonly in English
      at the end of a word is E (see table of digrams with blanks on p 35) and we already
       have a candidate for E, so we hypothesise that Q is a consonant. Much the most
      common two letter words starting with a consonant are TO and BE (see table of common
      English words on p34), and since we already
      have a candidate for E we hypothesise that Q=T and J=O. This is consistent with their
      frequent appearances in the ciphertext. 

      Now under this hypothesis GRQQRO=?ETTE? so we hypothesise that O=R and G=B or L.
      Our current guess starts like this (decrypted characters in lowercase):
\smallskip
\begin{verbatim}
      PBsYGe Getter KreNSeIEBeP CGoIe oKteI 
\end{verbatim}
\smallskip     
       I also appears at the end of two two-letter words BI and CI in the ciphertext. So now we 
      hypothesise that K=F, I=N and that B and C are both vowels. So our new guess starts out
\smallskip
\begin{verbatim}
      PBnYGe Getter freNSenEBeP
\end{verbatim}
\smallskip     

      The most common digram where E follows a vowel is IE, so hypothesise B=I.
 
\smallskip
\begin{verbatim}
      PinYGe Getter freNSenEieP CGone often
      neCrGX PSKKiEe to VeErXMt PSLPtCntiCG
      enYGiBA PentenEeP, CGtAoSYA FeeMinY UorV
      LreCFP in HCFeP Cn enorHoSP ViKKerenEe.  
\end{verbatim}
\smallskip     

      Looking at FeeMinY at noting that ING is a common trigram we hypothesise that
      Y=G, then looking at PingGe and noting that G=B or L we hypothesise G=L.
      
\smallskip
\begin{verbatim}
      Pingle letter freNSenEieP Clone often
      neCrlX PSKKiEe to VeErXMt PSLPtCntiCl
      engliPA PentenEeP, CltAoSgA FeeMing UorV
      LreCFP in HCFeP Cn enorHoSP ViKKerenEe.  
\end{verbatim}
\smallskip     
     
      Now it is easy to see that P=S, A=H, E=C, C=A.

\smallskip
\begin{verbatim}
      single letter freNSencies alone often
      nearlX sSKKice to VecrXMt sSLstantial  
      english sentences, althoSgh FeeMing UorV
      LreaFs in HaFes an enorHoSs ViKKerence
\end{verbatim}
\smallskip     

      Now all in a rush we get N = Q, S =U, X=Y, K=F, L=B, H=M, V=D, U=W, M=P, F=K

\smallskip
\begin{verbatim}
      single letter frequencies alone often
      nearly suffice to decrypt substantial  
      english sentences, although keeping word
      breaks in makes an enormous difference
\end{verbatim}
\smallskip     



\item This one succumbs to a  analysis similar to that for the last question.
      The only wrinkle is there are no E's in the plaintext.

\smallskip
\begin{verbatim}
 "'Sybil,' said I, "thing of loathing -- sybil, fury in bird's clothing!
By God's radiant kingdom soothing all man's purgatorial pain,
Inform this soul laid low with sorrow if upon a distant morrow
It shall find that symbol for -- oh for its too long unjoin'd chain --
Find that pictographic symbol, missing from its unjoin'd chain'
Quoth that Black Bird, 'Not Again'"

"And my Black Bird, still not quitting, still is sitting, still is sitting
On that pallid bust -- still flitting through my dolorous domain;
But it cannot stop from gazing for it truly finds amazing
That, by artful paraphrasing, I such rhyming can sustain --
Notwithstanding my lost symbol I such rhyming still sustain--
Though I shan't try it again!"
\end{verbatim}
\smallskip     


    It comes from the English translation (by Gilbert Adair) of Perec's
    three hundred page novel ``La disparition''. Neither the original nor the translation
    contains a single e.



\end{enumerate}




\end{document}
