(Acesso ao PROFMAT 2012 - Questão 9)
Seu João precisa pesar uma pera em uma balança de dois pratos. Ele possui $5$ pesos distintos, de $1\,$g, $3\,$g, $9\,$g, $27\,$g e $81\,$g. Seu João, equilibrando a pera com os pesos, descobriu que a pera pesa $61\,$g. Quais pesos estavam no mesmo prato que a pera?
Fiz uma edição mais enxuta do vídeo, extraindo apenas a parte da solução do problema, para facilitar os colegas interessados:
De fato, o que se faz no vídeo é resolver uma generalização deste problema, muito interessante por envolver uma representação alternativa dos inteiros na base $3$.
A generalização é a seguinte:
Prove que com o conjunto de pesos $\{1\,$g, $3\,$g, $9\,$g, $27\,$g, $81\,$g$\}$ é possível descobrir com exatidão o peso de qualquer objeto com peso $P$ em gramas inteiro de $1$ a $121$, utilizando uma balança de dois pratos, podendo-se colocar alguns pesos no mesmo prato que o objeto. A maneira de realizar esta pesagem é única para um dado valor de $P$.
De fato, os argumentos apresentados no vídeo são suficientes para ir um pouco mais além, considerando como conjunto de pesos as $n$ primeiras potências de $3$, começando de $3^0 = 1$, com o qual podemos pesar qualquer objeto com peso de $1$ até a soma dessas potências, $S_n = 1+3^1+3^2 + \cdots 3^{n-1}$.
Se somos capazes de equilibrar o objeto de peso $P$ na balança usando o conjunto de pesos do enunciado, então temos a igualdade
$$
P = \sum_{k=0}^{n-1} a_k \cdot 3^k = a_0 + a_1 \cdot 3^1 + a_2 \cdot 3^2 + \cdots + a_{n-1}\cdot 3^{n-1},
$$
na qual, para cada $k$, $a_k$ é igual a $0$, $-1$ ou $1$, se o peso de $3^k$ gramas está fora da balança, está no mesmo prato que o objeto de peso $P$, ou está no prato oposto, respectivamente.
Note a semelhança desta última igualdade com a representação de inteiros na base $3$. A única diferença é que em vez de usarmos os algarismos $0,1,2$ como possíveis valores dos coeficientes $a_k$, usamos os valores $-1,0,1$. Como $-1$ e $2$ diferem de $3$ unidades (em linguagem de congruências, $-1 \equiv 2 \pmod 3$), e o método tradicional para determinar a representação na base $3$ baseia-se nos restos de divisões sucessivas por $3$, é natural tentar utilizar este mesmo método, trocando os restos $2$ por restos $-1$. Vamos ver um exemplo diferente dos utilizados no vídeo, e, a seguir, daremos uma demonstração formal por indução.
Exemplo: $P = 413$. Dividindo $413$ por $3$ da maneira tradicional obteríamos quociente $137$ e resto $2$. Para substituir este resto por $-1$, consideramos o ``quociente" igual a $138$, já que $413 = 3 \times 138 - 1$. Isto significa que, na nossa representação alternativa em base $3$, o ``algarismo" das unidades será $a_0 = -1$. Traduzindo para a pesagem, concluímos que o peso de $1\,$g deverá ser colocado no mesmo prato que o objeto. Outra maneira de deduzir o mesmo seria observar que $413$ e $1$ são os únicos pesos não múltiplos de $3$, logo o efeito combinado de ambos deve ser múltiplo de $3$ para haver equilíbrio com os demais, e isso só pode ser obtido colocando-os juntos pois $414$ é múltiplo de $3$.
Seguindo o processo de divisões sucessivas, dividimos agora o quociente obtido, $138$, por $3$ e encontramos resto $0$ e quociente $46$. Isso significa que $a_1=0$, ou seja, o peso de $3\,$g deve ficar de fora da pesagem. Os próximos dois restos são $1$ e $0$ com quocientes $15$ e $5$, respectivamente. Agora, a divisão tradicional nos daria novamente resto $2$, logo fazemos nossa divisão alternativa e consideramos resto $-1$ e quociente $2$, finalizando com resto $-1$ novamente, e quociente $1$. Consolidando os resultados, obtemos
$$
(a_6, a_5, a_4, a_3, a_2, a_1, a_0) = (1, -1, -1, 0, 1, 0, -1).
$$
Ou seja, $413$ fosse é número de $7$ algarismos em nossa base $3$ modificada, e temos $413 = 3^6 -3^5-3^4 + 3^2 - 3^0$, ou seja, devemos colocar os pesos de $3^2$ e $3^6\,$g no prato oposto, e os pesos de $1$, $3^4$ e $3^5\,$g no mesmo prato do objeto.
Demonstração por Indução:
O resultado é válido para $n=1$. Supondo que seja válido para um certo valor de $n$, provemos que será válido para $n+1$. Para isso, seja $P$ tal que $S_n < P \leq S_{n+1}$. Existem inteiros $q$ e $r$ tais que $P = 3q+r$ e $-1\leq r \leq 1$ (Como no exemplo, se o resto da divisão de $P$ por $3$, é $2$, $r=-1$ e $q$ é igual ao quociente da divisão adicionado de uma unidade. Caso contrário, $q$ e $r$ são o quociente e o resto tradicionais da divisão de $P$ por $3$). Temos
$3q+r \leq S_{n+1}$, logo
$$
q \leq \dfrac{S_{n+1}}3 - \dfrac r3 = S_n + \dfrac 13 - \dfrac r3 \leq S_n + \dfrac 23.
$$
Mas $q$ deve ser inteiro, portanto $q \leq S_n$. Pela hipótese de indução, existem inteiros $a_0, a_1, \ldots, a_{n-1}$ tais que
$$
q = \sum_{k=0}^{n-1} a_k \cdot 3^k \;\; \mbox{e} \;\; a_k \in \{-1,0,1\}.
$$
Logo
$$
P = 3q + r = \sum_{k=0}^{n} b_k \cdot 3^k,
$$
com $b_k = a_{k-1}$ para $k=1, 2, \ldots, n$ e $b_0=r$, o que conclui a demonstração.
Agradecimento:
Muito obrigado ao blog "O Baricentro da Mente" por esta postagem que explica como escrever aqui no blogger usando fórmulas em LaTeX. Funciona para os comentários também!
http://obaricentrodamente.blogspot.com.br/2010/02/latex-no-blogger.html
