Nesse caso decompor e a mesma coisa q
particionar... varias pessoas perguntaram na hora da prova, e isso foi
confirmado...
E alem disso, vc deveria mostrar a reciproca do q vc
provou, ou seja, q se um dos numeros 'e multiplo do outro, entao vc consegue
A e B com as propriedades
pedidas.
Abracos
Villard
--------- Mensagem Original
--------
De: obm-l@mat.puc-rio.br
Para: "Lista OBM"
<obm-l@mat.puc-rio.br>
Assunto: [obm-l] IMC - problema 4
Data:
28/07/03 19:03
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
=========================================================================