7 - LogicaMD_07_Exerc_Apoio_2

Prévia do material em texto

7
Lógica e matemática 
discreta
EXERCÍCIO DE APOIO 2
Escolher dois entre os quatro exercícios para entregar, 
valendo 5 pontos cada.
exercício 1
Mostre que, para todo inteiro n ≥ 6, vale a seguinte igual-
dade (referente à soma de números ímpares):
11 + 13 + ... + (2n - 1) = n2 - 25
Siga os passos abaixo para fazer uma prova por indução.
a. Passo Inicial: mostre que a igualdade vale para n = 6.
b. Passo de Indução: suponha que a igualdade seja
verdadeira para um certo n = k ≥ 6, e mostre que a
igualdade vale para n = k + 1.
c. Conclua o exercício.
exercício 2
Dado o conjunto A = {1, 2, 3, …, 24, 25}, serão formados 
dois subconjuntos, B e C de forma que |B| = 10 e |C| = 7.
a. De quantas maneiras podemos formar o subcon-
junto B?
Lógica e Matemática Discreta / Aulas 25–28 Atividade para Avaliação 2
b. De quantas maneiras podemos formar os dois subconjuntos, C e B, 
de modo que C ∩ B = ∅? 
c. De quantas maneiras podemos formar os dois subconjuntos, C e B, 
se não há restrição sobre a intersecção entre eles?
Os números são muito grandes. Deixe a resposta indicada na forma de 
produtos de fatoriais, se preferir.
exercício 3
Quantos números de 4 algarismos distintos podemos formar de modo 
que os dois últimos dígitos sejam ambos pares?
exercício 4
a. Escreva os números que faltam na expansão do binômio:
(a - 2b)5 = a5 - 10a4b + 40a3b2 - a2b3 + 80ab4 - b5.
b. Determine se cada sentença abaixo é verdadeira ou falsa.
I. ∀x∈ℕ, (x > 10 ou x ≤ 2) ⇔ (x2 ≤ 8 ou x2 ≥ 115)
II. Dados A e B conjuntos finitos, se |A|<|B|, então A ⊂ B.
III. Dados A e B conjuntos finitos, se A ⊂ B, então P(A) ⊂ P(B).
IV. Dado A conjunto finito, vale que |P(A)| >|A|.
Lógica e Matemática Discreta / Aulas 25–28 Atividade para Avaliação 3
Gabarito
exercício 1
Vamos mostrar que vale a igualdade
11 + 13 + ... + (2n - 1) = n2 - 25 (*)
para todo inteiro n ≥ 6.
a. Passo Inicial:  a igualdade vale para n = 6.
Com n = 6, o lado esquerdo da igualdade tem somente um somando: 11.
O lado direito fica 62 - 25 = 11.
Conclusão: a igualdade (*) vale para n = 6.
b. Passo de Indução:  Vamos supor que a igualdade (*) seja verdadei-
ra para um certo n = k ≥ 6. Ou seja, vamos supor que:
11 + 13 + ... + (2k - 1) = k2 - 25
Somando (2(k + 1) - 1) = 2k + 1 a ambos os lados da igualdade, ob-
temos:
11 + 13 + ... + (2k - 1) + (2k + 1) = k2 - 25 + 2k + 1 = (k + 1)2 - 25,
o que mostra que vale a igualdade (*) para n = k + 1 e conclui a pro-
va do passo de indução.
c. Usando o Princípio da Indução Finita, concluímos que a igualdade (*) 
vale para todo inteiro n ≥ 6.
exercício 2
A = {1, 2, 3, …, 24, 25} ⇒ | A | = 25
| B | = 10 e | C | = 7.
a. 25
10
 =  25!
10!15!
 = 3.268.760
b. Há duas escolhas sucessivas a serem realizadas. 
 → Escolher os 10 elementos de B: pode ser feito de 25
10
 modos.
Lógica e Matemática Discreta / Aulas 25–28 Atividade para Avaliação 4
 → Escolher os 7 elementos de C (entre os 15 elementos que resta-
ram): pode ser feito de 15
7
 maneiras.
O números de maneiras distintas de formar os dois subconjuntos, B 
e C, de modo que sejam disjuntos, é o produto:
25
10
 15
7
 = 
25!
10!15!
⋅ 15!
7!8!
 = 
25!
10!7!8!
 = 21.034.470.600
c. Há duas escolhas sucessivas a serem realizadas. 
 → Escolher os 10 elementos de B (entre os 25 elementos de A): pode 
ser feito de 25
10
 modos.
 → Escolher os 7 elementos de C (entre os 25 elementos de A): pode 
ser feito de 25
7
 maneiras.
O números de maneiras distintas de formar os dois subconjuntos, B 
e C, é o produto:
25
10
 25
7
 = 
25!
10!15!
⋅ 25!
7!18!
 = 1.571.292.932.000
exercício 3
Há as seguintes restrições:
1. o primeiro algarismo não pode ser 0;
2. os dois últimos algarismos devem ser ambos pares.
A contagem deverá ser separada em dois casos pois a escolha de 0 como 
último ou penúltimo algarismo muda o número de escolhas possíveis 
para o primeiro.
I. Contar os números de 4 algarismos distintos, com os dois últimos 
algarismos ambos pares e com um deles sendo zero.
 → Para os dois últimos algarismos temos as seguintes possibilidades: 02, 
04, 06, 08 ou 20, 40, 60, 80. São 8 escolhas para os últimos dois números.
Lógica e Matemática Discreta / Aulas 25–28 Atividade para Avaliação 5
 → Escolhidos os últimos dois números, restam 8 escolhas para o pri-
meiro (não pode ser igual a nenhum dos dois últimos).
 → Escolhidos os dois últimos e o primeiro, restam 7 escolhas para o 
segundo.
— — — —
8 7 8
O total de escolhas é 8 × 7 × 8 = 448.
II. Contar os números de 4 algarismos distintos, sendo os dois últimos 
ambos pares e ambos diferentes zero.
 → Para o último algarismo há 4 escolhas: 2, 4, 6 ou 8.
 → Para o penúltimo algarismo há 3 escolhas: 2, 4, 6 ou 8, mas não 
pode ser igual ao já escolhido como último algarismo.
 → Para o primeiro algarismo há 7 escolhas: de 0 a 9, mas não pode 
ser 0 e não pode ser nenhum dos dois já escolhidos.
 → Para o segundo algarismo há também 7 escolhas: de 0 a 9 mas 
não pode ser igual a nenhum dos três já escolhidos.
— — — —
7 7 3 4
Total de escolhas é 7 × 7 × 3 × 4 = 588.
A resposta ao problema proposto é a soma dos números obtidos em 
cada caso: 448 + 588 = 1.036.
exercício 4
a. -80 e -32
(a - 2b)5 = a5 - 10a4b + 40a3b2 - 80 a2b3 + 80ab4 - 32 b5.
b. 
I. Verdadeira.
II. Falsa. A e B poderiam ser, por exemplo: A = {1} e B = {4, 5}.
III. Verdadeira. Se A⊂B, todo subconjunto de A é também um sub-
conjunto de B.
IV. Verdadeira. Sabemos que a cardinalidade de P(A) é | P(A) | = 2|A|.
E é verdade que 2n > n para todo natural n.