\documentclass[twoside]{article}
\usepackage{amssymb,amsfonts,amssymb,amsthm}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[latin1]{inputenc}%permite escrever com acentos, como no Word
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% POR FAVOR NÀO MODIFIQUEM OS DADOS ABAIXO
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagestyle{myheadings} \topmargin =-20pt \marginparwidth = 45pt
\evensidemargin = -15pt \oddsidemargin = -15pt \textheight = 670pt
\textwidth = 500pt \linespread{1.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\newtheorem{myth}{Teorema}[section]
\newtheorem{mylem}{Lema}[section]
\newtheorem{mypro}{Proposi\c c\~ao}[section]
\newtheorem{mydef}{Defini\c c\~ao}[section]
\newtheorem{myrem}{Observa\c c\~ao}[section]
\newtheorem{mycor}{Corol\'ario}[section]
\newtheorem{myex}{Exemplo}[section]
\newcommand{\cqd}{\hspace{10pt}\fbox{}}
\newcommand{\cqdf}{\hspace{10pt}\rule{5pt}{5pt}}
%
\begin{document}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% CABEÇALHO DA PÁGINA - POR FAVOR NÀO MODIFIQUEM!
\pagestyle{empty}
\title{\vspace{-1in}\parbox{\linewidth}{\footnotesize\noindent
{\sc  \bf V Bienal da SBM}
\newline
{\sc  \bf Sociedade Brasileira de Matemática}
\newline
{\sc \bf UFPB - Universidade Federal da Paraíba}
\newline
\bf 18 a 22 de outubro de 2010 }
\newline\newline
%%%%%%%%%%%%%%%%%%%FIM DO CABEÇALHO%%%%%%%%%%%%%%%%%%%%%%%%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% ESCREVER O TÍTULO DO TRABALHO NO COMANDO ABAIXO COM
%%% LETRAS MINÚSCULAS!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
{\sc o problema das argolas chinesas}
%\vskip -0.5truecm
\author{\sc Wanderson Aleksander da Silva Oliveira\,\thanks{Universidade Federal de Pernambuco,\,
UFPE, PE, Brasil,\, w.aleksander@bol.com.br} \,\,\,\,\&\,\,\,\, 
Karla Polyana Silva Falcão\,\thanks{Universidade Federal de Pernambuco,\,
UFPE, PE, Brasil,\,karlatahan@gmail.com.br
}}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% NAO PREENCHER O COMANDO \date{} ABAIXO, DEIXAR COMO ESTÁ!
%% NÃO RETIRAR OS COMANDOS \maketitle E \thispagestyle{empty}
\date{}
\maketitle \thispagestyle{empty} \vspace{-10pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%

\section{Introdução}
O puzzle com o qual trabalharemos neste minicurso é conhecido nos Estados Unidos pelos nomes de Baguenaudier ou \textit{chinese rings}. Já aqui no Brasil, é conhecido como Anéis Chineses. O jogo foi criado, segundo sua lenda, por um general que queria entreter a tropa durante os intervalos da guerra. Wikipedia é a fonte. A primeira vez que foi estudado a fundo foi por Eder Lucas, criador do problema das Torres de Hanoi e primeiro a mostrar uma solução consistente. Interessante é que a solução dada por ele (e que será discutida aqui) pode ser usada tanto para o problema dos Anéis Chineses quanto para as Torres de Hanói. 

O jogo consiste numa barra fixa com várias argolas entrelaçadas, e um garfo que está preso nessas argolas, iniciando numa configuração determinada. O objetivo é soltar o garfo da barra fixa.

\begin{figure}[h]
\centering
\includegraphics[scale=0.35]{Argolas.eps}
\caption{Uma configuração das Argolas Chinesas}
\label{fig:}
\end{figure}

Primeiramente, definimos o que é um movimento do jogo: é alterar a posição do garfo com respeito às argolas, ou seja, aplicar um movimento é colocar ou retirar uma argola no garfo. Um dos problemas da outra representação do problema é definir quando uma argola está dentro ou não do garfo, que neste segundo modelo é representado por uma corda. Portanto, também fica difícil definir o que é um movimento. No nosso caso, utilizaremos apenas o caso tradicional, em que o garfo é fixo.

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{fig2.eps}
\caption{Outra representação física do problema das argolas chinesas}
\label{fig:}
\end{figure}

Para não ser necessário manipular o jogo o tempo todo, podemos abstrair o jogo da seguinte forma: associamos a cada argola o número 1 ou 0. Se a argola estiver dentro do garfo associamos a 1 e associamos a 0 se não estiver. Além disso, o algarismo da esquerda sempre representa a argola mais externa (ou mais fácil de ser mexida). Cada posição está bem representada então e um movimento será uma alteração em um dos dígitos.

Por exemplo: Na configuração anterior, na figura 1, estamos na posição $0001111111$.

Entretanto, só com a manipulação (ou para os de boa visão espacial) vemos que só dois tipos de movimentos são possíveis:
\begin{enumerate}

\item Alterar o primeiro algarismo a qualquer momento;
\item Alterar o primeiro dígito após o primeiro 1, da esquerda pra direita.
\end{enumerate}

Tente mostrar porque só esses dois movimentos são possíveis.
\vspace{5cm}

Já que aprendemos quais são os movimentos permitidos, podemos agora nos preocupar em determinar qual o número mínimo de movimentos para retirar o garfo das argolas. Denotaremos por $\mathcal{A}(t)$ o número mínimo de movimentos para soltar o garfo de $t$ argolas. Comecemos com o caso de 7 argolas, mais simples:

$$\mathcal{A}(7)\ =\ 1111111\  \underrightarrow{\mathcal{A}(5)}\  0000011\  \underrightarrow{1}\  0000010\ \underrightarrow{\mathcal{A}(5)}\ 1111110\ \underrightarrow{\mathcal{A}(6)}\ 0000000$$

Generalizando essa idéia, temos que:

$$\mathcal{A}(n)\ =\ 111111\ldots 1\  \underrightarrow{\mathcal{A}(n-2)}\  0000\ldots 011\  \underrightarrow{1}\  0000\ldots 010\ \underrightarrow{\mathcal{A}(n-2)}\ 1111\ldots 110\ \underrightarrow{\mathcal{A}(n-1)}\ 00000\ldots 00$$

Conseguimos portanto nossa primeira relação de recorrência:
\begin{equation}
\mathcal{A}(n)=\mathcal{A}(n-1)+2\mathcal{A}(n-2)+1
\label{rec1}
\end{equation}

\textbf{Exercício: } Complete a tabela a seguir usando a recorrência de \ref{rec1} a fim de obter valores para o número mínimo de movimentos nos primeiros casos:

\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
 n & 1  &  2  &  3  &  4  &  5  &  6  &  7  &  8  &  9  &  10  \\ \hline \hline
 $\mathcal{A}(n)$ & & & & & & & & & & \\ \hline
\end{tabular}
\caption{A função $\mathcal{A}(n)$}
\label{tab:}
\end{table}


\textbf{Exercício: } É possível verificar alguma propriedade aparente desta tabela? Elabore uma hipótese.
\vspace{2cm}

\textbf{Exercício: } Agora mostre que a hipótese é verdadeira, usando indução e a relação de recorrência \ref{rec1}.
\vspace{4cm}

Então agora temos duas fórmulas de recorrência para trabalhar, mais simples que a anterior:

\begin{eqnarray}
\mathcal{A}(n)=2\mathcal{A}(n-1), n\equiv 0\ (mod\ 2)\\
\mathcal{A}(n)=2\mathcal{A}(n-1)+1, n \equiv 1\ (mod\ 2)
\end{eqnarray}

\textbf{Exercício: } Mostre que esta relação é verdadeira.
\vspace{3cm}

Agora buscamos uma relação na qual possamos relacionar termos pares entre si e ímpares entre si, de forma que possamos usar apenas uma fórmula para quebrar a recorrência.

\textbf{Exercício: } Tente encontrar tal relação de recorrência desse tipo, usando o método anterior.
\vspace{2cm}

Busquemos agora qeubrar a relação de recorrência dada no exercício anterior (Você deve ter achado que $\mathcal{A}(n)=4\mathcal{A}(n-2)+2$, se $n$ é par e que $\mathcal{A}(n)=4\mathcal{A}(n-2)+1$, se $n$ é ímpar). 

Primeiro vamos ver como quebrar a relação entre os $\mathcal{A}(n)$, quando $n$ é par. 

\begin{table}[h]
\centering
\begin{tabular}{lll}
$\mathcal{A}(n)$ & = & 4$\mathcal{A}(n-2)$+2 \\
 & = & 4(4$\mathcal{A}(n-4)$+2)+2  = $4^2\mathcal{A}(n-4)+2+2^2$ \\
 & = & $4^2(4\mathcal{A}(n)+2)+2+2^2$  =  $4^3\mathcal{A}(n-6) + 2 +2^2 +2^3$ \\
 & & \vdots \\
 & = & $4^r\mathcal{A}(n-2r)+2+2^2 + 2^3 + \ldots + 2^{r-1} $ \\
\end{tabular}
\end{table}

Como conhecemos $\mathcal{A}(2)$, fazemos o processo até que $n-2r=2$, ou seja, até $r=\frac{n-2}{2}$. Manipulando todo o resultado, temos finalmente que $$\mathcal{A}(n)=\frac{2}{3} (2^n -1)$$

\textbf{Exercício: } Repita o processo para o caso dos valores de $n$ ímpares.
\vspace{5cm}

\section{Argolas Chinesas e Códigos de Gray}

Uma das relações mais incríveis que estão embutidas na resolução do problema das Argolas Chinesas são os Códigos de Gray, que são códigos binários utilidados em sistemas mecânicos e cuja propriedade principal é que, ao passarmos de uma palavra a outra do código, variamos apenas uma entrada (ou bit). Além da importância no passado, atualmente é bastante utilizado nos Mapas de Karnaugh.

Veja as palavras (ordenadas) do Código de Gray com 5 entradas:

\begin{table}[h]
\centering
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{tabular}
\end{table}

Sempre de uma palavra para a sua vizinha (incluindo os extremos), tem apenas um bit de diferença. Notemos ainda que a solução das Argolas Chinesas está embutida aí.

\textbf{Exercício: } Aonde?

Com a análise do item anterior, podemos montar um programa (no nosso caso, em $C++$), que exiba a solução, dado apenas o número de peças.

\subsection{Curiosidade}

Ao escrevermos num tabela o número de movimentos mínimos necessários, uma propriedade interessante surge. Note:

\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\hline
$n$ & $\mathcal{A}(n)$ & $\mathcal{A}(n)_2$ \\ \hline \hline
1 & 1 & 1 \\ \hline
2 & 2 & 10 \\ \hline
3 & 5 & 101 \\ \hline
4 & 10 & 1010 \\ \hline
5 & 20 & 10101 \\ \hline
6 & 41 & 101010 \\ \hline
7 & 82 & 1010101 \\ \hline
8 & 165 & 10101010 \\ \hline
\end{tabular}
\end{table}

\textbf{Exercício: } Você consegue explicar o porquê?



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% REFERÊNCIAS
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Referências}
\setcounter{equation}{0}
\noindent[1] {\it http://www.mathvids.com/lesson/mathhelp/617-lecture-7-chinese-rings-puzzle}. Acessado em: 22 de julho de 2010.

\noindent[2] {\it http://pt.wikipedia.org/wiki/Codigo\_de\_Gray}. Acessado em: 22 de julho de 2010.

\end{document}
