Manobras com baldes

Propuseram-me recentemente este conhecido problema:

dados três baldes, um cheio com oito litros de água, e dois vazios, um com cinco litros e outro com três litros de capacidade, todos sem graduação, descobrir a forma de passar quatro litros de água do primeiro para o segundo balde, com o número mínimo de movimentos:

Não gosto de métodos empíricos, pelo que explorei a hipótese de transformar este problema num problema de determinação do caminho mínimo entre dois vértices de um grafo. Um grafo tem vértices e arestas. Os vértices seriam os estados inicial, intermédios e final, e as arestas indicariam ser possível transitar de um para outro estado com um movimento.

Primeira questão, de quantas formas será possível distribuir os 8 litros de água pelos três baldes, necessariamente um número inteiro de litros em cada balde. Bem, seria possível usar aqui a regra dos separadores para este cálculo, mas a resposta está à distância de um pequeno programa de computador:

São 24! Faltando saber se são todos estados possíveis dentro das regras definidas.

Em cada estado há no máximo 6 movimentos possíveis, do balde 1 para os baldes 2 ou 3, do balde 2 para os baldes 1 ou 3, e do balde 3 para os baldes 1 ou 2, desde que o balde de partida tenha água, e o movimento pode consistir em despejar a água toda ou em encher o balde de destino, não havendo situações intermédias, uma vez que os baldes não têm graduações.

Quantas arestas terá este grafo? Outro pequeno programa de computador ajuda a descobrir que são 106:

e o problema estará resolvido!

O próximo passo é visualizar este grafo (direccionado, digrafo). Utilizei Gephi:

Curiosamente, há 8 vértices inatingíveis (bons para problemas impossíveis...). Retirando-os, e pedindo ao Gephi que mostre, se houver, o caminho mais curto entre os vértices [8, 0, 0] e [4, 4, 0], chegamos a uma solução com comprimento 7 (ramo superior):

Há também uma solução óbvia com comprimento 8 (ramo inferior) e mais um conjunto de soluções de maior comprimento, passando todas pelo vértice [0, 5, 3].

Mais passeios aleatórios

Na última publicação, analisamos um problema de passeios aleatórios, que podemos traduzir nesta figura

Distância ao nó 6 (passeio aleatório)

em que temos um grafo com 6 nós e as distâncias que um viajante aleatório colocado num dos outros nós teria de percorrer em média para chegar ao nó 6.

Estes números costumam causar um certo desconforto, por chocarem com a nossa intuição, mas não deixam de ser verdade...

E se os seis nós estivessem em linha? As equações seriam

6 nós em linha

T5 = [1 + (1 + T4)] / 2

T4 = [(1 + T5) + (1 + T3)] / 2

T3 = [(1 + T4) + (1 + T2)] / 2

T2 = [(1 + T3) + (1 + T1)] / 2

T1 = 1 + T2

e eliminado sucessivamente T1, T2, T3 e T4

T2 = [(1 + T3) + (1 + 1 + T2)] / 2

T2 = 3 + T3

T3 = [(1 + T4) + (1 + 3 + T3)] / 2

T3 = 5 + T4

T4 = [(1 + T5) + (1 + 5 + T4)] / 2

T4 = 7 + T5

T5 = [1 + (1 + 7 + T5)] / 2

T5 = 9

e daqui que todas as distâncias que teriam de ser percorridas em média por um viajante colocado num nó de partida qualquer para chegar ao nó 6 serão as indicadas na figura a seguir

Distância ao nó 6 (passeio aleatório)

E se tivermos uma fila com N nós? Que distância teria de percorrer em média um viajante aleatório para vencer essa distância? Será (N - 1)^2?

Outra questão diferente será saber quantas vezes o viajante passou por cada nó, em média. No layout de um museu, ou de um espaço comercial, onde as pessoas se movam com alguma aleatoriedade, esse valor pode ser uma medida da qualidade da sua localização.

Fica o desafio.

Passeios aleatórios

Este problema pode ser apresentado sob as mais diversas formas.

Imaginemos um edifício com seis salas, e que um visitante, que está na sala 1, se move aleatoriamente entre as salas, com a probabilidade de escolher uma porta igual para todas as portas da sala.

Organização das salas

A questão é quantos movimentos terá de fazer, em média, o visitante até chegar à sala 6?

Ou poderia ser, quantos movimentos terá de fazer, em média, antes de visitar todas as salas?

Também podemos olhar para este problema, por exemplo, como um grafo

Grafo equivalente

e utilizar conceitos de teoria dos grafos.

E pensar que os nós poderiam ser páginas na Web e as ligações poderiam ser os links entre elas, e o problema ser qual é a página mais visitada por um viajante aleatório na Web.

Estes processos em que o caminhante decide aleatoriamente cada movimento não têm memória, cada decisão é independente do histórico anterior, é uma cadeia de Markov.

Quando está no nó 5, por exemplo, o caminhante tem duas alternativas igualmente prováveis, ir para o nó 6 e terminar ou então regressar ao nó 2, a partir do qual terá de realizar T2 movimentos para chegar ao nó 6. Assim, em média, para ir de 5 a 6 precisamos dos seguintes movimentos

T5 = [1 + (1 + T2)] / 2 

Da mesma maneira, podemos dizer que 

T2 = [(1 + T1) + (1 + T3) + (1 + T5)] / 3

T3 = 1 + T2

T1 = [(1 + T2) + (1 + T4)] / 2

T4 = 1 + T1.

Isto agora é álgebra, resolução de sistemas, em que estamos interessados apenas em T1.

Eliminando T4 na penúltima equação, ficamos com um equação em T1 e T2

T1 = [(1 + T2) + (2 + T1)] / 2.

Eliminando T3 na segunda equação, ficamos com

