[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Combinatoria na IMO



Caro JP:
 
NPL(n) = número de permutações legais de {1,2,...,2n}.
 
Eu usei inclusão-exclusão e cheguei a um somatório que, por enquanto, não consegui simplificar:
 
                      n
NPL(n) = SOMATÓRIO  (-1)^(k+1) * C(n,k) * (2n-k)! * 2^k
                   k = 1
 
Calculando numa planilha eu achei que NPL(n)  >  (2n)! / 2  para n de 1 até 10, mas ainda não consegui provar o caso geral.
 
Você concorda com esta fórmula?
 
Um abraço,
Claudio.
 
 
----- Original Message -----
Sent: Tuesday, February 04, 2003 2:14 PM
Subject: [obm-l] Combinatoria na IMO

Turma,to tentando resolve esse problema da IMO da Alemanha:

Chame uma permutaçao dos elementos 1,2,3,...,2n de legal se existe pelo menos um par de elementos consecutivos cuja diferença seja n.Mostre que ha mais legais do que nao-legais nessas permutaçoes.

Tentei achar soluçoes assim:

1)Defina uma funçao que transforma uma permutaçao legal numa ilegal,de modo que ela seja injetiva(duas permutaçoes legais cujas correspondentes ilegais sao iguais sao necessariamente iguais) e nao-sobrejetiva(e possivel escolher pelo menos uma permutaçao ilegal que nao e correspondente de nenhuma legal).Desse jeito acabou!

2)Calcule o numero de permutaçoes ilegais explicitamente e verifique que o total e menor que (2n)!/2.

Minha ideia era usar inclusao e exclusao(e um teorema poderoso sobre uniao de conjuntos finitos.O caso de dois conjuntos e facil.A uniao de dois conjuntos e o primeiro mais o segundo menos a intersecçao deles.A generalizaçao e imediata).

O primeiro parece facil mas nao achei a tal funçao.O segundo eu nao consigo arquitetar as contas direito.Sou muito lerdo e ainda to meio enrolado.Quem puder ajudar,valeu!!!



TRANSIRE SVVM PECTVS MVNDOQUE POTIRE

CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE

Fields Medal(John Charles Fields)



Busca Yahoo!
O serviço de busca mais completo da Internet. O que você pensar o Yahoo! encontra.