AD1-A1-2013-1-Gabarito

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