[obm-l] Problemas de combinatoria

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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
=========================================================================