T2 = [(1 + T1) + (2 + T2) + (1 + T5) ] / 3.

Eliminando T5 nesta, ficamos com uma segunda equação em T1 e T2

T2 = [(1 + T1) + (2 + T2) + (1 + [1 + (1 + T2)] / 2)] / 3.

Da primeira destas duas equações retiramos

2T1 = 1 + T2 + 2 + T1

T2 = T1 - 3

e substituindo na última

6T1 - 18 = 2 + 2T1 + 4 + 2T1 - 6 + 2 + 1 + 1 + T1 - 3

T1 = 19.

Em média, são necessários 19 movimentos, um número talvez surpreendentemente elevado!...

Fizemos uma simulação de 1 milhão de passeios aleatórios, usando um programa de computador muito simples, que confirmou estes resultados: média 19 e moda 5.

Fica aqui o gráfico da distribuição dos comprimentos desse milhão de percursos, todos evidentemente de comprimento ímpar...

Histograma da distribuição de comprimentos

E assim se conjugam alguns saberes para se encontrar a solução de um problema aparentemente simples mas muito desafiante, e que permite encontrar outros, e novos, desafios...

A ciência das matrizes III

(exclusivamente para não Matemáticos...)
Esta publicação está no seguimento de outra, em que olhamos para os conceitos de matriz identidade e matriz inversa, e revisitamos a regra de multiplicação de matrizes.
Uma matriz é um instrumento perfeito para representar uma relação entre dois conjuntos, por exemplo a relação 'gosto' entre um conjunto de pessoas P e um conjunto de clubes C, aqui representada por esta matriz G,

ou a relação 'fica em' entre em conjunto de clubes C e um conjunto de cidades D, aqui reprsentada pela matriz F,

E o que acontece se multiplicarmos estas duas matrizes? Primeira questão: pode-se? Há aquela regra de o número de colunas da primeira ser igual ao número de linhas da segunda, o que quer dizer que G.F existe, mas F.G, não!

A matriz resultado G.F é uma relação entre pessoas e cidades: 'gosto de n clubes que ficam em'. O Bruno gosta de dois clubes que ficam em Lisboa.
A multiplicação das matrizes conduziu à relação composta F depois de G.

A ciência das matrizes II

(exclusivamente para não Matemáticos...)
Na publicação anterior, vimos como um sistema de três equações a três incógnitas pode ser escrito como uma equação baseada num produto de matrizes A.x = b

Dois conceitos que ajudam a explorar esta situação são o de matriz identidade ou matriz unitária, uma matriz que tem a propriedade de poder ser multiplicada por outra sem a alterar, e o de matriz inversa, uma matriz que multiplicada pela matriz original conduz à matriz identidade.
A matriz identidade terá de ser necessariamente quadrada, tendo em conta a regra da multiplicação, e todos os seus elementos na diagonal principal devem valer 1 e os restantes 0:

Como obter a matriz inversa de uma matriz quadrada fica para depois. Por enquanto, podemos usar uma folha de cálculo para o fazer ...
Uma vez obtida a matriz inversa da matriz A anterior (com um factor em evidência para se trabalhar com inteiros), e verificado que multiplicando-as se obtem a matriz identidade

multiplicando ambos os lados da equação pela matrix inversa

e fazendo as contas

 encontra-se a solução do sistema

Pareceu fácil, mas nem sempre é possível obter a matriz inversa.
Curiosamente, hoje são muito importantes as situações em que não há matriz inversa...

A ciência das matrizes I

(exclusivamente para não Matemáticos...)
As matrizes (bidimensionais) são estruturas numéricas rectangulares que passamos a vida a encontrar nos capítulos mais diversos dos nossos interesses matemáticos.
Uma fotografia digital a preto e branco é uma matriz, cujos elementos são os valores dos respectivos pixeis da ,imagem

A esta imagem com 11x7 linhas corresponde uma matriz com dimensão 11x7:

Podem realizar-se operações com as matrizes. Duas importantes são a transposição, que corresponde a trocar a posição das linhas pela das colunas:

e a multiplicação, bem conhecida dos iniciados, que se faz multiplicando termo a termo a linha i da primeira matriz pela coluna j da segunda, somando as parcelas, e colocando o resultado na posição (i, j) da matriz resultado:

A multiplicação de matrizes permite representar de forma simples sistemas de n equações a n incógnitas. Este é um sistema de 3 equações a 3 incógnitas:

Mas será que isto nos ajuda a resolver este sistema de equações?
Lá chegaremos, mas por agora pensemos que uma matriz pode representar os negócios cruzados entre um conjunto de países, ou as adjacências de um grafo, ou uma cadeia de Markov, ou as ligações entre páginas Web, e que compreender estas estruturas matemáticas pode abrir novas formas de olhar para estes ou outros fenómenos.

Somados somos um quadrado perfeito!

A relação binária "somados somos um quadrado perfeito" no universo dos inteiros {1, 2, ..., 25} é muito interessante, por o grafo correspondente ter um único componente conexo e admitir caminhos Hamiltonianos, caminhos que visitam cada um dos nós do grafo exactamente uma vez.
Uma das minhas ferramentas favoritas, NodeXL, permite investigar estes factos muito facilmente.
Ja vimos algures que apenas 32 pares neste universo satisfazem a relação, que podem ser visualizados assim

evidenciando um dos tais caminhos Hamiltonianos, que percorre 24 dos 32 lados do grafo.
E quantos caminhos  Hamiltonianos haverá? Uma coisa é certa: o número 18 tem de estar num dos extremos, pois é o único nó do grafo com grau 1. E a seguir ao 7, temos de ir pelo 9, ou podemos ir pelo 2? Bem, não é fácil responder.É a vez da Informática... Fica o desafio.