[obm-l] IMC - problema 4

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

4. Determine the set of all pairs (a,b) of positive integers for which the
set of positive integers can be decomposed into two sets A and B such that
a.A = b.B.

Seja N = conjunto dos inteiros positivos.

O enunciado fala em decompor N e não particionar N.
Pra mim, isso significa que devemos ter A U B = N, mas não necessariamente A
inter B = vazio.
Com essa interpretacao, eu fiz o seguinte:

Consideremos os pares da forma (a,ka), com k inteiro positivo.
Nesse caso, basta tomar A = kN e B = N para garantir que teremos:
A U B = N  e  aA = a(kN) = (ka)N = (ka)B.

De forma analoga, podemos tomar todos os pares da forma (kb,b), com k
inteiro positivo.

Suponhamos agora que algum par (a,b) satisfaz ao enunciado sem que tenhamos
a | b ou b | a.
Isso significa que d < a  e  d < b, onde d = mdc(a,b).
Podemos escrever a = a1*d e b = b1*d, com mdc(a1,b1) = 1.

Sejam os conjuntos correspondentes A e B tais que A U B = N  e  aA = bB.

aA = bB ==>
a1*d*A = b1*d*B ==>
a1*A = b1*B

Podemos supor s.p.d.g. que 1 pertence a A.
Nesse caso, a1 pertence a a1*A ==>
a1 pertence a b1*B ==>
existe m em B tal que a1 = b1*m ==>
b1 | a1 ==>
b1 = 1 (ja que mdc(a1,b1) = 1).

Mas, b1 = 1 ==>
a = a1*d, b = b1*d = d ==>
b divide a ==>
contradicao

Logo, se a nao divide b e b nao divide a, entao (a,b) nao satisfaz ao
enunciado.

Conclusao: os unicos pares ordenados de inteiros positivos que satisfazem ao
enunciado sao aqueles nos quais uma das coordenadas eh um multiplo da outra.


Um abraco,
Claudio. 
=========================================================================
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
=========================================================================