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].

Fourier e a pandemia

Decidi investigar se, nos vários países, haveria uma periodicidade semanal na sequência de casos CoVid-19 registados diariamente.
Usei os dados fornecidos pela John Hopkins University, e fiz um pequeno programa que, para um país escolhido, retira a sequência de resultados disponíveis (casos acumulados), constrói a sequência de casos dia a dia, calcula a transformada de Fourier desta sequência, e mostra os resultados.
Por exemplo, para Portugal obtive (deixemos de lado a escala...)

Visível a sequência de casos diários conhecida (a azul) e, a laranja, a transformada de Fourier dessa sequência. A outra metade seria simétrica desta. Aquele pico por volta do índice 20 corresponde à periodicidade semanal! Et voilà!
Realmente, sendo a frequência de amostragem 1 por dia, e 145 o número de amostras, a frequência 1 em cada 7 dias estará no índice 145/7.
Curiosamente, noutros países encontrei picos mais nítidos, como na Alemanha

e mesmo na Itália

que interpreto como um funcionamento menos caótico do sistema de registo dos dados...
Será?

Aqui há mesmo informática...

Há quem considere ser este o mais curto grande artigo científico de sempre:

Não sei se é mesmo assim, mas o curioso é só seria possível escrevê-lo recorrendo a um computador e a uma linguagem de programação.

O computador foi o CDC 6600, da Control Data Corporation, o computador mais veloz do mundo de 1964 até 1969, e a linguagem de programação muito possivelmente terá sido Fortran.

O problema do coleccionador de cartas

Os supermercados têm o hábito de, em certas alturas, oferecer aos (filhos dos) seus clientes umas cartas para coleccionar. As cartas são oferecidas aleatóriamente, não podendo os clientes escolhê-las.
A questão consiste em saber quantas cartas terá um coleccionador de acumular, em média, para completar a sua colecção.
É um problema semelhante àquele de saber quantos lançamentos de um dado deve uma pessoa fazer, em média, para obter as seis faces. A resposta a esta questão é

que é a soma dos inversos das probabilidades de sair a primeira, a segunda, a terceira, a quarte, a quinta e a sexta faces, respectivamente.
No caso geral de N cartas,

que pode ser um número "assustadoramente" grande. Por exemplo, para 100 cartas, o número é 518.7, ou seja, em média, seria necessário recolher mais de 518 cartas para completar a colecção.
Este processo aleatório caracteriza-se por ter uma cauda longa, isto é, pode acontecer ser necessário esperar um tempo estranhamente longo para obter todos os resultados...
O gráfico seguinte corresponde a 1100 milhões de simulações do jogo dos dados, e houve uma vez em que foram necessários 127 lançamentos para saírem as seis faces!

Entretanto, a moda, o valor mais frequente, foi 11, bem inferior à média de 14.7!
(recordo aqui uma simulação em NetLogo que há uns tempos propus)

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.

Isso é muito chato!

Hoje tentei ensinar a uma jovenzinha qual é o resultado da divisão de um número por zero...
Comecei pelo algoritmo da divisão inteira - quantas vezes do dividendo se pode tirar o divisor - o número de vezes que se pode tirar é o quociente e o que sobra é o resto.
Por exemplo, para dividir 12 por 5, podemos tirar 2 vezes o 5 e sobram 2.

Ou para dividir 12 por 4, podemos tirar 3 vezes o 4 e não sobra nada - divisão exacta.

Estava a começar o caso da divisão por 0, quando sou interrompido por um "Isso é muito chato!" Porquê? "Porque assim a tirar 0 de cada vez nunca mais acaba!"
Missão cumprida...

HEART ou EARTH

Este problema apareceu no site brilliant.org.
Uma máquina de escrever está a gerar aleatoriamente uma sequência de caracteres de A a Z, todos com igual probabilidade de ocorrência. Dada uma palavra qualquer, essa palavra deverá eventualmente surgir escrita pela máquina, ao fim da geração de um número suficiente de caracteres.
Uma palavra de 5 letras, requererá em média a geração de 26^5 = 11881376 caracteres.
A questão é a seguinte: das duas palavras HEART e EARTH, haverá uma com maior probabilidade de ser escrita em primeiro lugar, ou as probabilidades são idênticas?
Eu acho que sim, que há uma, mais especificamente a palavra HEART, mas este problema desencadeou discussões muito interessantes no meu Facebook, com a maior parte dos intervenientes a achar que as probabilidades são idênticas. Curiosamente, alguns alunos de Informática corroboraram a minha opinião, e chegaram mesmo a produzir simulações que o evidenciavam.
A razão para esta assimetria resulta do facto de as duas palavras dadas diferirem apenas da posição da letra H, e de uma tentativa para formar a palavra EARTH exigir que antes da letra E não esteja a letra H, enquanto que uma tentativa para formar a palavra HEART não tem qualquer restrição na letra que antecede o H.
Em média, em cada 26 tentativas para formar a palavra EARTH, há uma que acaba por formar a palavra HEART, que fica assim mais provável.
Acabo de fazer eu próprio uma pequena simulação com 100 jogos, tendo gerado 637431406 caracteres e tendo a palavra HEART ganho 52 vezes.
Deixo aqui o código mesmo muito elementar que usei

Espero que se divirtam...

O número em falta

