Problema da semanaLógica
As fichas leves e a balança de uma pesagem só
Enunciado
MédioOito fornecedores mandam, cada um, um saco com 500 fichas metálicas. Uma ficha correta pesa 12 g. Um dos fornecedores está com a máquina desregulada, e todas as fichas do saco dele pesam 11 g. A olho nu as fichas são idênticas. Você tem uma balança digital precisa e pode fazer uma única pesagem, pondo nela quantas fichas quiser, dos sacos que quiser.
Como descobrir qual é o saco das fichas leves? Qual o menor número de fichas que você precisa pôr na balança?
Agora suponha que não se sabe quantos fornecedores estão desregulados. Pode ser nenhum, pode ser qualquer grupo deles, podem ser os oito, e as fichas de todo fornecedor desregulado pesam 11 g. Com uma única pesagem, como descobrir exatamente quais sacos são leves, e qual o menor número total de fichas na balança?
Dica
Cada ficha leve tira 1 g do total, então a pesagem devolve um único número, quantos gramas faltaram em relação ao peso esperado. Escolha quantas fichas tirar de cada saco de modo que cada situação possível produza uma falta diferente. Na segunda parte, comece contando quantas situações possíveis existem.
Solução completa
Primeira parte, um saco leve
Tire uma quantidade diferente de fichas de cada saco. A forma mais simples é tirar 1 ficha do saco 1, 2 do saco 2, e assim até 8 fichas do saco 8, \( 1 + 2 + \dots + 8 = 36 \), ou 36 fichas ao todo. Se todas fossem corretas, a balança marcaria \( 36 \cdot 12 = 432 \), ou 432 g. Cada ficha leve tira 1 g, então, se faltarem \( d \) gramas, o saco leve é o saco \( d \).
Dá para economizar. Uma das quantidades pode ser zero, porque não faltar nada também é uma informação. Tire 0 fichas do saco 8 e \( k \) fichas do saco \( k \), para \( k \) de 1 a 7. Se não faltar nada, o saco leve é o 8. São \( 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 \), ou 28 fichas.
Não dá para fazer com menos. Se dois sacos contribuírem com o mesmo número de fichas, a falta é a mesma quando um ou o outro é o leve, e a pesagem não os separa. As oito quantidades precisam ser diferentes entre si, e oito números inteiros diferentes, a partir de zero, somam pelo menos \( 0 + 1 + 2 + \dots + 7 = 28 \).
Segunda parte, qualquer grupo de sacos leves
Agora cada saco pode ser leve ou não, o que dá \( 2^{8} = 256 \), ou 256 situações possíveis, de nenhum saco leve até os oito. A falta precisa ser diferente em cada uma. Isso pede quantidades em que a soma de um grupo de sacos nunca coincida com a soma de outro grupo.
As potências de 2 fazem isso. Tire 1 ficha do saco 1, 2 do saco 2, 4 do saco 3, e assim por diante, dobrando, até 128 fichas do saco 8. A falta, escrita em base 2, diz quais sacos são leves, porque cada número inteiro tem uma única escrita em base 2. Uma falta de 37 g, por exemplo, é \( 32 + 4 + 1 \), e os sacos leves são o 6, o 3 e o 1. O total é \( 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255 \), ou 255 fichas, e cada saco tem fichas de sobra, porque o maior pedido é de 128 e cada saco tem 500.
Por que 255 é o mínimo
O argumento é de contagem. Se você puser \( N \) fichas na balança, a falta é um número inteiro entre 0 e \( N \), então só existem \( N + 1 \) leituras possíveis. Para separar 256 situações são necessárias pelo menos 256 leituras diferentes, ou seja \( N + 1 \ge 256 \), e \( N \ge 255 \). As potências de 2 atingem esse limite, então não existe esquema com menos fichas.
Na primeira parte, a contagem sozinha não basta. São só 8 situações, mas a leitura quando o saco \( k \) é o leve é exatamente a quantidade tirada dele, e por isso o limite que vale é o das oito quantidades diferentes. A segunda parte é uma codificação binária. Cada saco ganha um algarismo da base 2, e a pesagem lê o número inteiro de uma vez.
Resposta
- Com um saco leve, tire uma quantidade diferente de cada saco, de 0 a 7 fichas. Os gramas que faltam apontam o saco. O mínimo é de 28 fichas.
- Com qualquer grupo de sacos leves, tire 1, 2, 4 e assim por diante até 128 fichas, as potências de 2. A falta escrita em base 2 diz quais sacos são leves. O mínimo é de 255 fichas.
O que foi conferido e como
Os esquemas foram conferidos por força bruta sobre todos os casos. Com as quantidades de 0 a 7, e também com as de 1 a 8, as oito situações de um saco leve dão oito faltas diferentes. Com as potências de 2, as 256 situações possíveis dão 256 faltas diferentes, e a falta de 37 g aponta os sacos 1, 3 e 6. Os dois mínimos não são força bruta com oito sacos. Eles foram conferidos varrendo todas as escolhas possíveis de quantidades em versões menores do problema, de 1 até 7 sacos na primeira parte e de 1 até 5 na segunda. Com \( n \) sacos, o menor total que funciona foi sempre \( 0 + 1 + \dots + (n-1) \) na primeira parte e \( 2^n - 1 \) na segunda. Para oito sacos valem os dois argumentos da solução, que são os mesmos dessas versões menores. Os números do enunciado, os resultados da solução e o exemplo de 37 g, com as parcelas e os sacos, são lidos da página e comparados com essas contas, e as somas escritas nas fórmulas são refeitas.