Ola' Qwert, Bruno, Claudio e colegas da lista, o fato e' que N pode ser ainda maior que 927... [...]
Considere todos os ternos (p, q, r) de inteiros com |p|, |q|, |r| <= 10 e tais que mdc(p, q, r) = n (estou definindo mcd(x, 0) = |x|). Seja S o conjunto desses ternos. Eu afirmo que � poss�vel fazer o pedido com N = #S.
Para ver isso, fa�a uma bije��o entre os sacos e os ternos de S. Na i-�sima pesagem, coloque t_i moedas do saco associado a t no prato da direita (fa�a a coisa natural no caso t_i < 0). Como t pertence a S <=> -t pertence a S, a balan�a acusa um valor de t_i*d, onde d � a diferen�a de peso entre as moedas defeituosas. Logo as tr�s pesagens revelar�o o valor de t*d. Como d > 0 e as tr�s componentes de t s�o primas entre si, o mdc real entre as tr�s componentes de t � exatamente d, logo � poss�vel achar t.
Agora o problema � achar N. Pelo PIE, n�o � dif�cil ver que
#S = 21^3 - #T_2 - #T_3 - #T_5 - #T_7 + #T_6 + #T_10 + 1
onde #T_n � o conjunto dos ternos com norma do sup <= 10 e o mcd entre as componentes � um m�ltiplo de n.
Ent�o
#T_2 = 11^3 #T_3 = 7^3 #T_5 = 5^3 #T_6 = #T_7 = #T_10 = 3^3
Logo
N = #S_1 = 9261 - 1331 - 343 - 125 - 27 + 27 + 27 + 1 = 7490.
Isso tamb�m prova que, se todas as pesagens forem balanceadas, essa *�* a cota superior, logo basta provar que pesagens n�o-balanceadas n�o permitem ir al�m de um limite inferior a 7490.
(O meu racioc�nio est� certo? A contagem est� certa; eu conferi com um programinha em Python.)
[]s,
-- F�bio Dias Moreira
========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