Este problema apareceu no Quora.
"Neste fila
2491771842155490223116351359624312364528611014378220168235412194624714016711713319814428177371372322483356775157513821213812018915616178169180422057425055702049257200441752021649520319463179155401482271358391661117611818617619918524622611214787196431912247122923132852316022867242822118221107236471216824475181150239121712918214915910923798652331532147215125222170494190146216102161182971832061006216327616919791582131417224013622832171920823414111920188116842613237131811954516213053245241210105361242183110491312860155099247920710123810311423018722589102126931061741129193139134341491423011512712511380881921451541731651085920912215220148
estão todos os números entre 1 e 250, menos um, colocados por uma ordem aleatória. Qual é o número em falta?"
Este problema, na sua  simplicidade, levanta algumas questões interessantes, e nem todos olham para ele da mesma maneira...
Eu comecei por querer saber quantos algarismos estão na fila e quantos estariam se os 250 números lá estivessem.
Os computadores servem para fazer estas coisas com muita facilidade (eu gosto de Python, mas qualquer linguagem de programação é boa)

s="2491771842155490223116351359624312364528611014378220168235412194624714016711713319814428177371372322483356775157513821213812018915616178169180422057425055702049257200441752021649520319463179155401482271358391661117611818617619918524622611214787196431912247122923132852316022867242822118221107236471216824475181150239121712918214915910923798652331532147215125222170494190146216102161182971832061006216327616919791582131417224013622832171920823414111920188116842613237131811954516213053245241210105361242183110491312860155099247920710123810311423018722589102126931061741129193139134341491423011512712511380881921451541731651085920912215220148"
print (len(s))
v=""
for i in range (1,251):
    v = v + str(i)
print (len(v))

A primeira instrução de print dá-nos o comprimento da lista dada, 640, e a segunda instrução de print dá-nos o comprimento da lista dos 250 números construída com as instruções anteriores, 642.
Portanto, o número em falta tem dois algarismos, necessariamente iguais, pois se fossem diferentes ficaríamos com duas respostas possíveis.
Não é difícil saber quais são:

for i in range (0, 10):
    cs = 0
    for j in s:
        if j == str(i):
            cs = cs + 1
    cv = 0
    for j in v:
        if j == str(i):
            cv = cv + 1
    print (i, cs, cv)

O resultado deste programa todo é

640
642
0 45 45
1 155 155
2 106 106
3 55 55
4 55 55
5 46 46
6 43 45
7 45 45
8 45 45
9 45 45

(colorido a posteriori) e concluí-se que o número em falta é o 66!

Fourier no dia a dia

Fourier, transformada de Fourier, tempo e frequência, resposta em frequência, todo um susto para muitos de nós, iniciados ou leigos. No entanto, são conceitos que utilizamos todos os dias.
Quando dizemos que temos um almoço com um determinado grupo uma vez por semana, estamos a fazer uma definição no domínio das freqências!
Sendo a frequência o número de vezes que um evento ocorre por unidade de tempo, é fácil calculá-la. Neste exemplo, se a unidade de tempo for o dia, será 1/7 por dia. Se for a semana, será 1 por semana. Se for o segundo, será 1/7*86400 Hz (a unidade de medida seria o hertz, unidade de medida de frequência do sistema internacional de medidas).
Familiarmente, a electricidade que usamos em nossa casa é proveniente de uma fonte periódica com a frequência de 50 Hz, ou seja, que se repete 50 vezes por segundo.
Claro que a frequência com que ocorre um evento não nos permite localizá-lo no domínio dos tempos. Uma vez por semana? Mas em que dia? Falta o conceito de fase, que tipicamente se exprime como uma fracção do período, ou sob a forma de um ângulo: um período serão 360º ou 2*pi radianos.
No nosso exemplo rudimentar, se a semana se iniciasse à segunda-feira, um evento nesse dia teria fase 0, no dia seguinte, teria fase 1, etc.
A nossa agenda electrónico funciona mais ou menos assim. Existe um registo dos eventos recorrentes, em termos de frequência e fase, mas que queremos depois visualizar no domínio dos tempos. Por exemplo, aqui temos 3 eventos, um todas as semanas, à quarta-feira, outro de duas em duas semanas, à quinta-feira da primeira semana, e um terceiro, de quatro em quatro semanas, à quinta-feira da segunda semana:

Do nosso ponto de vista, interessa-nos normalmente visualizar a agenda no domínio dos tempos

(aqui, só uma vista de seis semanas consecutivas, a partir de uma origem dos tempos arbitrária), e não parece difícil fazer esta conversão. Mas realmente fez-se uma transformada de Fourier inversa!
A transformação no domínio oposto, do tempo para a frequência, seria neste caso mais complicada, mas realmente foram estes problemas que apaixonaram Fourier e Laplace, com os registos das passagens dos astros e a tentativa de os simplificar...

Matemática, Matemática...

Um livro de Matemática para os nossos alunos do 4º ano de escolaridade - a minha quarta classe, da Professora Maria da Graça, na Escola 33A - propõe o seguinte exercício:

Pasmo!
Um exercício de Matemática, ou qualquer outro, não pode começar por pecar logo no enunciado! E este tem erros de facto, que perturbam qualquer pessoa, e por maioria de razão um jovem de 9 anos de idade, que, ou resolve por algum automatismo estúpido imposto pelo seu professor ou, se decide ler, não consegue.
"Representar as operações nos quadriculados" o que quer dizer exactamente? Com outros quadriculados, até se entenderia:

E a partir daí, mesmo um aluno de 9 anos seria capaz de encontrar as desejadas respostas, 1/2, 3/4 e 2/3.
Com aqueles quadriculados, e "lendo" o enunciado como "Realizar as operações e representar os resultados nos quadriculados", poder-se-ia realizar as operações, por simplificação de fracções, obter os resultados, 1/2, 3/4 e 2/3, e depois representá-los nos quadriculados fornecidos

embora neste caso com um conteúdo didáctico muito fraquinho...
Seria esta a solução pretendida?!
Confesso que gostava de saber como tem este exercício sido interpretado nas nossas Escolas!