Lista de Exercícios Resolvidos - Teoria da Computação e Análise Combinatória

Fundamentos de Teoria de Computação 1 Prove que A B A em que A e B são conjuntos arbitrários 2 Prove que A B C A B C se e somente se C A 3 Quantos são os anagramas da palavra TurmaDaMonica a possíveis b que começam e terminam por vogal c que têm as vogais e as consoantes intercaladas 4 De quantos modos podemos selecionar 7 elementos do conjunto alfabeto abz sem selecionar duas letras consecutivas 5 Um campeonato é disputado por 16 clubes em rodadas de 4 jogos cada De quantos modos é possível selecionar os jogos da primeira rodada 6 Em uma escola y professores se distribuem em 7 bancas examinadores de modo que cada professor participa de exatamente duas bancas e cada duas bancas tem exatamente um professor em comum aCalcule y bDetermine quantos professores há em cada banca 7 Escrevemse os inteiros de 101 até 6666 a Quantas vezes o algarismo 2 é escrito b Em quantos números aparece o algarismo 3 8 Quantos são os inteiros positivos de 5 algarismos nos quais o algarismo 7 figura 9 Qual é o valor do termo independente de x do binômio 2x xn considerando que o mesmo corresponde ao sétimo termo de seu desenvolvimento 10 Escreve o termino que contém x13 no desenvolvimento de 2x2y y2x20 Omar Latorre Vilca 1 Prove que A B A em que A e B são conjuntos arbitrários 2 Prove que A B C A B C se e somente se C A 3 Quantos são os anagramas da palavra TurmaDaMonica a possíveis b que começam e terminam por vogal c que têm as vogais e as consoantes intercaladas 4 De quantos modos podemos selecionar 7 elementos do conjunto alfabeto abz sem selecionar duas letras consecutivas 5 Um campeonato é disputado por 16 clubes em rodadas de 4 jogos cada De quantos modos é possível selecionar os jogos da primeira rodada 6 Em uma escola y professores se distribuem em 7 bancas examinadores de modo que cada professor participa de exatamente duas bancas e cada duas bancas tem exatamente um professor em comum aCalcule y bDetermine quantos professores há em cada banca 7 Escrevemse os inteiros de 101 até 6666 a Quantas vezes o algarismo 2 é escrito b Em quantos números aparece o algarismo 3 8 Quantos são os inteiros positivos de 5 algarismos nos quais o algarismo 7 figura 9 Qual é o valor do termo independente de x do binômio 2x xn considerando que o mesmo corresponde ao sétimo termo de seu desenvolvimento 10 Escreve o termino que contém x13 no desenvolvimento de 2x2y y2x20 chama no wpp se quiser tbm 67 992189218 Fundamentos de Teoria de Computação 1 Prove que A B A em que A e B são conjuntos arbitrários 2 Prove que A B C A B C se e somente se C A 3 Quantos são os anagramas da palavra TurmaDaMonica a possíveis b que começam e terminam por vogal c que têm as vogais e as consoantes intercaladas 4 De quantos modos podemos selecionar 7 elementos do conjunto alfabeto abz sem selecionar duas letras consecutivas 5 Um campeonato é disputado por 16 clubes em rodadas de 4 jogos cada De quantos modos é possível selecionar os jogos da primeira rodada 6 Em uma escola y professores se distribuem em 7 bancas examinadores de modo que cada professor participa de exatamente duas bancas e cada duas bancas tem exatamente um professor em comum aCalcule y bDetermine quantos professores há em cada banca 7 Escrevemse os inteiros de 101 até 6666 a Quantas vezes o algarismo 2 é escrito b Em quantos números aparece o algarismo 3 8 Quantos são os inteiros positivos de 5 algarismos nos quais o algarismo 7 figura 9 Qual é o valor do termo independente de x do binômio 2x xn considerando que o mesmo corresponde ao sétimo termo de seu desenvolvimento 10 Escreve o termino que contém x13 no desenvolvimento de 2x2y y2x20 3 a A palavra Turma Da Monica tem 13 letras logo podemos permutálas de 13 formas mas a letra a se repete 3 vezes e a letra m duas vezes considerando que m minúsculo e maiúsculo é a mesma coisa assim cada uma dessas letras podem permutar entre si 3 e 2 vezes respectivamente que são sendo contadas Portanto temos 1332 anagramas b A palavra tem 6 vogais contando as repetidas logo para a primeira letra temos 6 possibilidades Uma vez escolhida a primeira a última letra restam 5 possibilidades de vogais Depois de escolhidas a primeira e última temos 11 letras para permutar no meio logo 11 formas Pelo principio multiplicativo 6 x 5 x 11 mas como temos letras repetidas vamos dividir por 32 Logo temos 651132 5112 anagramas se x AB então x A e x B logo x BC e x ABC Se x C então x BC e como C A então também x A logo x ABC Assim em qualquer caso x ABC logo ABC ABC Vamos mostrar agora que ABC ABC Seja x qualquer x ABC logo temos que x A e x B ou x C Se x B então x AB logo x ABC Se x C então x ABC Assim em qualquer caso x ABC logo ABC ABC Finalmente como ABC ABC e ABC ABC então ABC ABC 1 Dado qualquer x tal que x AB então pela definição x A e x B em particular x A Portanto AB A 2 Primeiro vamos provar a ida Considerando que ABC ABC Dado x qualquer tal que x C então x ABC logo pela hipótese x ABC Isto é x BC o que de fato ocorre pois x C e x A Portanto C A Agora fazendo a volta Considerando que C A Vamos mostrar que ABC ABC Seja x qualquer x ABC logo temos que se x AB então x A e x B logo x BC e x ABC c Considerando apenas vogais e consoantes só temos uma possibilidade de intercalalas na palavra que é C consoante e v vogal C V C V C V C V C V C Logo basta contar as permutações das consoantes entre si e multiplicar pela permutação das vogais Das consoantes temos 7 e duas repetidas logo 72 Das vogais são 6 e 3 repetidas logo 63 5 Logo o total de anagramas é 752 a Vamos contar da seguinte maneira Primeiro vamos contar quantas vezes escrevemos o 2 como algarismo das unidades Para isso veja que escreveremos um 2 a cada 30 começando por 302 até 6662 Como 302 30 x 10 2 e 6662 30 x 666 2 então são 666 10 1 657 vezes Agora vamos contar quantas vezes como algarismo das dezenas Para isso veja que escrevemos 10 números 2 a cada 300 começando com 320 até 6620 Como 320 300 x 1 20 e 6620 300 x 66 20 então ocorreu 66 1 1 66 intervalos que escreveremos 10 Logo 66 x 10 660 Contando nas centenas a cada 3000 escreveremos 100 números 2 Começando com 200 e terminando com 6200 Como 200 1000 x 0 200 e 6200 1000 x 6 200 então escreveremos 100 x 6 0 1 100 x 7 700 vezes Nas milhares escreveremos 1000 vezes que é entre 2000 e 2999 Portanto ao total foram 657 660 700 1000 3017 vezes que foi escrito b Vamos calcular número total e quais deles não aparece nenhum 3 O total são 6666 303 3 6566 números ao total Para calcular os que não aparecem 3 vamos dividir em 2 casos Os de três algarismos e os de quatro Nos de três algarismos temos 8 possibilidades pra as centenas já que não pode 0 nem 3 Uma vez escolhida ficam 9 para as dezenas pois não pode o 3 e 9 para as unidades Ficando 8 x 9 x 9 648 Porém temos que tirar os números 300 e 303 Logo 646 Nos de quatro algarismos vamos fazer os até 6000 e depois contemos entre 6000 e 6666 Até 6000 temos 4 possibilidades pois não pode ser 0 3 6 7 8 9 para o de milhares e 9 para os outros pois só não pode 3 Logo 4 x 9 x 9 x 9 2916 De 6000 a 6666 vamos dividir novamente de 6000 até 6600 e depois de 6600 até 6666 De 6000 a 6600 temos 6 nos milhares 5 possibilidades nas centenas e 9 nas dezenas e unidades Logo 5 x 9 x 9 405 De 6600 a 6666 temos 67 números precisamos tirar 10 que são os que tem 3 nas dezenas e os números 6603 6613 6623 6643 6653 e 6663 Logo ficam 67 10 6 51 Assim são 51 405 2916 3372 de quatro algarismos que não aparece o 3 Logo entre os números temos 6566 ao total e 646 3372 4018 que não aparece o 3 Portanto em 6566 4018 2548 números aparece o 3 8 Vamos contar o número total de números de 5 algarismos e subtrair os que 7 não aparece O total são 99999 10000 1 90000 números Nos que 7 não aparece temos 8 possibilidades para as dezenas de milhares pois não pode 0 ou 7 Para os outros algarismos temos 9 pois só não pode o 7 Ao total são 8 x 9 x 9 x 9 x 9 52488 Portanto ao total 90000 52488 37 512 números tem o algarismo 7 Como queremos o que contém x13 então x403p x13 40 3p 13 p 40 133 9 Logo queremos o 30 termo Substituindo no nosso desenvolvimento o valor de p 39 209 2209 y3920 x13 1 209 211 y7 x13