Oi, pessoal: Aqui estao alguns problemas de combinatoria que estao me dando (muito) trabalho:
1. (proposto pelo Nicolau) Quantas matrizes m x n com elementos em {1,2,...,p} (p: inteiro positivo) existem de forma que se A eh uma tal matriz, A(i,j) > A(i+1,j) e A(i,j) > A(i,j+1), para todos i e j. 2. Qual a condicao necessaria e suficiente para que um tabuleiro m x n possa ser inteiramente coberto com dominos p x q. No caso de p = 2 e q = 1, de quantas maneiras isso pode ser feito? 3. (proposto pelo Rogerio Ponce) Quantas permutacoes de {1,2,...,n} existem com todos os ciclos de ordem >= 3? 4. Prove que eh possivel pintar os pares nao ordenados (subconjuntos de 2 elementos) de R de azul ou vermelho de forma que nenhum subconjunto nao enumeravel S de R tenha todos os seus pares nao ordenados da mesma cor. 5. Uma familia F de subconjuntos de N eh dita "quase-disjunta" se para quaisquer membros A e B dessa familia, (A inter B) eh finito. Prove que existe uma familia de subconjuntos de N que eh "quase-disjunta" e nao enumeravel. 6. Sabe-se (desigualdade de Fisher) que se A_1, A_2, ..., A_m sao subconjuntos de {1,2,...,n} tais que para 1 <= i < j <= m, |A_i inter A_j| = k (0 <= k <= n-1) entao m <= n. Para k >= 2, de exemplos (se existirem) de familias de subconjuntos onde vale a igualdade. 7. Dada uma sequencia a_1 < a_2 < ... de inteiros positivos, seja A(x) = maior n tal que a_n <= x. Define-se a Densidade Inferior (DI) da sequencia como sendo DI = liminf(n->inf) A(n)/n e a Densidade Superior (DS) como sendo DS = limsup(n->inf) A(n)/n. De um exemplo de sequencia onde DI < DS. Qualquer ajuda serah (muito) bem vinda. Um abraco, Claudio. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================