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

%*
% (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")


\def\sen{\operatorname{sen}}
\def\pmat#1{\begin{pmatrix} #1 \end{pmatrix}}
\def\bmat#1{\left|\begin{matrix} #1 \end{matrix}\right|}
\def\sm#1{\begin{smallmatrix} #1 \end{smallmatrix}}
\def\bsm#1{\left|\begin{smallmatrix} #1 \end{smallmatrix}\right|}
\def\psm#1{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)}
\def\subst#1{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]}

Matemática Discreta - Segunda Prova (P2)

PURO-UFF - 2009.2

9/dezembro/2009

Prof: Eduardo Ochs


\bsk
\bsk


% (find-dn4exfile "edrxdnt.tex")
\def\defvelhachar#1#2{\expandafter\def\csname velhachar-#1\endcsname{#2}}
\def\velhachar#1{\csname velhachar-#1\endcsname}
\defvelhachar .{}
\defvelhachar o{\circ}
\defvelhachar x{×}

\def\jvelha#1#2#3#4#5#6#7#8#9{
  \begin{array}{c|c|c}
    \velhachar #1 & \velhachar #2 & \velhachar #3 \\ \hline
    \velhachar #4 & \velhachar #5 & \velhachar #6 \\ \hline
    \velhachar #7 & \velhachar #8 & \velhachar #9 \\
  \end{array}
}

\def\pzero   {P_0 \equiv \jvelha o.o .x. o.x}
\def\pum     {P_1 \equiv \jvelha oxo .x. o.x}
\def\pdois   {P_2 \equiv \jvelha oxo ox. o.x}
\def\ptres   {P_3 \equiv \jvelha oxo .xo o.x}
\def\pquatro {P_4 \equiv \jvelha oxo xxo o.x}
\def\pcinco  {P_5 \equiv \jvelha oxo xxo oox}
\def\pseis   {P_6 \equiv \jvelha oxo .xo oxx}
\def\psete   {P_7 \equiv \jvelha oxo .x. oox}
\def\poito   {P_8 \equiv \jvelha oxo xx. oox}
\def\pnove   {P_9 \equiv \jvelha oxo .xx oox}
\def\pdez {P_{10} \equiv \jvelha oxo oxx oox}



\noindent {\bf (1)} (Total: 10.0 pontos). Neste problema você vai ter
que representar ``formalmente'' o Jogo da Velha em Matematiquês.
Lembre que em Matematiquês só temos números, valores de verdade,
listas e conjuntos; todos os outros objetos que vimos no curso ---
relações, funções, partições, etc --- podiam ser representados como
números, valores de verdade, listas ou conjuntos.

Vamos usar o símbolo `$\equiv$' para indicar ``mudança de notação'',
ou ``é representado como'', ou ``é uma representação para''. Por
exemplo, temos um modo óbvio de representar matrizes $3×2$ como um par
de listas de comprimento 3:
%
$$\psm{1 & 2 & 3 \\ 4 & 5 & 6} \equiv ((1, 2, 3), (4, 5, 6))$$

A lista $((1, 2, 3), (4, 5, 6))$ é a {\sl representação formal} da
matriz $\psm{1 & 2 & 3 \\ 4 & 5 & 6}$; a matriz $\psm{1 & 2 & 3 \\ 4 &
5 & 6}$ é a {\sl representação como matriz} da lista $((1, 2, 3), (4,
5, 6))$.

\msk

a) Crie um modo de representar posições do Jogo da
Velha em matematiquês, explique como esse seu modo funciona, e dê
exemplos. Se
%
$$\pzero \qquad\text{e}\qquad \pum$$
%
como é que essas duas posições, $P_0$ e $P_1$, são representadas?

\msk

b) Defina o conjunto $A$ de todas as ``posições do Jogo da Velha''
representadas matematicamente do modo que você inventou. Este conjunto
pode incluir ``posições'' que não podem acontecer num jogo de verdade
--- por exemplo, a posição que tem 9 `$\circ$'s.

\msk

