Re: [obm-l] Moedas em sacos

[Fábio Dias Moreira <fabio@xxxxxxxxxxxxxxxxxxx>]

Rogerio Ponce escreveu:
> 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
=========================================================================