Estou supondo que os pratos, quando vazios, tem massas iguais.
Basicamente, depois que voce decidir onde coloca os pesos x1, x2 e x3 e
equilibrar a balanca, voce vai descobrir que a massa m eh
m=c1.x1+c2.x2+c3.x3 onde c1, c2, c3 estao no conjunto {-1,0,1} (ci=-1
significa que o peso xi estah no mesmo prato que a massa m, ci=1 significa
peso xi no outro prato, ci=0 significa que nao usamos aquele peso xi).
Note que ha 3^3=27 possiveis escolhas dos coeficientes, mas eu vou
coloca-las aos pares: para cada escolha {c1,c2,c3} ha uma escolha
{-c1,-c2,-c3}. Norte que, com isso, para cada combinacao que dah m, eu
arrumo uma combinacao que dah -m, o que indica que metade das combinacoes
sao inuteis (massas negativas nao existem) -- bom, para ser exato, 13
combinacoes dao massas negativas, jah que c1=c2=c3=0 fica pareada consigo
mesma e dah massa 0. Assim, das 27 combinacoes, (pelo menos) uma dah 0, e ha
no maximo 13 que determinam massas positivas, pois outras 13 determinam
menos os resultados daquelas primeiras 13 (nota: se os pesos forem mal
escolhidos, algumas dessas 13 podem dar 0 e voce perde opcoes!).
Problema 1: Creio que nao ha uma resposta para o primeiro problema! Se fosse
m variando de 1 a 13, eu acreditava que dava, mas 1 a 21, nao vejo como! O
raciocinio acima explica o porque de soh termos no maximo 13 valores
positivos possiveis de m.
Problema 2: O raciocinio acima mostra que m=13. Para m variando de 1 a 13,
podemos usar massas de 1, 3 e 9 gramas. Fica ai como exercicio ver que todo
numero de 1 a 13 pode ser escrito como combinacao de 1, 3 e 9, possivelmente
com sinais negativos. De qualquer forma, o proximo problema eh o caso geral
e inclui n=3.
Problema 3: A generalizacao do raciocinio acima mostra que, com n massas,
ha, no maximo, (3^n-1)/2 massas positivas que podem ser aferidas. Afirmo que
eh possivel aferir todos os numeros de 1 a (3^n-1)/2 usando os seguintes n
pesos: 1, 3, 9, 27, ..., 3^(n-1).
Para tanto, vou mostrar que combinacoes de coeficientes distintas tem que
dar numeros distintos, ou seja, a funcao f:{-1,0,1}^n em Z dada por
f(c1,c2,c3,...,cn)=c1.1+c2.3+c3.9+...+.cn.3^(n-1) eh injetiva. Afinal, se
dois estados da balanca dessem o mesmo peso, teriamos c1.1+c2.3+...+cn.3^n =
d1.1+d2.3+...+dn.3^n, onde cada ci e cada di sao -1, 0 ou 1. Seja m o maior
indice possivel onde cm dm, ou seja, suponha c(m+1)=d(m+1) e
c(m+2)=d(m+2), etc. Cortando estes caras iguais dos dois lados, fico com:
c1.1+c2.3+...+cm.3^m = d1.1+d2.3+...+dm.3^m
(dm-cm).3^m = (c1-d1).1+(c2-d2).3+...+(cm-dm).3^(m-1)
Agora, o cara do lado esquerdo eh, em modulo, PELO MENOS 3^m, jah que
|cm-dm|=1. O cara do lado direito eh, em modulo, NO MAXIMO,
2.1+2.3+...+2.3^(m-1)=3^m-1. Entao eles nao podem ser iguais! ABSURDO! O
absurdo eh supor que cmdm para algum m; o unico jeito de combinacoes
destes numeros serem iguais eh se cada cm for igual a cada dm!
Entao as 3^n combinacoes distintas dos coeficientes c1, c2, ..., cn levam a
3^n resultados distintos da funcao f. Mas o resultado minimo eh botar
todos os coeficientes cn iguais a -1, que dah -1-3-9-...-3^n=-(3^n-1)/2; o
resultado maximo eh 1+3+9+...+3^n=(3^n-1)/2. Todos os resultados tem que ser
inteiros, e ha exatamente 3^n inteiros entre este minimo e aquele maximo
(incluindo 0, que corresponde a botar todo mundo igual a 0). Conclusao:
todos os inteiros tem de estar na imagem de f, isto eh, todas as massas m
entre -(3^n-1)/2 e (3^n-1)/2 podem ser medidas. Bom, as massas negativas nao
existem (se existissem, a gente as determinava!), mas todas as positivas
ainda podem ser determinadas.
Abraco,
Ralph
2008/9/24 Tarso Moura Leitão [EMAIL PROTECTED]
Caro professor Ralph, caso consiga algum tempinho gostaria muito de ver
algum comentário seu sobre os problemas enviados de Haifa ( Israel ) por um
professor
bem velhinho.
Antecipadamente agradeço.
Tarso de Moura Leitão
Todos os problemas se dão em uma balança de braços iguais.
Primeiro - Num dos pratos da balança foi colocado um objeto cuja massa m é
um número interiro de gramas, com m entre 1 e 21, inclusive.
Existem três massas aferidas de x, y e z gramas com as quais ( e com a
balança ) consegue-se determinar a massa m. Encontre x, y e z.
Segundo: Considere, novamente, o objeto de massa m, agora m é um dos
seguintes números inteiros:
1,2,3,...,M - 1, M.. Qual o valor máximo de M para que ainda seja
possível determinar o valor de m usando três massas aferidas de x, y e z
gramas ? Determine também x,y e z e exiba um procedimento para obter o valor
máximo M.
Terceiro - É dado que m é um dos números inteiros
1,2,3,,M - 1, M. Qual o valor máximo de M para que seja possível
calcular m usando n massas aferidas ?
Nos itens anteriores tínhamos apenas três massas aferidas.
( Nos enunciado recebido do professor Bloh não há condições impostas sobre
o número n, parece razoável buscar o menor n.)
