sábado, 28 de outubro de 2017

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

quarta-feira, 13 de setembro de 2017

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!

quinta-feira, 7 de setembro de 2017

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

quarta-feira, 29 de março de 2017

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!

terça-feira, 14 de março de 2017

Aprender a contar

Contar, contar o número de elementos de um conjunto, o número de vezes que um ciclo se realiza, o número de soluções de um problema, etc. é a Informática de todos os dias. Daí a importância da Matemática Discreta nos planos de estudo de Informática e de Engenharia Informática.
Brincava há alguns dias com um amigo, professor de Matemática no ensino secundário, sobre esta questão, e sobre como este tópico é aí abordado. Tanto quanto percebi, não é tratado autonomamente, mas sim dissimulado no estudo das probabilidades. A ser assim, é mau, por muitas razões.
O problema de partida era muito simples: de quantas maneiras diferentes se podem distribuir dez rebuçados iguais por três taças, admitindo-se que uma ou mais podem ficar vazias?
A solução mais simples para este problema resulta da observação desta figura
Se lermos os rectângulos azuis como separadores e os rectângulos laranja como rebuçados, a figura corresponde à hipótese 2+4+4, e entende-se facilmente que haverá tantas formas diferentes de distribuir os dez rebuçados pelas 3 taças como as de colocar os dois separadores numa fila de 12 elementos.
Como há 12 hipóteses para colocar o primeiro separador e 11 para colocar o segundo, e a ordem dos separadores não conta, há no total 12x11/2 = 66 formas diferentes.
Uma variante deste problema será: de quantas formas diferentes pode um treinador de futebol posicionar os seus 10 jogadores de campo pelas três posições possíveis, defesa, médio e avançado, sabendo que em cada posição têm de jogar pelo menos 2 jogadores?
Neste caso, só há na realidade quatro jogadores livres, que é necessário arrumar pelas 3 posições (2 separadores), pelo que haverá 6x5/2=15 possibilidades diferentes! Ver para crer:
São estas as brincadeiras que nos fazem pensar nos porquês...

terça-feira, 27 de dezembro de 2016

Números primos

Gosto dos números primos. São rebeldes, não se deixam arrumar.
Por exemplo, se tivermos um certo número de azulejos e os quisermos arrumar em paineis rectangulares, há casos em que isso é possível e outros em que não!
Com 15 azulejos, temos duas soluções


Se em vez de azulejos, fossem chocolates, podíamos arrumá-los em 3 grupos de 5 ou em 5 grupos de três, o que dá muito jeito na hora de repartir.
Mas se fossem 13, o caso mudaria de figura, pois não há qualquer hipótese de os arrumar num rectângulo, 13 é um número primo!


Um número primo não tem qualquer divisor, para além dele próprio e da unidade.
E afinal quantos divisores tem um número? Temos de procurar os factores primos e todas as combinações entre eles.

Se quisermos saber quantos são os divisores de 48, por exemplo, como 48 = 2x2x2x2x3, o factor  2 surge 4 vezes e o factor 3 surge 1 vez, pelo que o número de divisores de 48 é 10, o número de elementos do produto cartesiano dos conjuntos {1, 2, 4, 8, 16} e {1, 3}, que são as formas como os factores 2 e 3 podem figuram num divisor de 48.
Feitas as contas, os 10 divisores de 48 são {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}.

Um número primo muito falado recentemente é 557, o salário mínimo nacional, pelo que não é possível dividir 557 € em valores de montantes iguais. Seria essa a ideia malévola de quem fixou este número?

A propósito, perguntava há uns dias a alunos meus da área da Comunicação se já tinham visto um programa por dentro. Usando PENCILcode, fiz um programa muito simples, que todos entenderam, e que desenhava uma estrela com um número variável de pontas. Quando lhes perguntei porque seria que o programa funcionava melhor com certos números - primos - um deles logo comentou que deveria ser obra de Deus...

sábado, 29 de outubro de 2016

A fila mal comportada

Estou no último lugar de uma fila de 100 passageiros com lugares marcados, num avião com 100 lugares. O primeiro da fila (onde é que eu já vi...) senta-se num lugar à sorte! Os passageiros seguintes vão-se sentando nos lugares que lhes estão destinados, e sempre que um deles encontra o lugar já ocupado senta-se também num lugar ainda livre, à sorte. Qual é a probabilidade de eu encontrar o meu lugar livre?


A probabilidade é 50%, como se pode notar por exemplo aqui.
Mas precisamos de fazer contas complicadas para chegar a esta conclusão? Eu diria que não...
Pensemos.
O primeiro passageiro escolhe à sorte um lugar, que pode ser o dele mesmo, e então eu vou sentar-me no meu, que pode ser o meu, e então eu vou trocar com ele, ou que pode ser o de um terceiro passageiro.
Neste último caso, todos se vão sentando nos seus lugares, até chegar a vez deste passageiro, que, como encontra o seu lugar ocupado, se vai sentar num lugar à sorte, de entre os livres.
Pode escolher o lugar do primeiro passageiro da fila, que ainda está livre, e então o meu lugar fica garantido, pode escolher o meu lugar, e então vou ficar com o lugar do primeiro passageiro, ou então um dos restantes lugares ainda livres, e a situação repete-se, até acontecer uma das duas situações: ou sai o lugar do primeiro ou sai o meu!
E as probabilidades são exactamente iguais.