Quizz 6 - resposta 2/3

As soluções dos leitores já estão online. A resposta à pergunta 2,

2. Qual o número mínimo de pesos que lhe permite fazer todas as pesagens unitárias de 1 a n? Ou seja, qual a regra geral a usar? Explique a intuição para esse resultado.

é usar potêcnias de base de 3, de tal forma que a soma total de todos os pesos seja igual ou superior a n. Ou seja, usar os pesos:

P1 = 1
P2 = 3^1 = 3
P3 = 3^2 = 9
P4 = 3^3 = 27
P5 = 3^4 = 81
P6 = 3^5 = 243
...
PX = 3^(X-1)

Logo, para obter os resultados de 1 a n, necessitamos de um número mínimo de pesos X, tal que (P1 + P2 + ... + PX) seja maior ou igual a n. Se tomarmos Si=1,X (Pi) como o somatório de Pi, de i=1 até i=X, tendo em conta que isto é uma soma de termos de uma progressão geométrica, temos que Si=1,X (Pi) = [3^(x+1) - 1] / 2. Logo, o número mínimo de pesos é igual a Int {log3 [(n+1) / 2]}, isto é, o número inteiro maior ou igual ao logaritmo de base 3 de [(n+1) / 2].

Qual a intuição para a solução ser o uso de potências de base 3?

Usemos a descrição dada na solução à primeira questão.

P1 = 1.

Para ser eficiente, tempos que P2 - P1 = P1 + 1, isto é, que P2 é tal que a diferença entre P2 e P1 é o peso seguinte a P1. Logo, P2 = 2P1 + 1 = 3, uma vez que P1 = 1.

Para P3 usamos o mesmo raciocínio. P3 tem de ser tal que conseguimos obter o número que se segue a (P1 + P2) através da diferença entre os dois. Logo, P3 - (P2 + P1) = (P2 + P1) + 1, isto é, P3 = 2(P2 + P1) + 1.

Podemos substituir a expressão para P2, obtendo P3 = 2(2P1 + 1 + P1) + 1 = 2(3P1 + 1) + 1 = 6P1 + 2 + 1 = 6 + 3 = 9.

P4 = 2(P3 + P2 + P1) + 1 = 2(P3 + 3P1 + 1) + 1, substituindo a expressão para P2. Substituindo P3, obtemos P4 = 2(6P1 + 3 + 3P1 + 1) + 1 = 2(9P1 + 4) + 1 = 18P1 + 8 + 1 = 18 + 9 = 27.

P5 = 2(P4 + P3 + P2 + P1) + 1 = 2(18P1 + 9 + 6P1 + 3 + 2 P1 + 1 + P1) + 1 = 2(27P1 + 13) + 1 = 54P1 + 26 + 1 = 81.

A intuição já deve estar a apurar... é fácil perceber donde vêem as potências de 3:

P2 = 2P1 + 1

P3 = 6P1 + 3 = 3 (2P1 + 1) = 3P2

P4 = 18P1 + 9 = 3 (6P1 + 3) = 3P3

Cada peso, a partir do terceiro, é o triplo do anterior. E temos que P1 = 1 e P2 = 3. Logo, temos uma sequência de potências de 3. Podíamos chegar lá através da expressão genérica para o peso n, mas confesso que o formato de blogue não convida à extensão de argumentos que usem muitas fórmulas.

Ainda por responder está a terceira pergunta - a demonstração que a solução mais eficiente é usar potências de base 3. O próximo quiz está para breve.