Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 60 visualizações

    MD21d T1cor

    Enviado por

    Eduardo Mário Timana
    1) O documento apresenta o guião de correção de um teste de matemática discreta com 6 questões. 2) As questões abordam tópicos como conjuntos, combinatória, sucessões recursivas e indução matemática. 3) As respostas são justificadas usando métodos como diagramas de Venn, princípio do produto, equações características e princípio da indução matemática.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd

    MD21d T1cor

    Enviado por

    Eduardo Mário Timana
    60 visualizações3 páginas
    1) O documento apresenta o guião de correção de um teste de matemática discreta com 6 questões. 2) As questões abordam tópicos como conjuntos, combinatória, sucessões recursivas e indução matemática. 3) As respostas são justificadas usando métodos como diagramas de Venn, princípio do produto, equações características e princípio da indução matemática.

    Título original

    MD21d_t1cor

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    1) O documento apresenta o guião de correção de um teste de matemática discreta com 6 questões. 2) As questões abordam tópicos como conjuntos, combinatória, sucessões recursivas e indução matemática. 3) As respostas são justificadas usando métodos como diagramas de Venn, princípio do produto, equações características e princípio da indução matemática.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    60 visualizações3 páginas

    MD21d T1cor

    Enviado por

    Eduardo Mário Timana
    1) O documento apresenta o guião de correção de um teste de matemática discreta com 6 questões. 2) As questões abordam tópicos como conjuntos, combinatória, sucessões recursivas e indução matemática. 3) As respostas são justificadas usando métodos como diagramas de Venn, princípio do produto, equações características e princípio da indução matemática.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    Você está na página 1de 3

    Faculdade de Ciências

    Departamento de Matemática e Informática


    Licenciatura em Ciências de Informação Geográca, Laboral
    10 Teste de Matemática Discreta I. Guião da Correcção.

    Duração: 110 minutos 03.07.2021

    Todas as respostas têm que ser justicadas!

    1. Uma turma de 40 pessoas estuda Álgebra e Geometria. 12 estudantes da turma não gostam
    de Álgebra nem de Geometria, 20 estudantes gostam de Álgebra, e 23 estudantes gostam de
    Geometria.
    (a) (1.5 valores) Quantos estudantes gostam de ambas disciplinas?
    (b) (1.5 valores) Quantos estudantes gostam só de Álgebra?
    Resolução: É conveniente usar o diagrama de Venn. Sejam X o conjunto dos estudantes da

    turma, A e G os conjuntos dos estudantes da turma que gostam de Álgebra e gostam de


    Geometria, respectivamente. É dado que |X| = 40, |X \ (A ∪ B)| = 12, |A| = 20, |G| = 23.
    (a) Tem que ser encontrado |A ∩ G|. Temos |A ∪ G| = |X| − |X \ (A ∪ G)| = 40 − 12 = 28.
    então, pela regra de união,

    |A ∪ G| = |A| + |G| − |A ∩ G| ⇒ 28 = 20 + 23 − |A ∩ B| ⇒ |A ∩ B| = 15.

    Resposta: 15 estudantes.
    (b) Tem que ser encontrado |A \ G|. Como A = (A ∩ G) ∪ (A \ G) e os conjuntos A ∩ G e A \ G
    não intersectam, temos que

    |A| = |A ∩ G| + |A \ G| ⇒ 20 = 15 + |A \ G| ⇒ |A \ G| = 5.

    Resposta: 5 estudantes.
    2. Uma turma consiste em 12 homens e 8 mulheres. É necessário dividir a turma em dois grupos
    de 10 pessoas cada. Em quantas maneiras é possível fazer isto, se:
    (a) (1,5 valores) cada grupo deve ter exactamente 4 mulheres;
    (b) (1,5 valores) o chefe e o vice-chefe da turma devem estar em grupos diferentes.
    Resolução: (a) O número procurado, seja n, é o número de variantes de formação do primeiro
    grupo (o segundo grupo forma-se automaticamente pelos estudantes restantes da turma). Pelo
    princípio do produto, n = n1 n2 onde n1 é o número de variantes da escolha da parte do primeiro
    grupo que consiste em homens, e n2 é o número de variantes da escolha da parte que consiste
    em mulheres.
    Temos que n1 é o número das combinações de 12 homens por 6, e n2 é o número das combinações
    de 8 mulheres por 4. Sendo assim,

    n = n1 n2 = C612 C48 = 924 · 70 = 64 680

    Resposta: 64 680 maneiras.


    (b) Seja n o número procurado. Seja A1 o conjunto das partições da turma em quais o chefe
    está no primeiro grupo e vice-chefe no segundo, e A2 o conjunto das partições da turma em

    1
    quais o vice-chefe está no primeiro grupo e chefe no segundo. É claro que A1 ∩ A2 = ∅, então
    n = |A1 ∪ A2 | = |A1 | + |A2 |.
    |A1 | é o número de maneiras de formação do subgrupo contendo 9 pessoas do primeiro grupo
    (um lugar já está ocupado por chefe) de 20 − 2 = 18 pessoas (todas da turma excepto o chefe
    e o vice-chefe), isto é o número de combinações de 18 por 9. O número |A2 | encontra-se do
    mesmo modo. Temos assim,

    n = |A1 | + |A2 | = 2 · C918 = 2 · 48 620 = 97 240.

    Resposta: 97 240 maneiras.


    3. (a) (1,5 valores) Quantos números naturais de sete dígitos têm três dígitos 5, dois dígitos 8 e
    dois dígitos 9?
    (b) (2,5 valores) Quantos números naturais de sete dígitos têm a soma dos dígitos igual a 9?
    Resolução: (a) Temos que encontrar o número das permutações da sucessão de comprimento
    n = 7 contendo n1 = 3 elementos 5, n2 = 4 elementos 8 e n3 = 2 elementos 9. Usando a
    fórmula de permutações com repetições, temos
    n! 7!
    = = 210.
    n1 ! n2 ! n3 ! 3! 2! 2!
    Resposta: 210 números.
    (b) O número procurado n é igual ao número das soluções da equação

    x1 + x 2 + x3 + x4 + x5 + x6 + x7 = 9

    onde xi ∈ Z, xi ≥ 0 (i = 1, 2, . . . , 7) e x1 ≥ 1.
    Fazendo a troca das variáveis t1 = x1 − 1, ti = xi (i = 2, 3, . . . , 7) reduzimos a este problema
    ao problema do número de soluções da equação

    t1 + 1 + t2 + t3 + t4 + t5 + t6 + t7 = 9 ⇔ t1 + t2 + t3 + t4 + t5 + t6 + t7 = 8

    sob as condições ti ∈ Z e ti ≥ 0 (i = 1, 2, . . . , 7). Então,


    8+7−1
    n = D(8, 7) = C7−1 = C614 = 3003.

    Resposta: 3003 números.


    4. (2 ) Dê uma denição recursiva para a sucessão sn = 5 · 23n+1 , n = 0, 1, . . .
    valores

    Resolução: Temos que s0 = 5 · 20+1 = 10 e para n = 1, 2, . . .


    sn 5 · 23n+1
    = =8 ⇒ sn = 8sn−1 .
    sn−1 5 · 23n−2
    Resposta: s0 = 10 e sn = 8sn−1 , n = 0, 1, . . .

    5. (3 valores ) Encontre a fórmula explícita para sn se s0 = 4, s1 = 1 e sn = −sn−1 + 2sn−2 para


    n = 2, 3, . . .
    Resolução: Temos a sucessão denida recursivamente com a equação de recorrência linear.

    2
    A equação característica é r2 = −r + 2, ou seja r2 + r − 2 = 0. Esta equação quadrática tem
    as raízes diferentes r1 = −2 e r2 = 1. Então, sn que satisfaz a relação recorrente é dada por
    sn = c1 r1n + c2 r2n , ou seja
    sn = c1 (−2)n + c2 1n = c1 (−2)n + c2 , c1 , c2 ∈ R. (1)
    Encontremos c1 e c2 usando a parte base da denição recursiva e a fórmula (1) para n = 0 e
    n = 1:  
    c1 (−2)0 + c2 = s0 c1 + c2 = 4
    ⇔
    c1 (−2)1 + c2 = s1 −2c1 + c2 = 1
    Subtraindo da primeira equação à segunda temos 3c1 = 3, logo c1 = 1. Substituindo à primeira
    equação, temos c2 = 4 − c1 = 4 − 1 = 3. Sendo assim,
    sn = c1 (−2)n + c2 = (−2)n + 3.
    Resposta: sn = (−2)n + 3, n = 0, 1, 2, . . .
    6. Considere a sucessão denida recursivamente:
    s0 = s1 = 1 e sn = (n − 1)(sn−1 + sn−2 ), n = 2, 3, . . .
    (a) (2 valores) Encontre s2 , s3 , s4 , s5 , s6 por cálculo iterativo, e com base deste cálculo formule a
    hipótese sobre fórmula explícita para sn (sugestão: calcule n! para alguns primeiros n naturais).
    (b) (3 valores) Demonstre a fórmula encontrada em (a) usando o método de indução matemática.
    Resolução: (a) Temos que

    s2 = (2 − 1)(s1 + s0 ) = 1(1 + 1) = 2,
    s3 = (3 − 1)(s2 + s1 ) = 2(2 + 1) = 6,
    s4 = (4 − 1)(s3 + s2 ) = 3(6 + 2) = 24,
    s5 = (5 − 1)(s4 + s3 ) = 4(24 + 6) = 120,
    s6 = (6 − 1)(s5 + s4 ) = 5(120 + 24) = 720.
    O conhecimento dos termos s0 , s1 , . . . , s6 permite supor que a fórmula explícita para sn é
    sn = n! , n = 0, 1, 2, . . . (2)

    (b) Demonstremos a fórmula (2) usando princípio de indução matemática (PIM) com base de
    dois elementos. Introduzimos o predicado P (n) = {sn = n!}.
    (B) P (0) = {s0 = 0!} = {s0 = 1} e P (1) = {s1 = 1!} = {s1 = 1} são verdadeiras.
    (I) Fixemos k ∈ {0, 1, . . .}.
    Hipótese: P (k) = {sk = k!} e P (k + 1) = {sk+1 = (k + 1)!} são verdadeiras.
    Tese: P (k + 2) = {sk+2 = (k + 2)!} é verdadeira.
    Temos que:
    sk+2 = (k + 1)(sk+1 + sk ) (denição de sn )
    = (k + 1)((k + 1)! + k!) (Hipótese)
    = (k + 1)k!(k + 1 + 1)
    = k!(k + 1)(k + 2) = (k + 2)!
    Então, P (k + 2) é verdadeira.
    Pelo PIM, sn = n! qualquer que seja n = 0, 1, 2, . . ..

    Professores Yury Nepomnyashchikh e Timóteo Arnaldo Sambo

    Você também pode gostar