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.