% (find-angg "LATEX/2010-1-MD-hanoi.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010-1-MD-hanoi.tex && latex    2010-1-MD-hanoi.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010-1-MD-hanoi.tex && pdflatex 2010-1-MD-hanoi.tex"))
% (eev "cd ~/LATEX/ && Scp 2010-1-MD-hanoi.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2010-1-MD-hanoi.dvi"))
% (find-dvipage "~/LATEX/2010-1-MD-hanoi.dvi")
% (find-pspage  "~/LATEX/2010-1-MD-hanoi.pdf")
% (find-pspage  "~/LATEX/2010-1-MD-hanoi.ps")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2010-1-MD-hanoi.ps 2010-1-MD-hanoi.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2010-1-MD-hanoi.ps 2010-1-MD-hanoi.dvi && ps2pdf 2010-1-MD-hanoi.ps 2010-1-MD-hanoi.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage  "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2010-1-MD-hanoi.pdf" (ee-twupfile "LATEX/2010-1-MD-hanoi.pdf") 'over)
% (ee-cp "~/LATEX/2010-1-MD-hanoi.pdf" (ee-twusfile "LATEX/2010-1-MD-hanoi.pdf") 'over)

\documentclass[oneside]{book}
\usepackage[latin1]{inputenc}
\usepackage{edrx08}       % (find-dn4ex "edrx08.sty")
%L process "edrx08.sty"  -- (find-dn4ex "edrx08.sty")
\input edrxheadfoot.tex   % (find-dn4ex "edrxheadfoot.tex")
\begin{document}

\input 2010-1-MD-hanoi.dnt

\def\psm#1{\left(\sm{#1}\right)}

%*
% (eedn4-51-bounded)

%Index of the slides:
%\msk
% To update the list of slides uncomment this line:
%\makelos{tmp.los}
% then rerun LaTeX on this file, and insert the contents of "tmp.los"
% below, by hand (i.e., with "insert-file"):
% (find-fline "tmp.los")
% (insert-file "tmp.los")


{\setlength{\parindent}{0pt}
Matemática Discreta

Notas sobre a aula de Torres de Hanói

2010jun02
}

\bsk

Na aula passada vimos vários modos, diferentes mas equivalentes, de
representar posições das Torres de Hanói ``em matematiquês''. Por
exemplo, a posição (com 5 discos)
%
$$\und{\begin{matrix}
  | & | & | \\
  | & | & | \\
  1 & | & | \\
  4444 & | & | \\
  55555 & 22 & 333 \\
  \end{matrix}}
$$
%
pode ser representada como:
%
$$\psm{ 1&0&0 \\ 0&2&0 \\ 0&0&3 \\ 4&0&0 \\ 5&0&0 \\ }, \quad
  \psm{ 0&0&0 \\ 0&0&0 \\ 1&0&0 \\ 4&0&0 \\ 5&2&3 \\ }, \quad
  (\{1,4,5\},\{2\},\{3\}), \quad
  ((1,4,5),(2),(3)), \quad
  12311
$$

É possível definir formalmente o conjunto das posições válidas para
$n$ discos para cada uma dessas representações (exercício!). Aí:
%
$$\begin{array}{l}
  \psm{ 1&0&0 \\ 0&2&0 \\ 0&0&3 \\ 4&0&0 \\ 5&0&0 \\ } Ý A_5 \subset ¯M_{5×3}(\N) \subset ¯M_{5×3}(\R), \\
  \psm{ 0&0&0 \\ 0&0&0 \\ 1&0&0 \\ 4&0&0 \\ 5&2&3 \\ } Ý B_5 \subset ¯M_{5×3}(\N) \subset ¯M_{5×3}(\R), \\
  (\{1,4,5\},\{2\},\{3\}) Ý C_5 \subset ¯\Pts(\N)^3, \\
  ((1,4,5),(2),(3)) Ý ??? \qquad \text{(pense! 8-))}, \\
  12311 Ý E_5 \qquad 
  \end{array}
$$

Nós sabemos definir {\sl informalmente} uma relação $R \subset
A_5×A_5$ tal que $aRb$ é verdade se e só se ``é possível ir da posição
$aÝA_5$ para a posição $bÝA_5$ em um movimento''; aí nós passamos para
a representação por números, definimos (informalmente) a relação $S
\subset E_2×E_2$, vimos que sabemos calcular $S \subset E_2×E_2
\subset \N×\N$, e representamos a relação $S$ graficamente.

Uma {\sl solução em $k$ passos} para o problema das Torres de Hanói
com $n$ discos (usando a representação ``$E$'') é uma seqüência (isto
é, uma lista)
%
$$(p_0, p_1, \ldots, p_k)$$
%
que obedeça as seguintes condições:

\msk

(i) $ýiÝ\{0,\ldots,k\}. p_iÝE_n$,

(ii) $ýiÝ\{1,\ldots,k\}. p_{i-1}Sp_i$,

(iii) $p_0$ é a posição inicial na representação $E$ (todos os discos no pino 1)

(iv) $p_k$ é a posição final na representação $E$ (todos os discos no pino 2).





%*

\end{document}

% Local Variables:
% coding:           raw-text-unix
% ee-anchor-format: "«%s»"
% End: