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