[obm-l] Re: [obm-l] Problema dos Remédios

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

 

De:	owner-obm-l@mat.puc-rio.br

Para:

obm-l@mat.puc-rio.br

Cópia:

Data:

Wed, 8 Mar 2006 07:19:24 -0300

Assunto:

Re: [obm-l] Problema dos Re médios

> Há 10 caixas de um tipo de remédio, cada caixa com 100 comprimidos, cada

> comprimido pesando 10g.

> Algumas destas caixas (você não sabe quantas nem quais) são oriundas

> de um lote defeituoso, onde os comprimidos pesam 9 g.

> Você tem acesso a uma balança digital, que só pode ser usada uma vez, e tem

> precisão suficiente para lhe dar o resultado exato de qqr pesagem com esses

> remédios.

>

> Qual a sua estratégia de pesagem para determinar, com certeza, exatamente

> quais caixas de remédio são defeituosas?

>

> []s, N.

>

>

 

Ou seja, temos uma sequência a_0, a_1, ..., a_9 tal que a_i = 0 ou a_i = 1.

Precisamos determinar uma segunda sequência de inteiros positivos b_0, b_1, ..., b_9 tal que a expressão:

N = SOMA(i = 0 ... 9) a_i*b_i

nos permita determinar para quais índices i temos a_i = 0.

 

Usando a unicidade da representação binária de um inteiro, podemos tomar:

b_i = 2^i.

Ou seja, N = a_0 + 2*a_1 + 4*a_2 + ... + 512*a_9.

 

Se a_i1, a_2, ... a_ir forem iguais a 1, então:

N = 2^i1 + 2^i2 + ... + 2^ir e é univocamente determinado.

 

No caso das caixas, após numerar os lotes de 0 a 9, colocamos simultaneamente 2^k caixas do lote k na balança (0 <= k <= 9) e subtraimos

9*(1 + 2 + 4 + ... + 512) = 9207 do valor indicado no mostrador.

O resultado é um dado N que determina univocamente as caixas normais (e, portanto, as defeituosas).

 

[]s,

Claudio.