\documentclass[twoside]{article}
\usepackage{amssymb,amsfonts,amssymb,amsthm}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\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{at}{Atividade}
\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 hex - conexões extremas em ladrilhos hexagonais}
%\vskip -0.5truecm
\author{\sc Izabelly Marya Lucena da Silva\,\thanks{Universidade Federal de Pernambuco,\,
UFPE, PE, Brasil,\, izabellymarya@ig.com.br} \,\,\,\,\&\,\,\,\, Gésica Peixoto Campos
\,\thanks{Universidade Federal de Pernambuco,\, UFPE, PE, Brasil,\, gesica.pcampo@bol.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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%

\textbf{Resumo:}
 O Hex é um jogo de profunda sutileza. Inicialmente inventado pelo matemático, físico e poeta dinamarquês Piet Hein em 1942. Depois em 1948 o matemático John Nash quando se preparava para o seu doutorado inventa o mesmo jogo sem saber e nem ter contato com a invenção de Piet Hein.
O jogo consiste em fazer conexões ao longo do tabuleiro feito de hexágonos, a fim de construir um caminho contínuo que ligue dois extremos do tabuleiro com peças do mesmo jogador.O jogo é jogado com dois oponentes e quem conseguir construir o caminho primeiro é o ganhador.
Este minicurso busca: estudar e explicar estratégias vencedoras para garantir a vitória no hex para o primeiro jogador e em certas situações para o segundo também, formas diferentes de se jogar o hex, regras para tornar o jogo justo, teoremas e demonstrações e também tabuleiros equivalentes com verificação da equivalência.

\textbf{Palavras-chave:} Conexões; ligação; tabuleiro; equivalência e hexágonos.

\section{Histórico}
Inventado por Piet Hein, matemático, físico e poeta dinamarquês, o jogo apareceu pela primeira vez no jornal diário "Polytiken" de 26 de Dezembro de 1942, com o nome de "Polígono" em plena Segunda Guerra Mundial. Nesta época, o jogo adquiriu grande popularidade na Dinamarca, sendo que eram vendidos impressos para se jogar Hex, com lápis (da mesma forma que se faz atualmente com batalha naval).

Jornais publicavam problemas sobre Hex, como se publica hoje problemas de xadrez. O próprio Piet teve uma vida interessante: durante a invasão alemã, iniciada em 1940, durante a 2ª Guerra, ele fez parte do movimento de resistência da Dinamarca. O jogo hex ocorreu a Piet quando cismava sobre o teorema das quatro cores da topologia (afirma que quatro cores são suficientes para colorir qualquer mapa sem que haja dois países vizinhos com a mesma cor).

Em 1948, o matemático John Nash, enquanto preparava o seu doutoramento em Princeton, e sem ter conhecimento da invenção de Piet Hein, inventou de novo o jogo. Recorde-se que Jonh Nash veio a receber o prêmio Nobel de Economia pelos seus trabalhos sobre as melhores estratégias de sucesso (ver referências Fernandes).

Uma história conta que o jogo teria sido inventado, desenvolvido e jogado, no interior de um banheiro, cujo piso era formado de ladrilhos hexagonais. Com o tempo, o jogo ganhou algumas variantes, como aquele em que as "casas" não são hexagonais, mas triangulares ou retangulares. Contudo, foi Martin Gardner, nas páginas do Scientific American, que o popularizou nos anos 50. Hoje o Hex está a tornar-se cada vez mais popular, sendo muito estudado.

\section{Conceitos do HEX}
	O Hex é um jogo de conexão, seu tabuleiro tem formato semelhante ao de um losango e é formado por hexágonos interligados. O tabuleiro utilizado habitualmente tem 11 por 11 hexágonos, mas podem ser utilizados tabuleiros de menores ou maiores dimensões. Cada um dos jogadores possui dois lados opostos do tabuleiro. Cada jogador tem um determinado número de fichas, normalmente 60, sendo que um deles jogará com as azuis e outro com as vermelhas.

	Determinam-se quem joga em primeiro lugar procedendo, por exemplo, ao lançamento de uma moeda ao ar. Depois os jogadores, alternadamente, vão colocando as suas fichas nos hexágonos livres do tabuleiro. Ganha aquele que primeiro conseguir formar um caminho de fichas próprias que una os seus dois lados opostos, isto é, um caminho vermelho que una as duas margens vermelhas ou um caminho azul que una as duas margens azuis.

	Para contrariar a vantagem (pelo menos teórica) do primeiro jogador, há quem admita uma regra opcional para que o jogo seja justo para os 2º jogadores. Senão, o 1º jogador sempre teria vantagem, pois escolheria a peça do meio. Quando efetua o movimento de abertura, o segundo jogador pode optar por trocar a ficha do adversário por uma das suas em vez de ocupar uma das "casas" vazias. Assim, ao efetuar a abertura do jogo o primeiro jogador terá que considerar a hipótese da sua peça ser substituída por uma do adversário. Terá que avaliar se deve colocar a sua primeira peça na posição que considera ótima correndo o risco de vê-la substituída, ou se deve optar por colocar a sua primeira peça noutra posição menos vantajosa vendo o adversário ocupar a melhor posição, mas ficando com a sua peça no tabuleiro.

	Neste jogo não há capturas, preenchendo-se seqüencialmente o tabuleiro com peças. O jogo nunca termina sem vencedores, pois só é possível bloquear o jogo do adversário completando a própria corrente. Iremos analisar estratégias vencedoras baseadas na colocação das peças de forma a obter vantagem e garantir a vitória no hex.

\section{Definições do HEX}
\begin{itemize}
\item Adjacência - duas peças dizem-se adjacentes se os hexágonos que ocupam partilham uma aresta.
\item N-ésima vizinhança - é dada, neste caso, pelo n-ésimo hexágono que circunda a peça. (Figura~\ref{fig1}).
\item Distância - a distância entre uma peça e outra (ou uma margem) é dada pela identificação da ordem da vizinhança em que está esta outra peça (ou margem) em relação a primeira
\item Grupo - um conjunto de peças adjacentes da mesma cor.
\end{itemize}

%FIGURA 1

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.45]{figura1.eps}
\end{center}
\caption[Hex.]{Hex. Neste exemplo, o
tabuleiro tem ``tamanho $5\times5$, os números 1 e 2 representam a ordem da vizinhança que se encontra ''.}
\label{fig1}
\end{figure}

\section{Estudando a Estratégia do Hex}


Uma das melhores sutilezas do hex é jogá-lo num tabuleiro com pequeno número de  hexágonos. Convencionaremos as jogadas do primeiro jogador horizontalmente no sentido  leste$-$oeste e oeste$-$leste e nossos tabuleiros serão do tipo m $×$ n, m linhas e n colunas  e com m = n. Estudaremos a estratégia partindo das jogadas do primeiro jogador. E sem  utilizar a Regra do Equilíbrio.

\section{Atividades Sugeridas}

\begin{at}
 Quais das casas hexagonais abaixo garantem a vitória no hex para o primeiro jogador, no tabuleiro  $2\times2$  (ver Figura~\ref{fig2})?
\end{at}

%FIGURA 2
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{figura2.eps}
\end{center}
\caption[Hex.]{Hex. Neste exemplo, o
tabuleiro tem ``tamanho $2\times2$ ''.}
\label{fig2}
\end{figure}
\begin{at}
 Agora vamos fazer a mesma atividade para tabuleiro 3$×$3 (ver Figura~\ref{fig3}):
Utilizando os mesmo raciocínios anteriores, vamos analisar agora tabuleiros maiores. O jogo a partir daqui começa a ficar mais elaborado e requer mais atenção para as jogadas.
\end{at}

\begin{at}
 No tabuleiro 4 $×$ 4 abaixo (ver Figura~\ref{fig4}), inicialmente partindo da casa 1, com quantas jogadas garantirá a vitória no hex$?$ E na casa 2$?$ E na casa 3$?$ E finalmente na casa 4$?$ Tente imaginar as jogadas contra do adversário, pense que o mesmo também vai querer ganhar e jogará da melhor forma possível.
\end{at}


% FIGURA 3 E
% FIGURA 4 UMA DO LADO DA OUTRA
\begin{figure}[h]
       \begin{minipage}[b]{0.48 \linewidth}
\centering
           \includegraphics[scale=0.48]{figura3.eps}\\
           \caption[Hex.]{\it Hex. Neste exemplo, o
tabuleiro tem\\ tamanho $3\times3$.}
           \label{fig3}
       \end{minipage}
       \begin{minipage}[b]{0.48 \linewidth}
\centering
           \includegraphics[scale=0.35]{figura4.eps}\\
           \caption[Hex.]{\it Hex. Neste exemplo, o
tabuleiro tem ``tamanho $4\times4$, numerada apenas a diagonal principal para análise ''. }
           \label{fig4}
       \end{minipage}
   \end{figure}
\begin{at}
 E se a jogada inicial não fosse em nenhuma das casa numeradas, com quantas jogadas seria possível garantir a vitória.
\end{at}

\section{Pontes}

Uma das estratégias utilizadas numa partida de Hex é a formação de Pontes, pois para unir os dois lados opostos, realizar movimentos adjacentes não é a melhor opção. Cria$-$se uma ponte quando um par de peças (do mesmo jogador) ocupa casas não adjacentes, estando estas a duas unidades de distância. Perante esta situação, o jogador das peças pretas tem sempre dois caminhos possíveis que ligam estas duas peças pretas, o que se torna muito vantajoso. Sempre que uma peça branca ocupe uma destas duas casas a tracejado, o jogador das peças pretas pode sempre realizar uma jogada na outra, estabelecendo dessa forma a ligação. É por esta razão que os jogadores tentam construir várias pontes ao longo do tabuleiro. Quanto mais próximo do centro, realizarem as suas primeiras jogadas, mais fáceis se torna a formação de pontes.

Podemos verificar a ocorrência dessas pontes nas atividades realizadas anteriormente. Por exemplo, no tabuleiro 2 $×$ 2 (ver Figura~\ref{fig1}), as únicas casas que garantem a vitória são aquelas que formam as pontes diretamente com as margens leste?oeste e oeste $?$ leste, ou seja, as casas com as letras B e C.

%FIGURA 5
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{figura5.eps}
\end{center}
\caption[Hex.]{Hex. Neste exemplo, o
tabuleiro tem ``tamanho padrão $11\times11$, analisamos aqui a estratégia de pontes ''.}
\label{fig5}
\end{figure}
\pagebreak
 \begin{at}
 Analisando o tabuleiro de 5 $×$ 5 ( ver Figura~\ref{fig6}) e utilizando a estratégia de pontes. Com quantas jogadas o primeiro jogador ganhará se ele partir da casa central do tabuleiro?
\end{at}
%FIGURA 6
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.35]{figura6.eps}
\end{center}
\caption[Hex.]{Hex. Neste exemplo, o
tabuleiro tem ``tamanho $5\times5$, e analisamos a jogada partindo da casa central ''.}
\label{fig6}
\end{figure}
No HEX o número de jogadas é finito e haverá sempre um vencedor, nunca terminando o jogo empatado (David Gale). Também se pode demonstrar que, se jogasse de forma ótima, o primeiro jogador ganharia sempre. O problema está em descobrir a estratégia que o conduzirá à vitória.
O tabuleiro 7 $×$ 7 é o maior tabuleiro para o qual se conhece a estratégia que dá a vitória ao primeiro jogador. Num tabuleiro maior o primeiro jogador sabe que, em teoria, deveria ganhar, mas não sabe como. No entanto existem algumas estratégias que aumentam a probabilidade de um jogador ganhar, que é a formação das pontes, explicado anteriormente.


