1. Considere o conjunto dos números que podem ser escritos com os dígitos 0, 1, ..., 9 (base 10), onde todos os dígitos são diferentes. Utilize o princípio da inclusão-exclusão para determinar a cardinalidade deste conjunto.
   
   
2. Seja T = { t₁, ..., t_n } uma sequência de n números distintos.
   
   
   1. Utilize indução matemática (com reforço de hipótese) para propor um algoritmo que obenha a maior subsequência crescente (não necessariamente consecutiva).
      
      
   2. Repita o item anterior para obter a maior subsequência decrescente.
      
      
   3. Considere que para cada elemento de T é associado um custo positivo c_i, i=1,...,n. Proponha um algoritmo para encontrar a subsequência crecente de T onde a soma dos custos dos elementos é maximizada.
      
      
   4. Repita o item anterior para obter a subsequência decrescente com maior peso.
      
      
   5. Aplique os algoritmos obtidos acima na sequência:
      3, 17, 9, 12, 35, 6, 27, 8, 21, 26, 23, 11, 19, 13, 15
      com os pesos 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 e também com os pesos 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
   
   
3. Seja u_n o número de strings no alfabeto {0,1} que possuem a propriedade de não ter dois zeros consecutivos. Mostre que u₁ = 2, u₂ = 3 e u_n = u_n-1 + u_n-2.
   
   
4. Mostre que qualquer conjunto de 172 inteiros existe um par cuja diferença é divisível por 171.
   
   
5. Mostre que em um grupo de 6 pessoas existe pelo menos um conjunto de 3 pessoas se conhecem mutuamente ou se desconhecem mutuamente. Em seguida, mostre que em um grupo de 10 pessoas existe sempre um conjunto de 4 pessoas que se conecem ou um conjunto de 3 pessoas que se desconhecem mutuamente. Mostre agora que se o conjunto tem 20 pessoas então existe um conjunto de 4 pessoas onde ou todos se conhecem ou todos se desconhecem. Observe que a relação ``conhecer" é simétrica.
   
   Para isso, inicie sempre considerando um pessoa arbitrária em particular e aplicando a generalização do princípio da casa do pombo generalizado onde observa-se que se um conjunto de n elementos é particionado em k grupos então pelo menos um subgrupo possui é n/k ù elementos. Por exemplo, um grupo de 5 elementos particionado em dois subgrupos implica que existirá um subgrupo com 3 elementos.
   
   A aplicação recursiva dos resultados obtidos permite provar as afirmações acima.
   
   
6. Considere o conjunto S= { 1, 2, ..., 2n } e um subconjunto X de S. Seja a função f:X ¾® Y onde f(x) é o maior número impar que divide x para x Î X. Observe que Y, a imagem de f, necessariamente está contida em { 1, 3, ..., 2n - 1}. Argumente que qualquer conjunto X onde |X| ³ n + 1 possui dois elemento onde um divide o outro.

This document was translated from L^AT_EX by H^EV^EA.