Quizz 6 (III)

Uma nota: tem que ser possível obter efectivamente qualquer dos pesos de 1 a 40, inclusivé. Ou seja, se uma alternativa permitir, por exemplo, pesar de 1 a 39, ficando o 40 "de fora", isso não é solução. Há apenas uma pesagem, e com ela tem que ser possível pesar qualquer unidade de 1 a 40. Imaginem que têm um monte com 100 kilos de arroz para pesar, e que numa só pesagem têm de conseguir obter qualquer quantidades de 1 a 40.

Em jeito de (mais outra) pista (há outra no fim do post) para a solução do quizz 6, aqui ficam ilustrados alguns dos resultados que conseguimos obter com as alternativas A e B sugeridas aqui por dois leitores. Os resultados que não conseguimos obter estão a vermelho:


A: 1, 2, 5, 10, 20

Resultado pretendido = Combinação de pesos a usar

1 = 1
2 = 2
3 = 2 + 1
4 = 5 - 1
5 = 5
6 = 6 + 1
7 = 5 + 2
8 = 5 + 2 + 1
9 = 10 -1
(...)
17 = 10 + 5 + 2
(...)
36 = 20 + 10 + 5 + 1
37 = 20 + 10 + 5 + 2
38 = 20 + 10 + 5 + 2 + 1
39 = impossível
40 = impossível


B: 2, 2, 5, 10, 20

Resultado pretendido = Combinação de pesos a usar

1 = 5 - 2 - 2
2 = 2
3 = 5 - 2
4 = 2 + 2
5 = 5
6 = 10 - 2 - 2
7 = 5 + 2
8 = 10 - 2
9 = 5 + 2 + 2
(...)
17 = 10 + 5 + 2
(...)
36 = impossível
37 = 20 + 10 + 5 + 2
38 = impossível
39 = 10 + 5 + 2 + 2
40 = impossível

Outra pista ainda: reparem que quer com a combinação A quer com a B, existe alguns pesos que podem ser obtidos de mais do que uma forma. Isto soa a solução ineficiente. E (para já) mais não digo.