\begin{at}
Demonstre.
\end{at}
\begin{myth}
Nenhum jogo do hex pode terminar em empate.
\end{myth}

\begin{at}
Demonstre.
\end{at}
\begin{myth}
O jogo do hex pode ser sempre ganho pelo primeiro jogador. (Demonstração baseada na de John Nash).

\end{myth}

\begin{myth}

Os cantos agudos de um tabuleiro são aberturas perdedoras. (Demonstração por %Beck):


\end{myth}

\paragraph{Demonstração:}%{\it Existência -}

Se o jogador das peças azuis colocar a primeira peça na posição a1, então o jogador das peças vermelhas responderá colocando uma peça vermelha em a2. Esta jogada remove quase por completo a peça azul do jogo.
Seja o conjunto de casas vazias adjacentes à peça azul {X}, logo para voltar a utilizar esta peça azul, colocada em a1, o jogador terá que usar a casa X, para  estabelecer uma união. No exemplo anterior, a única casa adjacente à peça azul colocada em a1 é b2. No entanto, esta ligação não é favorável, na medida em que ligará as peças azuis ao seu próprio lado. Isto é, qualquer das peças neste lado do tabuleiro poderia ser a segunda jogada com o mesmo efeito de b1 para alcançar o objetivo; a1 se torna uma jogada dispensável. Esta situação pode proporcionar a vitória das peças vermelhas.
Podemos concluir, que esta estratégia é perdedora, porque um movimento de abertura num dos cantos agudos do tabuleiro pode conduzir o segundo jogador à vitória.



