Prova Matematica Discreta 2019-1 - Exame Individual

Exame de Matematica Discreta 20191 A prova e individual sem consulta e e proibido usar qualquer eletrˆonico Pode responder as questoes usando lapis deixe as resolucoes legıveis caso a folha seja de papel reciclado e em qualquer ordem Devolver a folha de questoes no final da prova E preferıvel responder menos questoes mas com qualidade do que muitas questoes mal res pondidas um exercıcio certo vale mais que dois meiocertos Tambem e preferıvel responder questoes em temas diferentes do que no mesmo tema A prova tem 8 questoes Para a avaliacao serao consideradas 6 questoes Caso resolva mais questoes vocˆe deve indicar quais 6 devem ser consideradas Resposta sem justificativa nao sera considerada Eventualmente a prova nao sera corrigida ate o prazo de lancamento de notas nesse caso os conceitos serao lancados no proximo quadrimestre 1 Definicao 1 Uma cadeia binaria e uma sequˆencia de numerais ou bits 0 e 1 usualmente escritos um seguido do outro e nao separados por vırgulas como por exemplo 01001 Podemos alternativamente definir recursivamente o conjunto 0 1 de todas as cadeias binarias A0 λ 0 1 λ e uma cadeia binaria chamada cadeia vazia cujo objetivo e representar a cadeia sem sımbolos A1 se s 0 1 entao sb 0 1 para qualquer b 0 1 Definicao 2 A concatenacao das cadeias s e t e a cadeia st Essa operacao pode ser definida recursivamente por B0 se s λ entao st t senao B1 s bu com b 0 1 e u 0 1 de modo que st but but Definicao 3 O reverso da cadeia s e denotado por sR e definido como a ca deia obtida escrevendo S na ordem inversa Por exemplo o reverso de 0101 e 0101R 1010 e o reverso de 1110 e 0111 Com tais definicoes resolva a e b ou c e d ou e e f a Dˆe uma definicao recursiva para ℓ 0 1 N onde ℓs e a quantidade de bits na cadeia s Por exemplo ℓ01001 5 a0 Se s λ entao definimos ℓs 0 a1 senao por B1 s bu com b 0 1 e u 0 1 entao definimos ℓs 1 ℓu b Prove usando inducao estrutural que ℓst ℓs ℓt para quaisquer s t 0 1 1 Por inducao em s Se s λ entao ℓst ℓt 0 ℓt ℓs ℓt Seja s bu com b 0 1 e u 0 1 e suponha que ℓut ℓu ℓt t Se s bu st but but por B1 assim ℓst ℓbut mas ℓbut ℓb ℓut por a1 e ℓut ℓu ℓt por hipotese Portanto ℓst ℓs ℓt Por inducao ℓst ℓs ℓt para todos s t 0 1 c Dˆe uma definicao recursiva para o reverso de uma cadeia binaria b0 Se s λ entao definimos sR s b1 senao por B1 s bu com b 0 1 e u 0 1 entao definimos sR uRb d Prove usando inducao estrutural que stR tRsR para quaisquer s t 0 1 Por inducao em s Se s λ entao stR tR tRsR por b0 Seja s bu com b 0 1 e u 0 1 e suponha que utR tRuR u Se s bu st but but por B1 assim stR butR utRb por b1 mas utR tRuR por hipotese de inducao Portanto stR tRuRb tRsR Por inducao stR tRsR para todos s t 0 1 e Prove usando inducao estrutural que Para todo s 0 1 sλ s Se s λ entao sλ s Seja s bu com b 0 1 e u 0 1 e suponha que uλ u u Se s bu sλ buλ buλ bu s Por inducao sλ s para todo s 0 1 f Defina L 0 1 recursivamente por C0 λ L C1 se s L entao 0s0 L e 1s1 L Prove usando inducao estrutural que ℓt e par para todo t L Seja s L Se s λ entao ℓt 0 e par senao s btb com b 0 1 e t L e assuma ℓt par Entao ℓs 2 ℓt portanto par Por inducao ℓt e par para todo t L 2 Prove por indução que 2 é irracional Dica Pn a sentença 2 nb para todo natural b 0 Seja Pn para todo n N a sentença dada no enunciado Se n 0 então Pn é verdadeira pois 2 0 0b para todo b Seja k um natural arbitrário e suponha que P0 P1 Pk são verdadeiros Vamos provar Pk 1 por contradição Se existe um natural b 0 tal que 2 k1b então 2 k12b2 donde concluímos como prova feita em sala que k 1 é par Se k 1 2s então b também é par como prova feita em sala b 2t Então 2 k 1b 2s2t st contrariando Ps que por hipótese é verdadeira Note que s k 1 e Ps afirma que 2 sb para todo natural b 0 Qual é o coeficiente de x2 y5 z3 na expansão de x y z10 x y z10 x y zx y zx y zx y z um produto com 10 parcelas Quando aplicamos a distributividade das 10 parcelas há 10 choose 2 modos de escolher 2 que contribuirão com x no produtos pra cada uma delas há 102 choose 5 modos de escolher 5 parcelas que contribuirão com y as 3 parcelas restantes contribuirão com z portanto pelo Princípio Multiplicativo 10 choose 2102 choose 5 termos correspondem a x2 y5 z3 De quantas maneiras podemos distribuir k partículas indistinguíveis em n níveis de energia distintos Esta distribuição de partículas em níveis de energia é chamada em Física de Estatística de BoseEinstein Se xi é o número de partículas no nivel i o número de distribuições é a quantidade de soluções de x1 x2 xn k com xi N que tem nk1 choose k ou nk1 choose n1 soluções De quantas maneiras podemos distribuir k partículas indistinguíveis em n níveis de energia distintos se cada nível pode conter no máximo uma partícula Esta distribuição de partículas em níveis de energia é chamada em Física de Estatística de FermiDirac Cada distribuição corresponde à seleção de um subconjunto de k dos n níveis de energia logo são n choose k modos de distribuir Uma roleta de seis compartimentos é pintada com três cores azul vermelho e branco sendo permitida a repetição de cores Use uma relação de equivalência para mostrar que o número de maneiras de fazer esta pintura é 130 Defina X a1 a2 a3 a4 a5 a6 ai branco azul vermelho que representa as possíveis pinturas dos compartimentos Pelo princípio multiplicativo X 36 Se rodarmos a roleta a pintura não muda Assim consideraremos a relação de equivalência R em X definida pelas rotações duas sextuplas pertencerão a uma mesma classe de equivalência se uma 6upla puder ser obtida a partir de rotações da outra por exemplo as sextuplas a1 a2 a3 a4 a5 a6 e a2 a3 a4 a5 a6 a1 representam a mesma pintura ou seja pertencem à mesma classe de equivalência Temos 3 classes de equivalência unitárias que correspondem a todos os compartimentos com a mesma cor Temos 3 classes de equivalência com cardinalidade 2 pois temos que escolher uma das três cores para um compartimento e depois uma das duas cores restantes para o compartimento vizinho os demais compartimentos alternam as cores Para cardinalidade 3 temos que compartimentos opostos devem ter mesma cor o que nos daria 33 Porém devemos subtrair as pinturas em que a roleta está toda de uma mesma cor pois estes já foram contados Isso nos dá 33 3 Dividindo pelo tamanho 3 ficam 8 classes de equivalência Finalmente as classes de equivalência de cardinalidade 6 A maneira mais fácil de contar isso é subtrair de 36 as configurações que estão nas outras classes de equivalência 36 3 3 2 33 3 que dividindo por 6 dá 116 classes de equivalência de tamanho 6 Logo no total temos 130 classes de equivalência Enuncie de modo preciso e como uma sentença condicional e prove Remover um elemento de um conjunto infinito resulta num conjunto infinito Se A é infinito então A x é infinito para todo x A Vamos provar a contrapositiva Se A x é finito então A x n para algum natural n Se x A então A A x x e a união é de disjuntos logo A A x 1 n 1 ou seja é finito Sejam A e B ordens totais Uma função f A B é dita crescente se e só se para todos x y A vale x y fx fy Dê uma prova ou um contraexemplo para a sentença toda função crescente f A B é injetiva Para quaisquer x y A se x y então x y ou y x pois a ordem é total Se x y então fx fy em particular fx fy Se y x então fy fx em particular fx fy Portanto f injetiva