O problema do teste de Singapura

De repente, não se fala de outra coisa...
Num exame para miúdos de 14 anos, em Singapura, saiu o seguinte problema:

Albert e Bernard ficaram amigos de Cheryl, e querem saber a data do seu aniversário. A Cheryl faz uma lista de 10 datas possíveis

Maio: 15, 16, 19
Junho: 17, 18
Julho: 14, 16
Agosto: 14, 15, 17

e diz, separadamente, a Albert o mês do seu aniversário e a Bernard o dia.
Albert diz: não sei qual é o dia, mas sei que o Bernard também não sabe.
Bernard diz: inicialmente, não sabia, mas agora já sei.
Albert conclui: então também sei!
Qual é a data de aniversário de Cheryl?

(solução segue dentro de momentos...)

Vamos então a isso!
Albert diz: não sei qual é o dia, mas sei que o Bernard também não sabe.
Albert sabe o mês. Se o mês fosse Maio ou Junho, não podia ser peremptório relativamente ao facto de Bernard também não saber, pois em Maio há o dia 19 e em Junho o dia 18, que só ocorrem nesses meses. Então o mês é Julho ou Agosto.
Bernard diz: inicialmente, não sabia, mas agora já sei.
Bernard sabe o dia. Se fosse 14, não podia saber a data, pois podia ser em Julho ou Agosto. Assim, é 16 de Julho ou 15 ou 17 de Agosto.
Albert conclui: então também sei!
Albert sabe o mês! Então o dia é 16 de Julho, pois se fosse um dia de Agosto ainda restariam duas possibilidades para a data!

Torre de Hanói

Um problema que muitas vezes se usa para ilustrar o poder da recursividade é o da torre de Hanói.
Segundo a lenda, numa cidade no centro do mundo, um monge realiza a tarefa de mover 64 discos de um pilar para outro, usando apenas um pilar auxiliar, e de acordo com duas regras simples: só pode mover um disco de cada vez e nunca pode colocar um disco sobre outro de menor diâmetro. Quando terminar a tarefa, será o fim do mundo...

Este problema pode ser analisado sob o prisma da recursividade. Realmente, se soubermos resolver o problema para n-1 discos, sabemos facilmente resolvê-lo para n discos!
Como? Aplicando a solução para os n-1 discos duas vezes: primeiro, movendo todos os discos menos o de maior diâmetro para o pilar auxiliar, em seguinda movendo o disco de maior diâmetro para o pilar de destino, e finalmente movendo os n-1 discos que estão no pilar auxiliar para  o pilar de destino...
E já está? Estaria se soubéssemos efectivamente mover os n-1 discos. E se não soubermos? Segundo a mesma lógica, bastaria saber mover n-2 discos, etc.
Repetindo o raciocínio, devemos chegar ao ponto em que basta saber mover 2 discos, e isso sabemos facilmente, com 3 movimentos: mover o disco de menor diâmetro para o pilar auxiliar, mover o disco de maior diâmetro para o pilar de destino, e finalmente mover disco de menor diâmetro do pilar auxiliar para o pilar de destino.
E quantos movimentos serão necessários para mover os 64 discos? Se representarmos por mov(n) o número de movimentos necessários para transportar n discos, ter-se-á:

mov(2) = 3
mov(3) = mov(2) + 1 + mov(2) = 3 + 1 + 3 = 7
mov(4) = mov(3) + 1 + mov(3) = 7 + 1 + 7 = 15 = 2^4 - 1
mov(5) = mov(4) + 1 + mov(4) = 15 + 1 + 15 = 31 = 2^5 - 1
...
mov(64) = 2^64 -1

o que dá exactamente 18 446 744 073 709 551 615 movimentos! Se o monge conseguisse realizar um movimento por segundo, demoraria aproximadamente 5849 milhões de séculos para concluir a tarefa...

Ora aqui está outro belo tema para uma página Web a desenvolver por alunos do 7º ano do nosso ensino secundário.

Recursividade

A recursividade, a capacidade de formular de forma recursiva a solução de um problema, é uma das dimensões do chamado pensamento computacional.
Sempre que se fala de recursividade, costuma usar-se a função factorial para a ilustrar.
Realmente, como fact(n) = n x fact(n-1), acrescentando uma condição de paragem, fact(1) = 1, temos a função factorial definida de uma forma recursiva:

def fact(n):
    if (n <= 1):
        return 1
    else:
        return n * fact(n - 1)

Encontrei recentemente uma ideia muito interessante para ilustrar a recursividade, sem recorrer a estes conceitos de programação.
Imagine o leitor que está sentado numa fila de um anfiteatro, a assistir a um espectáculo, e pretende saber qual é o número da fila em que está sentado.

Uma solução será perguntar a um espectador sentado na fila à sua frente em que fila está, e somar 1 à resposta obtida. Se este espectador não souber, ele próprio pode proceder de modo idêntico relativamente ao espectador da fila seguinte, e assim sucessivamente, até um saber a resposta (eventualmente um espectador sentado na primeira fila!). Nesse momento, o problema fica resolvido.

E que tal desafiar um grupo de alunos de TIC, 7º ano de escolaridade, a entender este conceito e explicá-lo numa página Web de sua autoria? Também é assim que se desenvolve o pensamento computacional...

PACC

O selecionador nacional convocou 17 jogadores para o próximo jogo de futebol. Destes 17 jogadores, 6 ficarão no banco como suplentes. Supondo que o selecionador pode escolher os seis suplentes sem qualquer critério que restrinja a sua escolha, poderemos afirmar que o número de grupos diferentes de jogadores suplentes (A) não se relaciona com o número de grupos diferentes de jogadores efetivos. (B) é superior ao número de grupos diferentes de jogadores efetivos. (C) é igual ao número de grupos diferentes de jogadores efetivos. (D) é inferior ao número de grupos diferentes de jogadores efetivos.
Aqui está um exemplo de uma pergunta mal escolhida e mal formulada.

Imagem retirada de aqui.

Na cabeça do autor da pergunta está aquela ideia simples de que C(n, m) = C(n, n - m), isto é, de que o número de combinações possíveis de m elementos retirados de um conjunto de n é exactamente igual ao número de combinações dos n - m não retirados: C(17, 6) = C(17, 11). Qualquer treinador de futebol sabe: retirados os suplentes, ficam os efectivos.
O problema é que no futebol os jogadores ocupam posições no campo, isto é, com 11 jogadores é possível fazer mais que uma equipa, trocando-os de posição. Não se trata de combinações, mas de arranjos! E na verdade A(17, 11) é maior que A(17, 6), pelo que, nesta óptica, a resposta certa seria a resposta (D), e não a resposta (C) como o IAVE propõe.
Ao perguntar o número de grupos, fica a dúvida. Grupo, é uma palavra dúbia, neste contexto. A sugestão de que se trata de futebol, e não corta-mato, por exemplo, sugere que a posição conta.
E isto não pode acontecer. E não é exemplo de pensamento computacional.
Tivesse eu realizado a prova e respondido (D), não me calava...