Sam Slovic::...
Existem 9! (Nota do Sr. Slovic: Isso é um nove fatorial, ou seja 9x8x7x6x5x4x3x2, ou 362.880) combinações do X e O no tabuleiro. Pensando só na vencedoras, o número de possibilidades cai somente para 255.168!!!! (desta vez, não fatorial).
...
Apenas uma correção rápida, 9 fatorial vc esta desconsiderando diversas combinações que são repetições uma da outra, apenas rotacionada ou espelhada.
Para essa situação temos o seguinte.
9 casas a serem preenchidas, sendo 5 "X" e 4 "O" (ou vice-versa). Alinhando as casas numa única fileira fica:
_ _ _ _ _ _ _ _ _ Um exemplo de preenchimento seria X O X O X O X O X (Esse jogo teria acabado antes do preenchimento total, pois o X venceria, mas vamos relevar isso para fins de cálculo).
Dessa forma nós temos uma permuta com repetição, o número de combinações possíveis seria:
9!/(4!5!) = 126
Essa conta pode ser encontrada melhor explicada e validada em (
http://clubes.obmep.org.br/blog/11865-2/)
Nessa abordagem são desconsideradas as partidas que encerram com menos de 9 jogadas.
Esse valor de 9! é considerando o número de partidas únicas possíveis, desconsiderando espelhamentos, reflexões e partidas que se encerrariam por um dos jogadores já ter vencido antes da 9ª jogada.
Vamos tentar chegar num número mais realista:
_/_/_ 1 2 3
_/_/_ --> 4 5 6
_/_/_ 7 8 9
Utilizando a notação acima nós temos um número para cada espaço.
Notem que começar o jogo nos espaços 1, 3, 7 e 9 é a mesma coisa (apenas rotacionando o tabuleiro). Os espaços 2, 4, 6 e 8 também. E o 5 é a ultima possibilidade. Logo para a primeira jogada, temos 3 possibilidades (e não 9, como no caso do 9!).
Para cada uma das aberturas possíveis você tem:
- Começando em 1, 3, 7 ou 9 temos mais 5 possibilidades (e não 8) pois jogar em 2 ou 4 é a mesma situação, assim como 3 ou 7 e 6 ou 8. O 5 e o 9 são uma possibilidade cada.
- Começando em 2, 4, 6 ou 8 temos novamente 5 possibilidades. Os pares de posições equivalentes são: 1 e 3, 4 e 6, 7 e 9. 5 e 8 são jogadas únicas.
- Começando em 5 temos apenas 2 possibilidades, pois nesse caso 1, 3, 7 e 9 são equivalentes, assim como 2, 4, 6 e 8.
Nesse ponto nós já fizemos 2 jogadas e tivemos apenas 12 possibilidades (3 aberturas, levando a 12 segundas jogadas) contra as 9*8=72 jogadas da opção 9!.
A partir desse momento a analise fica longa demais para dar seguimento, mas ainda assim o número de possibilidades vai cada vez mais afunilando.
Observando o problema por outro ponto de vista podemos pensar que cada um dos 9 espaços tem 3 possibilidades (X, O ou em branco) o número de estados de jogo seria 3ˆ9 = 19683. Mas dessa forma temos partidas inacabadas (mais de 4 espaços em branco, ja que só se pode ganhar após o 5º movimento) e partidas invalidas(com desequilíbrio de X e O, já que não é possível ter 2 X e 4 O por exemplo).
Uma outra forma de se pensar é que em partidas jogadas certo existem apenas 3 arranjos finais de empate. Existem apenas 3 possibilidades de partidas, e diversas rotações e espelhamentos destas.*
Enfim, apenas queria mostrar que o número de 9! de possibilidades para jogo da velha é uma abordagem excessivamente simplista em sua análise, que infla o número de possibilidades de partidas para valores imensos. Tendo na verdade muito menos possibilidades de jogo.
*Para quem dúvida, tentem encontrar um empate que não seja espelhamento ou rotação de uma destas partidas:
X/O/X
X/O/O
O/X/X
O/X/O
O/O/X
X/O/X
O/X/O
X/O/X
X/O/X
