Quizz 6 - solução 1/3

As respostas ao quizz 6 vão ser dadas por partes. Hoje atacamos a primeira questão. O problema, antes de mais.

Existe uma balança com dois pratos onde pretende conseguir pesar qualquer quantidade unitária de 1 a 40. Ou seja, qualquer número inteiro positivo entre 1 e 40, inclusivé, isto é: 1, 2, 3, 4, ... 38, 39, 40. Tem à sua disposição todos os pesos unitários de 1 a 40.

1. Qual o número mínimo de pesos que lhe permite fazer todas as pesagens unitárias de 1 a 40? Quais são os pesos escolhidos? Explique como chegou à sua resposta.

A ideia chave aqui é «eficiência». Tentar, cada vez que escolhemos um peso, fazer com que haja o mínimo de redundância possível, isto é, que entre dois pesos X e Y, devemos escolher aquele que permitir mais pesagens. E também não deixar "buracos por preencher". Para clarificar os termos, vamos chamar "pesos" aos intrumentos que vamos utilizar na balança e "resultados" ao peso final obtido. O ponto fulcral é perceber que com uma balança de dois pratos podemos jogar com os pesos dum lado ou do outro, o que equivale a somar ou subtrair (isto será claro mais tarde).

Para obtermos o resultado 1, a solução mais eficiente parece intuitivamente ser usar o peso 1. Poderíamos, também, escolher dois pesos cuja diferença fosse 1. Por exemplo, escolher o 2 e o 3. Mas isso parece claramente ineficiente. Isto será óbvio mais tarde. A ideia, como referi anteriormente, é que não pode ser eficiente deixar "buracos" por preencher, e com os pesos 2 e 3 obteríamos os resultados 1, 2, 3 e 5, mas não o 4, que é, desse modo, um "buraco" que fica por preencher. Escolhamos então P1 = 1. De seguida, temos de obter o resultado 2. Podemos escolher o peso 2 ou o peso 3. O último é claramente mais eficiente, dado que com 1 e 3 conseguimos obter 1, 2, 3 e 4, enquanto que com 1 e 2 apenas obtemos 1, 2 e 3. Logo, P2 = 3. Temos, agora, de obter o resultado seguinte, o 5.

Aqui aparece a «intuição» do problema. Escolher 5 é ineficiente. O peso mais eficiente que devemos escolher para P3, uma vez que já conseguimos os resultados de 1 a 4, é um peso tal que subtraído de 4 resulte em 5. Assim evitamos a ineficiência de conseguir obter o mesmo peso de mais do que uma maneira. Seguindo este raciocínio, chegamos a P3 = 9. Quais os resultados que conseguimos obter com os pesos P1 = 1, P2 = 3 e P3 = 9? Melhor explic(it)ar:

1 = 1
2 = 3 - 1
3 = 3
4 = 3 + 1
5 = 9 - 3 - 1
6 = 9 - 3
7 = 9 - 3 + 2
8 = 9 - 1
9 = 9
10 = 9 + 1
11 = 9 + 3 - 1
12 = 9 + 3
13 = 9 + 3 + 1

Chegados a este ponto, como obter o resultado 14? O raciocínio é o mesmo que utilizamos para chegar a P3 = 9. Uma vez que com os três primeiros pesos conseguimos obter qualquer resultado de 1 a 13, P4 deverá ser tal que subtraído de 13 dê 14. Logo, P4 = 27.

A solução é, portanto, escolher os pesos 1, 3, 9 e 27. Com estes é possível obter qualquer resultado de 1 a 40 - de forma eficiente.

Fica para depois a resposta às duas restantes perguntas:

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.

3. Demonstre o resultado obtido na resposta anterior.

Para aqueles que desistiram da demonstração, deixo duas dicas. I) Apenas é pedido que se prove que esta escolha é a mais eficiente, mas não necessariamente a única (embora também o seja). II) Qualquer resultado pode ser visto como sendo obtido usando o seguinte método, onde somamos sempre todos os pesos disponíveis, e cada um está ponderado por um elemento do conjunto {-1, 0, 1}.

Por exemplo:

1 = (1)P1 + (0)P2 + (0)P3 + (0)P4 = 1 + 0 + 0 + 0 = 1

5 = (-1)P1 + (-1)P2 + (1)P3 + (0)P4 = -1 - 3 + 9 + 0 = 5

7 = (1)P1 + (-1)P2 + (1)P3 + (0)P4 = 1 - 3 + 9 + 0 = 7

11 = (-1)P1 + (1)P2 + (1)P3 + (0)P4= -1 + 3 + 9 + 0 = 12

17 = (-1)P1 + (0)P2 + (-1)P3 + (1)P4 = -1 + 0 - 9 + 27 = 17

25 = (1)P1 + (-1)P2 + (0)P3 + (1)P4 = 1 - 3 + 0 + 27 = 25

34 = (1)P1 + (-1)P2 + (1)P3 + (1)P4 = 1 - 3 + 9 + 27 = 34

40 = (1)P1 + (1)P2 + (1)P3 + (1)P4 = 1 + 3 + 9 + 27 = 40

Volto a moderar os comentários, para quem quiser arriscar respostas a qualquer das duas perguntas ainda não tratadas aqui. Boa sorte.

PS: aos que pretenderem também provar que o resultado é único, há que ter em conta a concavidade/convexidade da função que se está a pretender minimizar . Outra dica: podemos usar um argumento "dual" aqui: minimizar uma determinada função pode ser equivalente a maximizar uma outra. Digo "pode" porque é preciso provar que se pode usar este argumento.