Contar quadrados...

Uma versão ligeiramente diferente de um problema antigo.
Olhemos para o quadrado da figura abaixo, que tem uma área de 8x8=64 quadrados unitários.

Se o recortarmos em quatro peças, conforme assinalado e rearrumarmos as peças de acordo com a sua posição no rectângulo representado, verifica-se que obtemos uma figura com uma área de 5x13=65 quadrados unitários! Apareceu um quadrado!

Qual é a explicação? Deixo aqui o desafio...

Herança em perigo

Aos domingos, gosto de olhar para os desafios do Público, de José Paulo Viana e Cristina Sampaio.
Algumas vezes fico decepcionado, mas a maioria das vezes gosto de pensar no desafio, sempre com a ideia de comparar a minha solução com a que será publicada no domingo seguinte. É o caso de hoje:
"Pouco antes de morrer, o pai chamou o filho:
- Tenho aqui 111 moedas de ouro muito antigas. Aparentemente são iguais mas foram fabricadas em momentos diferentes e 50 delas pesam menos um grama que as outras 61. Todas elas serão tuas se conseguires resolver o problema que te vou pôr.
Pegou numa das moedas e continuou:
- Tens de descobrir se esta moeda é uma das leves ou uma das pesadas. Para isso, tens direito a fazer uma única pesagem usando esta balança de dois pratos e estes pesos de 1, 2, 4, 8, 16 e 32 gramas para equilibrar os pratos.
Como deverá proceder o filho para ter a garantia absoluta que herdará as moedas?"
Aqui está!

Curiosamente, ocorreu-me de imediato a ideia de dividir as outras 110 moedas em dois grupos de 55 e determinar a diferença de pesos. Mas será que nenhuma das diferenças de pesos excede 1+2+4+8+16+32=63 gramas? E que da diferença de pesos se pode retirar a conclusão pretendida?
Se a moeda que o pai pegou for das leves, as outras 110 são 49 leves e 61 pesadas, e se for das pesadas, as outras 110 são 50 leves e 60 pesadas, dois conjuntos diferentes.
E como se podem distribuir, nos dois casos, as 110 moedas em dois grupos de 55?
Se nos concentrarmos nas moedas pesadas apenas, no primeiro caso temos um total de 61, ficando necessariamente num dos pratos um número par de moedas e no outro um número ímpar, pelo que a diferença de pesos entre os dois pratos será ímpar, e no segundo caso temos um total de 60, ficando nos dois pratos simultaneamente ou um número par ou um número ímpar de moedas, pelo que a diferença de pesos entre os dois pratos será par.
Como a diferença máxima é de 55-6=49 no primeiro caso e de 55-5=50 no segundo, e com pesos com aqueles valores, todas as diferenças podem ser medidas (numeração binária), e os pesos são suficientes para pesarmos qualquer diferença possível.
E então, o que teremos de fazer será dividir as 110 moedas em dois grupos de 55 e determinar a diferença de pesos. Se a diferença for ímpar, a moeda retirada é das leves, e se for par é das pesadas.
Simples!

Ensinar é despertar a vontade de aprender

O meu trabalho com futuros professores de Informática no 3º ciclo do ensino básico e no ensino secundário, de que tenho partilhado aqui alguns aspectos,  tem-me permitido observar de uma forma directa os problemas com que se debatem especificamente os professores de Informática, apanhados entre as nossas gerações mais jovens, os nativos digitais, que querem perceber para que serve o que lhes é ensinado, os programas nacionais, cheios de visões do passado, muito feitos à medida das dificuldades dos professores, e os conhecimentos que estes trouxeram da Universidade, datados, quantas vezes inúteis, quando não contra-producentes.
As TIC, as ferramentas TIC, as ferramentas da Web, servem para disfarçar estas dificuldades e para manter alunos e professores ocupados nas salas de aula em actividades muitas vezes inúteis, pois dão uma visão errada da realidade, em que a tecnologia domina, quando devia ser colocada ao serviço da resolução de problemas.
Todos deviam ler  este relatório "Informatics education: Europe cannot afford to miss the boat"

e tomar consciência do que está a acontecer em tantos países, que já tomaram consciência da importância do ensino de Informática desde muito cedo.
O desafio é gigantesco, vai ser preciso desaprender, vais ser necessário compreender que o professor não pode ser alguém que debita na sala de aula aquilo que aprendeu à justa nos dias anteriores, mas tem de ser alguém treinado especificamente para ensinar, para despertar a vontade de aprender, e que distinga os níveis de conhecimento que o professor deve ter e que o aluno deverá atingir.
O professor de música não forma músicos para a orquestra sinfónica nacional, mas tem de saber e ensinar música, e não pode aniquilar o talento musical precoce de um jovem.
Vem isto a propósito das minhas tentativas de desafiar os alunos com problemas tão simples que não é possível o costumeiro refúgio do mau aluno, que não faz, diz como se "faz"...
Recentemente, propús que resolvêssemos "à mão" um problema muito simples de pesquisa de soluções numa árvore, como introdução à resolução de um problema aparentemente mais complexo, relatado noutro sítio. Este problema,

curiosamente permitiu desenhar toda a árvore de soluções a pesquisar

