\problemdata     
{S01-PS3-4}           
{structural induction}
{}              
{F00-PS3, S01-PS3} 		
{S01 Karger}        	

\begin{problem} 

The set $SSS$ of ``super-symmetric strings'' is defined as follows:
\begin{enumerate}
\item
The length one strings consisting of individual letters of the
alphabet, $a$, $b$, $c$, $d$, $\ldots$, $z$, are in $SSS$. 
\item
If $\alpha$ and $\alpha'$ are two strings in $SSS$ then the string
$\alpha \alpha' \alpha$ is in $SSS$.
\item
$SSS$ contains nothing else.
\end{enumerate}
\bparts
\ppart
Which of the following are super-symmetric strings?\\
i.  a\\     
ii.  aaaba\\   
iii.  abcbacabcba\\
iv. $\lambda$, the empty string\\
v. abaabcbaaba\\

\solution{

i. Yes.  This is stated in part 1 of the definition.\\
ii. No.  This string is not of the form $\alpha \alpha' \alpha$.\\
iii. Yes.  Formally, consider $\alpha'=aca$, $\alpha=bcb$.  Then we have
a string of the form $a \alpha \alpha' \alpha a$, which is in $SSS$
by parts 1 and 2 of the definition.\\
iv.  No.  By part 3 of the definition\\
v. Yes. Similar reasoning to part iii shows that the string $bcb$ is in the 
middle of the super-symmetric\\ 
string, with the string $a$ wrapped around it, and with the string
$aba$ wrapped around that.

}

\ppart
Prove by structural induction that in any super-symmetric string $\alpha$, 
exactly one letter appears an odd number of times.\\


\solution{

\textbf{Proof:} Define $P(e)$: String $e$ has exactly one letter which appears an odd number of times.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall e \in SSS \ P(e)$.\\
1. (Base) $P(a)$\>\>\>\>The string $a$ has exactly one letter which appears an odd number of times.\\
2. (Base) $P(b)$\>\>\>\>Same for the string $b$\\
$\vdots$\\
26. (Base) $P(z)$\>\>\>\> Still has exactly one letter which appears once.\\
27. (Inductive Step) $\forall e, e' \in SSS \ P(e)\wedge P(e') \longrightarrow P(ee'e)$ \\
\>1. Fix $e,e' \in SSS$.\\
\>2. Assume $P(e) \wedge P(e')$.  That is, each of $e$ and $e'$ has exactly one letter which\\
\>\>appears and odd number of times.\\
\>3. By the inductive hypothesis, both $e$ and $e'$ have exactly one letter which appears an odd\\
\>\> number of times.  When we form the string $ee'e$, the letters in $e$ all get repeated, \\
\>\> and thus they all appear an even number of times.  By the IH, there is one letter in $e'$\\
\>\> which appears an odd number of times in $e'$.  Now, even if this letter is also present in\\
\>\>$e$, it will still appear an odd number of times in $ee'e$ (since
the sum of an odd number \\
\>\>and an even number is odd).  Therefore, we
have shown $P(ee'e)$.\\ 
\>4. QED.\\
\end{tabbing}
}

\eparts        
\end{problem}