\section{Estratégia do Reflexo}

A estratégia do reflexo para tabuleiros n $×$ (n$+$1), é feita ao longo do eixo central, e dar ao segundo jogador a vitória certa. Qualquer que seja o jogo do adversário, o parceiro joga na outra casa que foi refletida. Vamos exemplificar no tabuleiro abaixo como essas reflexões ocorrem, as dimensões utilizadas serão 6 $×$ 7 (ver Figura 7.1). Imagine-se que associamos as casas de acordo com o diagrama.

%FIGURA 7
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{figura7.eps}
\end{center}
\caption[Hex.]{Hex. Neste exemplo, o
tabuleiro tem ``tamanho $6\times7$, analisamos aqui as jogadas num tabuleiro assimétrico ''.}
\label{fig7}
\end{figure}
Como a distância dele aos dois lados do tabuleiro é menor, ele não poderá perder.


\section{Campos Equivalentes para o Jogo do Hex}

Observe as figuras abaixo:

%FIGURA 8
%FIGURA 9
%FIGURA 10 UMA DO LADO DA OUTRA

\begin{figure}[h]
       \begin{minipage}[b]{0.48 \linewidth}
           \includegraphics[scale=0.6]{figura8.eps}\\
           \caption[Hex.]{\it Hex. Neste exemplo, o
tabuleiro\\ tem ``tamanho $3\times3$ ''.}
           \label{fig8}
       \end{minipage}
       \begin{minipage}[b]{0.48 \linewidth}
           \includegraphics[scale=0.5]{figura9.eps}\\
           \caption[Hex.]{\it Hex. Neste exemplo, o
tabuleiro tem ``tamanho $3\times3$ e a contrução do equivalente está sobreposto ao mesmo ''.}
           \label{fig9}
       \end{minipage}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{figura10.eps}
