[obm-l] 3 Problemas

[Cláudio \(Prática\)]

1)O produto de 2001 inteiros positivos distintos possui exatamente 2000 divisores primos distintos. Mostre que podemos escolher alguns destes 2001 números de modo que seu produto seja um quadrado perfeito.   Cada um dos 2001 inteiros pode ser escrito da seguinte forma: N = P1^X1 * P2^X2 * ... * P2000^X2000, onde os Pi's são primos distintos e os Xi's inteiros não negativos.   N é quadrado perfeito <==> cada Xi é par   Podemos representar cada um dos 2001 inteiros por um vetor de 2000 componentes, onde a i-ésima componente é 0 se Xi for par e 1 se Xi for ímpar.   Com esta representação, multiplicar dois dos inteiros equivale a somar os dois vetores correspondentes (mod 2) (ou seja, 0 + 0 = 1 + 1 = 0  e  1 + 0 = 0 + 1 = 1).   Consideremos os seguintes casos: CASO 1: Algum dos 2001 vetores é o vetor nulo (todas as componentes = 0) ==> o N correspondente é quadrado perfeito ==> o problema está resolvido.   CASO 2: Nenhum dos 2001 vetores é o vetor nulo, mas existem dois vetores iguais ==> a soma destes dois vetores é o vetor nulo ==> o produto dos dois inteiros correspondentes é quadrado perfeito ==> o problema está resolvido   CASO 3: Nenhum dos 2001 vetores é o vetor nulo e os vetores são distintos dois a dois.   Nesse caso, o número de subconjuntos não-vazios do conjunto de 2001 vetores é igual a 2^2001 - 1. Como cada vetor tem 2000 componentes e cada componente pode ser 0 ou 1, o número total de vetores distintos é igual a 2^2000 < 2^2001 - 1.   Logo, pelo princípio das gavetas, devem existir dois subconjuntos distintos de vetores tais que a soma de seus elementos (mod 2) é a mesma.   Suponhamos que os subconjuntos sejam: {U1, U2, ..., Ur, V1, V2, ..., Vs}  e  {U1, U2, ..., Ur, W1, W2, ..., Wt}', onde os cada Vi é diferente de cada Wj.   Somas iguais (mod 2) ==> U1 + ... + Ur + V1 + ... + Vs = U1 + ... + Ur + W1 + ... + Wt (mod 2) ==> V1 + ... + Vs = W1 + ... + Wt  (mod 2) ==> V1 + ... + Vs + W1 + ... + Ws = 0  (mod 2) ==> o produto dos (s+t) inteiros correspondentes aos Vi's e aos Wj's é quadrado perfeito ==> o problema está resolvido.   *************** 2)Determine n pertencente aos naturais tais que n^2+2 divida 2+2001n.   Inicialmente, temos que: n^2 + 2 <= 2 + 2001n ==> n^2 - 2001n <= 0 ==> 0 <= n <= 2001.   n = 1 ou 2 (mod 3) ==> n^2 + 2 = 0 (mod 3)  e  2 + 2001n = 2 (mod 3)  ==> 3 divide n^2 + 2  e  3 não divide 2 + 2001n ==> n^2 + 2 não divide 2 + 2001n ==> n = 0 (mod 3) (necessariamente) ==> n = 3m com m natural e 1 <= m <= 667   n^2 + 2 divide 2 + 2001n ==> n^2 + 2 divide (2 + 2001n) - (n^2 + 2) ==> n^2 + 2 divide n(2001 - n)   n = 3m ==> 9m^2 + 2 divide 3m(2001 - 3m)  ==> 9m^2 + 2 divide 9m(667 - m)   MDC(9m^2 + 2,9) = MDC(2,9) = 1 ==> 9m^2 + 2 divide m(667 - m)   CASO 1: m é par ==> m = 2p (1 <= p <= 333) ==> 36p^2 + 2 divide 2p(667 - 2p) ==> 18p^2 + 1 divide p(667 - 2p)   MDC(18p^2 + 1,p) = MDC(1,p) = 1 ==> 18p^2 + 1 divide (667 - 2p) ==> 18p^2 + 1 <= 667 - 2p ==> 18p^2 + 2p - 666 <= 0 ==> 9p^2 + p - 333 <= 0 ==> 1 <= p <= 6   Testando estes 6 valores possíveis de p, achamos que apenas p = 1 satisfaz a condição de divisibilidade ==> m = 2 ==> n = 6   ------------------------------   CASO 2: m é ímpar ==> m = 2p+1 (1 <= p <= 333) ==> 36p(p + 1) + 11 divide (2p+1)(667 - 2p - 1) ==> 36p(p + 1) + 11 divide 2(2p + 1)(333 - p)   36p(p + 1) + 11 é ímpar ==> 36p(p + 1) + 11 divide (2p + 1)(333 - p) ==> p = 333   ou   36p(p + 1) + 11 <= (2p + 1)(333 - p)  ==> p = 333   ou   38p^2 - 297p - 322 <= 0  ==> p = 333   ou   1 <= p <= 8   p = 333 ==> m = 667 ==> n = 2001   Testando os outros 8 valores possíveis de p, achamos que apenas p = 1 satisfaz a condição de divisibilidade ==> m = 3 ==> n = 9   Assim, os únicos naturais n tais que n^2 + 2 divide 2 + 2001n são 6, 9 e 2001.   OBS: Se 0 for considerado natural, então claramente n = 0 também é solução.     ****************   3)Para os inteiros positivos x e y é verdadeira a igualdade 3x^2 + x= 4y^2+y. Mostre que x-y é um quadrado perfeito.   Inicialmente, temos que x > y, pois se x <= y, então 3x^2 + x <= 3y^2 + y < 4y^2 + y ==> contradição   Suponhamos que MDC(x,y) = d. Então: x = a*d  e  y = b*d  com MDC(a,b) = 1   Como x > y, temos que a > b ==> (a - b) <> 0   3a^2d^2 + ad = 4b^2d^2 + bd  ==> 3a^2d + a = 4b^2d + b ==> 3a^2d - 3b^2d + a - b = b^2d ==> 3d(a - b)(a + b) + (a - b) = b^2d ==> (a - b)[3d(a + b) + 1] = b^2d ==> (a - b) divide b^2d   Mas MDC(a - b,b^2) = 1 ==> (a - b) divide d ==> d = k(a - b) ==> (a - b)[3k(a - b)(a + b) + 1] = b^2k(a - b) ==> 3k(a^2 - b^2) + 1 = b^2k  ==> k(4b^2 - 3a^2) = 1 ==> k divide 1 ==> k = 1 ==> d = a - b   Mas nesse caso: x = da = (a - b)a = a^2 - ab y = db = (a - b)b = ab - b^2   Assim: x - y = a^2 - 2ab + b^2 = (a - b)^2 ==> quadrado perfeito.   *******************   Um abraço, Claudio.