Matemática Discreta 2011.1
Transcrição
Matemática Discreta 2011.1
Matemática Discreta 2011.1 - Problemas de contagem 1. Quais são as maneiras de cobrir um retângulo quadriculado 2 x 6 com dominós? 2. Quantas soluções têm a equação x + y + z = 30, sendo x, y, z inteiros maiores ou iguais a 7? 3. Determine o número de soluções inteiras positivas da equação x · y · z · t = 512. 4. Quantas soluções têm a equação x · y · z · t = 1024, sendo x, y, z, t inteiros maiores ou iguais a 2? 5. Determine o número de soluções inteiras da inequação x + y + z < 30 que satisfaçam as restrições: x ≥ 2, y ≥ 0 e z ≥ 3. 6. Determine o número de soluções inteiras não negativas da equação a + b + c + d = 30 sabendo que a > 2 e b > 3. 7. De quantos modos pode-se repartir 100 moedas iguais entre 5 pessoas de modo que cada pessoa receba pelo menos duas moedas? 8. Considere um torneio em que cada um dos n jogadores joga contra todos os outros e cada jogador ganha pelo menos uma partida. Mostre que, ao final do torneio, existem pelo menos dois jogadores com o mesmo número de vitórias. 9. Mostre que em qualquer conjunto de 52 inteiros existe um par de inteiros cuja soma ou cuja diferença é divisı́vel por 100. 10. De um baralho comum (52 cartas) sacam-se sucessivamente e sem reposição três cartas. Quantas são as extrações nas quais a primeira carta é de copas, a segunda é um rei e a terceira não é uma dama ? Solução: 2350 11. Quantos inteiros entre 1 e 1.000.000 tem soma de seus algarismos igual a 5 ? E a soma menor que 5 ? 12. Considere o desenho abaixo: A1 A2 A3 A4 A5 A6 B De quantas maneiras diferentes você pode andar de cada ponto Ai até o ponto B? Os únicos movimentos permitidos são indicados acima. Problemas de contagem Matemática Discreta 2011.1 13. Usando os mesmos tipos de movimentos permitidos no exercı́cio anterior, escreva, em cada bolinha do triângulo abaixo, de quantas maneiras diferentes você consegue chegar do ponto A até aquela bolinha. Justifique. A 14. Uma partı́cula estando no ponto (x,y), pode se movimentar par o ponto (x+1,y+1) ou para o ponto (x+1,y-1). Quantos são os trajetos possı́veis da partı́cula de (0,0) a (10,4)? Solução: 120 15. Uma partı́cula estando no ponto (x, y) do plano cartesiano pode se movimentar para o ponto (x + 1, y) ou para o ponto (x, y + 1). (a) Quantos são os trajetos possı́veis que esta partı́cula pode percorrer do ponto (0, 0) até o ponto (10, 3)? Solução: Temos que dar 13 passos, sendo 10 passos para a direita e 3 para cima, em qualquer ordem. Portanto temos 13 = 286 possibilidades. 3 (b) Escolhendo-se ao acaso um dos trajetos definidos no item (a), qual a probabilidade de que ele passe pelo ponto (2, 2)? Solução: Para ir de (0, 0) a (2, 2) são necessários 4 passos, sendo 2 para cima; portanto há 42 = 6 possibilidades. Para ir de (2, 2) a (10, 3) são necessários 9 passos, sendo 1 para cima; portanto há 91 = 9 possibilidades. Assim, há 6 × 9 = 54 caminhos de (0, 0) a (10, 3) passando por (2, 2). Logo 27 54 a probabilidade em questão é 286 = 143 ' 0.1888. 16. Seja Hn,m uma justaposição planar de laranjas formando um hexágono de lados de tamanhos n e m alternadamente. Quantas laranjas há em Hn,m ? 17. Tem-se uma rede de caminhos conforme a figura abaixo. Do ponto O partem 216 homens. Metade parte na direção l e metade na direção m. Ao chegar ao primeiro cruzamento cada grupo de divide: uma metade segue na direção l, a outra na direção m. Numeremos as linhas e os cruzamentos a partir do zero; assim, o ponto O é o zero-ésimo cruzamento da linha zero e o ponto A é o primeiro cruzamento de linha 4. Seja B um ponto que corresponde ao quinto cruzamento da linha 10. Partindo de O, quantos homens chegam a B? Página 2 de 3. Matemática Discreta 2011.1 Problemas de contagem 18. Determine o menor valor de n com a propriedade que para qualquer conjunto de n inteiros não-negativos distintos, se pode garantir que existe um par de inteiros (distintos) cuja soma ou cuja diferença é múltiplo de 10. Solução: Dado um par de números inteiros x e y, para saber se x + y ou x − y é múltiplo de 10, basta conhecer o último dı́gito de x e o último dı́gito de y. Suponha que x1 , . . . , xn são inteiros positivos tais que nenhuma soma ou diferença seja múltiplo de 10. Sejam d1 , . . . , dn os últimos dı́gitos de x1 , . . . , xn , respectivamente. Esses dı́gitos são todos distintos, pois senão haveria uma diferença xi − xj múltipla de 10. O fato de nenhuma soma xi + xj ser múltiplo de 10 faz com que os dı́gitos 1 e 9 não podem ambos aparecer na lista d1 , . . . , dn . Analogamente para 2 e 8, para 3 e 7, para 4 e 6. Assim, os n “pombos” d1 , . . . , dn tem que entrar nas 6 “casas” {0}, {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}, com no máximo um pombo por casa. Isso é impossı́vel se n ≥ 7. Por outro lado, existe uma lista de 6 números tal que nenhuma soma ou diferença seja múltiplo de 10, por exemplo: 0, 1, 2, 3, 4, 5. Concluı́mos que a resposta é n = 7 . Página 3 de 3.