INF1631 - Estruturas Discretas - 99.1

2a Lista de Exercícios

  1. Vamos considerar um jogo de poker. Nesse jogo, um jogador recebe uma "mão" com 5 cartas, tiradas de um baralho completo. (Um baralho completo tem 52 cartas, distribuídas em 4 naipes; cada naipe tem 13 valores de cartas: A, 1, 2, ... 10, J, Q, K.) A probabilidade de uma determinada configuração de cartas acontecer (por exemplo um "four", uma mão com 4 cartas de valor igual) pode ser calculada dividindo-se o total de mãos diferentes nas quais a configuração acontece pelo total geral de mãos diferentes. (Quantas mãos diferentes um jogador pode receber?)

    Calcule as probabilidades de um jogador ter as configurações abaixo. Dê o resultado final numericamente, mas procure calcular o total de configurações classificando o problema antes de fazer as contas; em particular, procure identificar as combinações envolvidas em cada problema. Se possível, resolva cada problema de pelo menos duas formas diferentes para poder conferir os resultados.

    1. Uma mão com um rei de copas.
    2. Um "four" (4 cartas com o mesmo valor).
    3. Um "flush" (todas as cartas de um mesmo naipe).
    4. Uma "full hand" (uma trinca e uma dupla).
    5. Um "straight flush" (todas as cartas de um mesmo naipe, com valores consecutivos).
    6. (*) Uma dupla (duas cartas de mesmo valor). Cuidado: um "four" não é uma dupla (apesar de conter duas cartas de mesmo valor); uma full hand também não. Uma dupla significa que o máximo que o jogador consegue agrupar são duas cartas de mesmo valor (ou seja, todas as outras cartas tem valores diferentes entre sí e diferentes do valor da dupla).

  2. Considere um jogo de Loto, onde 5 números são sorteados entre um total de 100 números.
    1. Qual a probabilidade de você acertar, jogando exatamente 5 números?
    2. E se você jogar 7 números?
    3. Quantos cartões de 5 números são necessários para se "cobrir" um cartão com 7 números?

  3. Quantas "palavras" de 4 letras podem ser escritas? Como você pode mapear esse problema para um problema de bolas e urnas? (Quem seriam as bolas? E as urnas? Quem seria distinguível?)

  4. Para cada um dos 4 tipos de problemas de bolas e urnas que vimos, liste todas as soluções para o caso de 4 bolas e 3 urnas. Faça a listagem de forma sistemática. Em particular, para o caso de bolas e urnas indistinguíveis, use a ordem derivada do algoritmo visto na última aula (primeiro os casos com pelo menos uma urna vazia, depois os casos sem urnas vazias).

  5. Queremos dividir um grupo de 5 pessoas em 3 grupos. Cada grupo pode ser de qualquer tamanho, só não pode ser vazio. Uma solução recursiva para esse problema é: Baseado no algoritmo acima, liste todas as soluções para o problema.

  6. Prove e dê um argumento combinatório para as seguintes igualdades: n*C(n-1,k) = (k+1)*C(n,k+1) = (n-k)*C(n,k)

  7. De quantas formas podemos colocar b bandeiras em m mastros distintos, onde a ordem das bandeiras em cada mastro é relevante?

    Dica: de quantas formas podemos colocar uma bandeira? De quantas formas podemos colocar a 2a bandeira? (Podemos pensar que a 1a bandeira dividiu um dos mastros em 2, pois a 2a pode entrar em baixo ou em cima da 1a...)

    Outra forma de resolver: como podemos codificar cada solução em uma string? Quantas strings dessas podemos escrever?

  8. Quantas sequências crescentes de números inteiros podemos escrever começando em 1 e terminando em n? (Dica: enumere todos os casos para n=2,3,4,5)

  9. (*) Quantas combinações de k números podemos fazer do conjunto {1,2,...,n}, de modo que cada combinação nunca contenha dois números consecutivos?