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 =========================================================================