\documentclass{article}

\usepackage[latin1]{inputenc}
\usepackage[portuguese]{babel}

\title{\begin{tabular}{c}
         Trabalho Prático \\
         AEDS 1}
         

\date{15 de Maio de 2006}

\author{Carlos Camarão}

\begin{document}

Faça um programa para jogar {\em Nim\/}. O computador deve ser um
jogador e o usuário do programa o adversário.

O jogo inicia-se com uma seqüência de $n$ {\em linhas\/}, na qual toda
linha tem uma seqüência com um determinado número de símbolos {\tt *}
(qual símbolo específico é usado não tem importância nenhuma). A
primeira linha tem apenas um {\tt *}, a segunda 2 símbolos {\tt *}
etc., até a $n$-ésima linha, que tem $n$ símbolos {\tt *}.

Cada jogador, na sua vez, tira um determinado número $k$ de símbolos
{\tt *} de uma única linha com $m$ símbolos, deixando-a com $m-k$
símbolos (onde $k\leq m$). O jogador que tirar o último {\tt *} perde
o jogo.

O valor $n$ e quem começa o jogo devem ser especificados como entradas
para o programa. 

O programa deve perguntar a jogada do usuário e, para cada jogada,
deve mostrar a configuração anterior à jogada (a não ser na primeira
jogada, quando não existe configuração anterior), a jogada que foi
feita e a configuração após a jogada.

O programa deve usar a seguinte estratégia, que é ótima (ou seja: é
uma estratégia que sempre vence quando é possível vencer).

O ponto-chave da estratégia está no uso da soma binária dos números de
símbolos {\tt *} em cada linha, desprezando todos os {\em
vai-um}. Essa operação é chamada também de {\em ou-exclusivo\/}. Vamos
denotá-la por $\oplus$ e escrever $a \oplus b$ para a soma binária de
$a$ e $b$. 

Por exemplo, para uma configuração com 3 linhas ($a$,$b$,$c$) e,
respectivamente, 3, 4 e 5 símbolos {\tt *} em cada uma, temos:

        \[ \begin{array}{ccc}
             \textrm{Binário} & \textrm{Decimal} & \textrm{Linha} \\
               11    &   3     &  a    \\
              100    &   4     &  b    \\
              101    &   5     &  c    
           \end{array}
        \]

A soma binária $3 \oplus 4 \oplus 5$ é igual a $2$ ($10$ em binário).

A estratégia ótima consiste em deixar a soma binária igual a zero, o
que é possível se e somente se a soma binária não é igual a zero antes
da jogada. 

Se a soma binária for igual a zero, então o jogador que irá realizar a
jogada perderá se o outro jogador não cometer um erro.

Para decidir qual jogada deve ser realizada, faça o seguinte: seja $x$
a soma binária de todos os $k_i$, $i=1,\ldots,n$, onde $k_i$ é o
número de símbolos {\tt *} na linha $i$. Tome a soma binária de $x$
com cada $k_i$ e ache uma linha $j$ na qual essa soma binária decresce
(i.e.~seja menor que $x$). A jogada ótima retira símbolos {\tt *}
desta linha. O número de símbolos a ser retirado é tal que a soma
binária dos $k_i$ seja igual a zero ($i=1,\ldots, n$).

No exemplo acima, temos: 

 \[  \begin{array}{llll}
        3 \oplus 2 & = 11_2  \oplus 10_2 & = 10_2  & = 2 \\
        4 \oplus 2 & = 100_2 \oplus 10_2 & = 110_2 & = 6 \\
        5 \oplus 2 & = 101_2 \oplus 10_2 & = 111_2 & = 7 
     \end{array}
 \]

Portanto, a jogada ótima retira dois {\tt *}s da linha $a$.

\end{document}