\end{center}
\caption[[Hex.]{Hex. Tabuleiro Equivalente ''.}
\label{fig10}
\end{figure}

Dado o tabuleiro de hex mais comum, ou seja, o de casas hexagonais (ver Figura~\ref{fig8}), podemos obter um tabuleiro equivalente a esse da seguinte maneira: Colocando em cada uma das casas hexagonais um vértice, representado por um círculo e a cada dois vértices pertencentes a casas hexagonais adjacentes ligarmos com uma aresta, (ver Figura~\ref{fig9}), obteremos o seguinte tabuleiro de triângulos da figura~\ref{fig10} que joga o mesmo jogo de hex.


Podemos fazer a seguinte comparação por caminhos. Isolando do tabuleiro de casas hexagonais, um dos hexágonos que tenha todas as adjacências, podemos perceber que jogando nessa casa, o caminho poderá ser feito de 6 formas diferentes visto que hexágono é uma figura plana, regular com 6 lados. Se jogarmos no tabuleiro de triângulos da Figura 8.1c, iremos jogar nos vértices dos triângulos e as ligações serão feitas por meio das arestas do triângulo, fazendo a mesma observação no vértice central da Figura 8.1c, percebemos que 6 arestas partem dele para vértices adjacentes. Logo o caminho poderá ser feito de 6 formas diferentes também, assim como no tabuleiro de hexágonos da Figura 8.1a. Logo os dois tabuleiros são equivalentes.
O tabuleiro equivalente de Nash é dessa maneira, feito de triângulos e a jogabilidade é a mesma do tabuleiro de hexágonos como podemos analisar acima. Um jogador liga N$-$S, colocando peças da sua cor nas intersecções, o outro tenta a ligação E$-$O.


%FIGURA 11
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.25]{figura11.eps}
\end{center}
\caption[[Hex.]{Hex. Tabuleiro Equivalente de John Nash , o
tabuleiro tem ``tamanho Padrão $11\times 11$ ''.}
\label{fig11}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% REFERÊNCIAS
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Referências}
\setcounter{equation}{0}
\noindent[1] {\sc emília,  helena} -
  {\it O Jogo do Hex.}, $31$ out $2007$. Disponível em $<$http://wwwdescobertamat.blogspot.com/2007/ 10/jogo-do-hex.html$>$. Acesso em $20$ mar $2010$.

\noindent[2] {\sc fernandes, josé a. s.} -
{\it Hex Ludos - Regras}, Disponível em $<$http://agpico.edu.pt/index.php?option$=$com\underline{\ \ } content\&view$=$article\&id$=131:$ hex-ludos-regras\&catid$=19$:plano-da-matematica\&Itemid$=33>$. Acesso em: $20$ mar $2010$.

\noindent[3] {\sc hein, piet; nash, john} -
{\it Hex - Regras do jogo.}, O Janeirinho, p.8-9. Nov 2005. Disponível em $<$http://ludicum.
org/events/04janh08\underline{\ \ }09-1.pdf$>$ Acesso em $15$ fev $2010.$

\noindent[4] {\sc santos, carlos p. dos} -
{\it Análise de um problema de hex}. Disponível em $<$http://ludicum.org/games/abstr/hex1 /Hex.doc/view?searchterm=hex$>$. Acesso em $20$ mar $2010$.





\end{document} 
