[obm-l] Combinatoria na IMO(ingles)

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Verifiquem isso!!!!

Problem 6

A permutation {x₁, x₂, ... , x_m} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |x_i - x_i+1| = n for at least one i in {1, 2, ... , 2n-1}. Show that for each n there are more permutations with property P than without.

Solution

from Arthur Engel, Problem-Solving Strategies, Springer 1998 [Problem books in mathematics series], ISBN 0387982191. A rather good training book.

Let A_k be the set of permutations with k and k+n in neighboring positions, and let A be the set of permutations with property P, so that A is the union of the A_k.

Then |A| = Sum_k |A_k| - Sum_k<l |A_kÇA_l| + Sum_k<l<m |A_kÇA_lÇA_m| - ... . But this is an alternating sequence of monotonically decreasing terms, hence |A| >= Sum_k |A_k| - Sum_k<l |A_kÇA_l|.

But |A_k| = 2 (2n - 1)! (two orders for k, k+n and then (2n - 1)! ways of arranging the 2n - 1 items, treating k, k+n as a single item). Similarly, |A_kÇA_l| = 4 (2n - 2)! So |A| >= (2n - 2)! [n.2(2n -1) - n(n - 1)/2 4] = 2n² (2n - 2)! > (2n)!/2.

 

---

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