Baixe o app para aproveitar ainda mais
Prévia do material em texto
A´lgebra I AD1 - Primeira Avaliac¸a˜o a Distaˆncia - Aulas 1 a 7 1a Questa˜o: (2, 0 pontos) Determine uma condic¸a˜o necessa´ria e suficiente para que se tenha A ∪ (B ∩ C) = (A ∪B) ∩ C, onde A, B e C sa˜o conjuntos quaisquer. Soluc¸a˜o: Para que ocorra a igualdade deveremos ter A∪(B ∩ C) ⊂ (A ∪B)∩C e (A ∪B)∩ C ⊂ A ∪ (B ∩ C). Vejamos que condic¸a˜o deve ser imposta para que tenhamos a primeira das incluso˜es. Tomando um elemento arbitra´rio, digamos x, pertencente ao conjunto A∪(B ∩ C) temos que x ∈ A ou x ∈ B ∩C. Se x ∈ B ∩C enta˜o x ∈ B e x ∈ C e portanto x ∈ A∪B e x ∈ C, logo x ∈ (A ∪B) ∩ C. Agora se x ∈ A para que tenhamos x ∈ (A ∪B) ∩ C devemos impor que x ∈ C, ou seja, para todo x tomado em A devemos ter que x pertence a C, dessa forma a condic¸a˜o procurada e´ que A ⊂ C. Note ainda que a inclusa˜o contra´ria vale sempre, de fato, tomando x ∈ (A ∪B) ∩ C temos que x ∈ A ∪ B e x ∈ C. Como x ∈ A ∪ B enta˜o x ∈ A ou x ∈ B. Se x ∈ A enta˜o x ∈ A ∪ (B ∩ C). Se x ∈ B, como ele tambe´m esta´ em C, enta˜o x ∈ B ∩ C e assim x ∈ A ∪ (B ∩ C). Resumindo temos que, A ⊂ C se, e somente se, A ∪ (B ∩ C) = (A ∪B) ∩ C. 2a Questa˜o: a) (1, 0 ponto) Um rei muito rico possui 3n moedas de ouro. Pore´m, uma destas moedas e´ falsa e seu peso e´ menor que o peso das demais. Com uma balanc¸a de 2 pratos e sem nenhum peso, mostre que e´ poss´ıvel encontrar a moeda falsa com apenas n pesagens. b) (1, 0 ponto) Prove que H2n ≥ 1 + n 2 , para n ≥ 0. Hj representa o nu´mero harmoˆnico e e´ definido por Hj = 1 + 1 2 + 1 3 + ...+ 1 j . 1 Soluc¸a˜o: a) Vamos utilizar o Princ´ıpio de Induc¸a˜o finita. Para n = 1 temos 3 moedas. Para de- scobrirmos a moeda mais leve basta pegarmos qualquer duas das treˆs moedas e pormos na balanc¸a. Se os pratos ficarem em equil´ıbrio a moeda que ficou de fora e´ a moeda procurada. Caso os pratos se desequilibrem a moeda mais leve e´ a que esta´ no prato mais elevado. Em qualquer um dos casos com apenas uma pesagem determinamos a moeda mais leve. Como hipo´tese de induc¸a˜o vamos admitir que com 3n moedas n pesagens sa˜o suficientes para determinarmos a moeda mais leve. Provemos agora o passo indutivo, isto e´, com 3n+1 moedas necessitamos de n + 1 pesagens para determinarmos a moeda mais leve. Note que 3n+1 = 3 · 3n = 3n + 3n + 3n. Temos portanto treˆs grupos, cada um dos quais com 3n moedas. Se pegarmos quaisquer dois desses grupos e colocarmos cada um em um dos pratos da balanc¸a teremos as seguintes possibilidades: Equil´ıbrio na balanc¸a - Neste caso a moeda mais leve esta´ no grupo que ficou de fora da pesagem. Como este grupo possui 3n moedas, pela nossa hipo´tese de induc¸a˜o, com n pesagens descobriremos a moeda mais leve. Como ja´ tinhamos efetuado uma pesagem temos um total de n+ 1 pesagens. Desequil´ıbrio na balanc¸a - Nesta situac¸a˜o o grupo que esta´ no prato mais elevado e´ o que possui a moeda mais leve e nesse caso, usando a nossa hipo´tese de induc¸a˜o, com mais n pesagens determinamos a moeda mais leve, ou seja, tambe´m foram necessa´rias n+1 pesagens para alcanc¸armos nosso objetivo. b) Para n = 0 temos que H20 = H1 = 1 ≥ 1 + 0 2 = 1 o que esta´ OK. Vamos admitir que para n = k vale que H2k ≥ 1 + k 2 . Provemos que o resultado permanece va´lido para n = k + 1. De fato, H2k+1 = H2·2k = 1 + 1 2 + ...+ 1 2k + 1 2k + 1 + 1 2k + 2 + ...+ 1 2k+1︸ ︷︷ ︸ 2k termos ≥ ≥ 1 + k 2 + 1 2k + 1 + 1 2k + 2 + ...+ 1 2k+1 ≥ 1 + k 2 + 2k · 1 2k+1 = 1 + k + 1 2 . 2 Note que na u´ltima passagen acima usamos que 1 2k + 1 ≥ 1 2k+1 , 1 2k + 2 ≥ 1 2k+1 ,... e o fato de termos a presenc¸a de 2k termos. Portanto segue do Princ´ıpio de Induc¸a˜o Finita o resultado desejado. 3a Questa˜o: (2, 0 pontos) Deseja-se pesar qualquer nu´mero inteiro de gramas de ouro, entre 1g e 100g, numa balanc¸a de dois pratos, onde os pesos so´ podem ser usados no prato esquerdo da balanc¸a. Mostre que a escolha adequada de 7 pesos diferentes e´ suficiente para realizar esta tarefa. Sugesta˜o: Use o sistema de numerac¸a˜o em base 2. Soluc¸a˜o: Basta notar que qualquer nu´mero a compreendido entre 1 e 100 pode ser repre- sentado na base 2 como a = α0 + α12 1 + α22 2 + α32 3 + α42 4 + α52 5 + α62 6. Nossa representac¸a˜o parou em 26 porque 27 = 128 > 100. Dessa forma necessitamos apenas dos pesos 20, 21, 22, 23, 24, 25 e 26. Observamos ainda que como αi ∈ {0, 1} i = 0, 1, 2, ..., 6 os pesos na˜o se repetem. 4a Questa˜o: (2, 0 pontos) Um retaˆngulo de lados inteiros AB = m e BC = n, e´ dividido em quadrados de lado 1. Em cada um dos ve´rtices ele possui um pequeno orif´ıcio. Um raio de luz entra no retaˆngulo por um dos ve´rtices, na direc¸a˜o da bissetriz do aˆngulo reto, e e´ refletido sucessivamente nos lados do retaˆngulo. Quantos quadrados sa˜o atravessados pelo raio de luz? Justifique sua resposta. Soluc¸a˜o: E´ importante fazermos alguns testes preliminares dando valores a m e n, assim veremos que em cada caso a resposta coincidira´ com o mmc (m,n). Vamos provar que de fato isto vale para m e n quaisquer. Vamos fazer algumas observac¸o˜es: • Cada vez que um raio de luz atravessa um quadrado ele avanc¸a uma unidade tanto na direc¸a˜o horizontal como na direc¸a˜o vertical. 3 • Se o raio entra pelo ve´rtice A, tera´ que atravessar m quadrados ate´ chegar ao lado BC, imediatamente mais m para chegar ao lado AD, depois mais m para chegar novamente ao lado BC, e assim sucessivamente. Ale´m disso, depois do raio percorrer pm quadrados, com p ∈ N, estara´ batendo no lado BC ou no lado AD. Fac¸a uma figura!!!! • De modo ana´logo o raio batera´ no lado DC se, e somente se, atravessar qn quadrados, com q ∈ N. • Somente nos ve´rtices B,C e D do retaˆngulo pode acontecer que o raio incidente saia do retaˆngulo, terminando assim o processo de reflexa˜o. Temos que o raio chegara´ a um ve´rtice quando chegar simultaneamente a dois lados perpendiculares do retaˆngulo. Portanto, deve ter atravessado um nu´mero x de quadrados tal que x = pm = qn, ou seja, x devera´ ser um mu´ltiplo comum de m e n. A primeira vez que o raio chega a um ve´rtice sera´ o nu´mero x dado pelo menor mu´ltiplo comum de m e n, isto e´, x = mmc (m,n). 5a Questa˜o: (2, 0 pontos) Considere o conjunto A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} . E´ poss´ıvel decompor o conjunto A em dois subconjuntos disjuntos tais que o produto dos elementos de um seja igual ao produto dos elementos do outro? Justifique sua resposta. Soluc¸a˜o: Se uma tal decomposic¸a˜o fosse poss´ıvel deveriam existir conjuntosA1 = {p1, p2, p3, ..., pr} e A2 = {q1, q2, ..., qs} de modo que p1 · p2 · ... · pr︸ ︷︷ ︸ α = q1 · q2 · ... · qs︸ ︷︷ ︸ β . Como A1 e A2 sa˜o disjuntos temos que o nu´mero 7 aparece no produto α ou no produto β, mas na˜o em ambos simultaneamente. Mas pelo Teorema Fundamental da Aritme´tica a fatorac¸a˜o em primos de α e´ igual a fatorac¸a˜o em primos de β e sendo assim o 7 deveria aparecer tanto em α quanto em β o que gera uma contradic¸ao! Portanto, com as condic¸o˜es exigidas tal decomposic¸a˜o na˜o e´ poss´ıvel. 4
Compartilhar