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.