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)