[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Re: [obm-l] IMC - problema 4




 Vou dar minha solução: eu considerei AUB=N partição. 
  Sejam a, b tais que 
 a.A= b.B.
  Podemos supor, WLOG, que 1 está em A. Então a está em B, de modo que existe
d em B tal que a=b.d. Temos então que b|a, e ainda  aA=db.A => d.A=B. 
 Nosso problema se restringiu então a acharmos d natural tal que d.A=B,
onde AUB é alguma partição de N. Afirmo que todo d satisfaz tal condição.
De fato, cada natural n é representado de modo único na forma d^a.c, onde
d não divide c. Seja então
  A= {d^a.c ; a é par e d não divide c}
  B= {d^a.c ; a é ímpar e d não divide c}
 Claramente AUB= N e d.A=B. 
 Logo, os pares (a,b) que satisfazem são os que satisfazem mdc(a, b)=min{a,
b}.
  Se virem algum erro, me avisem!!

-- Mensagem original --

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

[]'s, Yuri
ICQ: 64992515


------------------------------------------
Use o melhor sistema de busca da Internet
Radar UOL - http://www.radaruol.com.br



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