c) Agora defina uma relação $J$ sobre o conjunto $A$ que diz quando é
possível ir de uma posição para outra em uma jogada. Por exemplo, $P_0
J P_1$ é verdadeiro porque em $P_0$ é a vez do `$×$', e se o `$×$'
joga em cima a posição $P_0$ ``vira'' $P_1$. Suponha que o `$\circ$'
sempre começa --- então se há um número igual de `$\circ$'s e `$×$'s
no tabuleiro é a vez do `$\circ$'s.

\msk

d) Encontre todas as continuações possíveis do jogo a partir de $P_1$.
Se você estiver em dúvida do que isto quer dizer e quiser uma
explicação totalmente formal, lá vai: seja $B_2 = \sst{P'}{P_1 J P'}$,
seja $B_3 = \sst{P''}{P' \in B_2 \text{ e } P'JP''}$, $B_4 =
\sst{P'''}{P'' \in B_3 \text{ e } P''JP'''}$, etc; seja $B = \sof{P_1}
\cup B_2 \cup B_3 \cup \ldots$; este conjunto $B$ é o conjunto de
``todas as posições possíveis a partir de $P_1$''.

\msk

e) A relação $J \subseteq A×A$ que você definiu no item (c) tem um
número enorme de pares, e seria quase impossível representá-la
graficamente. Vamos definir uma relação $K \subseteq B×B$ sobre o
conjunto $B$ que você definiu no item (d), por:
%
$$PKP' \text { se e só se } P,P'İB \text{ e } PJP'$$

Ou seja, se $PKP'$ é verdade então é possível ir de $P$ para $P'$ em
uma jogada, e tanto $P$ quanto $P'$ são posições a que podemos chegar
a partir da posição $P_1$ definida no item (a). {\sl Represente a
relação $K$ graficamente, como um grafo direcionado} --- desenhe todos
os elementos de $B$ numa folha de papel e use setas para indicar os
pares relacionados.

\msk

f) Escolhe dois elementos da relação $K$ que você definiu no item
anterior e represente-os ``em matematiquês''.

\msk

g) A relação $K$ é uma função? E a relação $K^{-1}$? Sim, não, porquê?
Se alguma delas for uma função diga qual o seu domínio e a sua imagem.

\bsk
\bsk


\noindent {\bf (2)} (Total: 5.0 pontos). Considere a seqüência $(a_0,
a_1, a_2, \ldots)$, definida pelas regras $a_0 = 1$, $a_{n+1} = 4a_n$,
e a seqüência $(b_0, b_1, b_2, \ldots)$, definida pelas regras $b_0 =
1$, $b_{n+1} = 5a_n$. Prove {\sl formalmente, por indução,} que
%
$$ınİ\N.\;a_n \le b_n.$$

\bsk
\bsk
\bsk
\bsk
\bsk
\bsk


A prova é para ser feita em duas horas, sem consulta.

Responda claramente e justifique cada passo.

Lembre que a correção irá julgar o que você escreveu, e

que é impossível ler o que você pensou mas não escreveu.

Lembre que a resposta esperada para cada questão não é só

uma fórmula ou um número --- a ``resposta certa'' é um

raciocínio claro e convincente, com todos os detalhes

necessários, mostrando que você sabe traduzir corretamente

entre as várias linguagens (português, diagramas,

matematiquês, etc) e explicando o que você está fazendo

quando for preciso.

Outra dica: {\sl confira as suas respostas!}

\ssk

{\bf Boa prova!}


% \end{document}

\newpage

Gabarito:

%D diagram velha
%D 2Dx     100       +65        +65         +65       +65
%D 2D  100 \pum ---> \pdois
%D 2D
%D 2D  +40           \ptres -> \pquatro -> \pc inco
%D 2D
%D 2D  +40                     \pseis      \pcinco
%D 2D
%D 2D  +40           \psete -> \poito
%D 2D
%D 2D  +40 \pzero              \pnove ---> \pdez
%D 2D
%D (( \pzero \pum -> \pum \pdois ->
%D    \pum \ptres -> \ptres \pquatro ->  \pquatro \pcinco ->
%D                     \ptres \pseis ->
%D    \pum \psete -> \psete \poito -> \poito \pcinco ->
%D                   \psete \pnove -> \pnove \pdez ->
%D ))
%D enddiagram
%D
$$\diag{velha}$$






% (find-LATEX "2009-2-C4-prova-1.tex")



%*

\end{document}

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