INF1631 - Estruturas Discretas - 99.1

Lista de Exercícios

  1. Uma fábrica produz 5 sabores de balas, e as vende em caixas de 8 balas. De quantas formas uma caixa pode ser preenchida? (495)
  2. idem, mas garantindo-se que cada caixa tem pelo menos 2 sabores diferentes. (490)
  3. Considere o seguinte problema: dados 20 jogadores, escolher 11 para um time, designando um deles como goleiro (qualquer um dos 20 pode jogar no gol). Podemos resolver isso escolhendo primeiramente um goleiro, e em seguida os 10 jogadores restantes. Alternativamente, podemos primeiramente escolher os 11, e depois escolher qual deles será o goleiro.
    1. Verifique que as duas alternativas estão corretas (isso é, cada escolha dá um resultado final diferente).
    2. Mostre que as duas alternativas dão o mesmo resultado (como era de se esperar).
    3. Generalize essa igualdade para o caso de n jogadores para um time de m.
  4. De quantas formas podemos pintar 5 faixas usando 8 cores, de modo que 2 (e apenas 2) faixas tenham a mesma cor? (16800)
  5. Dados 20 alunos, de quantas formas podemos escolher um grupo de 5, garantindo que o João e o José não sejam escolhidos simultaneamente? (Dica: se tirarmos a restrição, quantos grupos terão o João e o José simultaneamente?) (14688)
    1. De quantas formas podemos escolher uma string usando exatamente n vezes a letra a e m vezes a letra b (sem nenhuma outra letra)?
    2. De quantas formas podemos escolher n itens de um conjunto com n+m itens?
    3. Mostre que não é uma coincidência os dois resultados anteriores serem iguais. Mostre que existe uma correspondência 1-1 entre os dois conjuntos de resultados.
  7. De quantas formas podemos colocar 8 torres em um tabuleiro de xadrez, de modo que nenhuma possa atacar outra? (40320)
  8. (*) De quantas formas podemos distribuir 20 pessoas em 5 grupos? (Dica: a fórmula fechada para esse problema é bastante complicada. Procure uma equação recursiva, baseada na seguinte divisão: "ou a primeira pessoa está sozinha em um grupo ou não está.") (749206090500)
  9. Considere as equações recursivas para combinações: C(n,0)=1, C(0,m)=0, C(n,m)=C(n-1,m)+C(n-1,m-1). Baseado nessas equações, prove as igualdades abaixo:
    1. C(n,m) = 0, se n é menor que m
    2. C(n,n) = 1
    3. C(n,1) = n
    4. C(n,m) = C(n,n-m)