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 e seus numero de elementos).