chegar às 8 soluções possíveis, e perceber como se poderia mecanizar um problema de maior dimensão. Com os 25 números do outro problema haveria 25! soluções a pesquisar, e uma pesquisa exaustiva demoraria vãrias idades do Universo a realizar...

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.

Um problema de um manual de Matemática do 12º ano

Não sei qual é o manual, não sei quem são os autores, só sei o que nos diz hoje o José Paulo Viana na solução do desafio do Público da semana passada: "O Martim tem uma antiga balança de pratos mas só lhe restam cinco pesos: 2g, 5g, 10g, 20g e 50g. Com estes pesos quantas pesagens diferentes se conseguem fazer?"
O manual indica 31 como resposta, o que está obviamente errado, como o JPV nos explica. Aliás, bastava os autores alguma vez terem visto alguém num mercado qualquer manusear uma dessas balanças, como tantas vezes vi no Mercado do Bolhão e em tantos outros sítios, para perceberem que uma boa parte da técnica de utilização destas balanças reside na possibilidade de se colocarem pesos nos dois pratos e numa destreza mental de respeito.
Os autores do manual lá terão pensado que "aqui havia Informática", partiram do princípio de que cada peso só pode ser utilizado num dos pratos, e limitaram-se a contar quantos números binários de 5 dígitos diferentes de 0 existem, sendo que em cada posição o dígito 0 significaria que o peso respectivo não é utilizado e o dígito 1 significaria que é:

50g	20g	10g	5g	2g
0/1	0/1	0/1	0/1	0/1

Muito habilidoso, mas pouco instrutivo, até porque a suposta ideia do contador binário só funciona se os pesos, colocados por ordem decrescente, pesarem cada um no máximo metade do anterior. Imagine-se, por momentos, que os pesos eram de 2g, 5g, 10g, 20g e 30g, por exemplo. Então, como 30g poderia ser pesados de duas maneiras diferentes, já não haveria as tais 31 pesagens diferentes!
Para contar todas as hipóteses, de um peso estar num prato, no outro, ou não estar em nenhum, seria necessário utilizar um contador ternário, em que o dígito -1 significaria que o peso está colocado no mesmo prato do objecto:

50g	20g	10g	5g	2g
-1/0/1	-1/0/1	-1/0/1	-1/0/1	-1/0/1

Neste caso, há 3 à 5ª contagens diferentes, das quais uma conduz ao peso 0, e metade das restantes correspondem a pesos negativos. As restantes 121 correspondem a pesos positivos.
O problema agora está nas repetições...
A maneira mais simples será analisar todas as possibilidades numa folha de cálculo, e verificar que há mesmo só 52 possibilidades.

Fibonacci

Este desenho representa um dos estudos mais interessantes da matemática e da arte, e que começou eventualmente com Euclides e as suas aproximações ao desenho de espirais por justaposição de quartos de círculo.

Começando com um quadrado de lado 1, ele acrescentava um segundo quadrado também de lado 1, depois um de lado 2 (1 + 1), um de lado 3 (2 + 1), um de lado 5 (3 + 2), um de lado 8 (5 + 3). um de lado 13 (8 + 5), e assim sucessivamente.
Esta sequência de lados dos quadrados - 1, 1, 2, 3, 5, 8, 13, ... - é a sequência de Fibonacci, que tantas vezes nos surpreende. Define-se recursivamente:

F(n) = F(n -1) + F(n - 2)
F(1) = 1
F(0) = 1

A figura anterior é um rectângulo, e a relação entre a sua largura e a sua altura é considerada artisticamente proporcionada, sendo conhecido pelo rectângulo dourado. À medida que novos quadrados são acrescentados, a proporção converge para um valor determinado:

Um dos problemas destas sucessões definidas recursivamente é a dificuldade em obter um termo geral, que permita calcular qualquer dos seus termos sem ser necessário retroceder até F(0).
Pode-se?
Os mais familiarizados com a transformada Z reconhecem imediatamente aqui uma aplicação, e com alguns cálculos simples até chegam ao valor exacto de F(n)/F(n - 1) quando n tende para infinito: (1 + Ö5)/2 = 1.6180339887... Número mágico, presente na pintura, na arquitectura, na música, na economia, e em muitos outros domínios.

Recursividade

Recursividade, o que é?
Eis um assunto que tem de ser visto com todo o cuidado, para não restarem dúvidas.
Uma função recursiva será uma função em cuja definição se recorre à própria função. Um exemplo muito usado é o do cálculo de n! (factorial de n): se soubermos (n-1)!, então calcular n! é facílimo, basta multiplicar n por (n-1)!:

int factorial (int n)
{
   return n * factorial (n-1);
}

E isso basta? Não! Não basta. Assim, nunca mais pára! Se quiséssemos calcular 5!, por exemplo, iríamos obter sucessivamente


5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1 * 0!
5 * 4 * 3 * 2 * 1 * 0 * (-1)!
...

Precisamos claramente de uma instrução que indique que não é necessário continuar o processo, uma vez que chegamos a um valor conhecido da função, e podemos retroceder. Por exemplo

int factorial (int n)
{
   if (n == 0) return 1;
      else return n * factorial (n-1);
}

que permite que agora tudo corra bem:

5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1 * 1
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

e obtenhamos o resultado correcto.
Temos de voltar a isto, mas acompanhados de Fibonacci.