Maths Olympiad Prep

Library / /459 of 520

Combinatorics Difficulty 6.2 National olympiad Prove it

LII OM - II - Problem 6

For a given positive integer n n , determine whether the number of n n -element subsets of the set {1,2,3,,2n1,2n} \{1,2,3,\ldots,2n-1,2n\} with an even sum of elements is the same as the number of n n -element subsets with an odd sum of elements. If not, determine which is greater and by how much.

Solution

Let's connect the numbers from the set S={1,2,3,,2n1,2n} S = \{1,2,3,\ldots,2n-1,2n\} in pairs:

Let X X be any n n -element subset of the set S S . Choose (if possible) the smallest number x x from the set X X with the property that the number y y paired with x x does not belong to the set X X . Then remove the element x x from the set X X and replace it with the element y y . The resulting set is called f(X) f(X) . The sets X X and f(X) f(X) have sums of elements of different parity.
In the further part of the solution, we will consider two cases:
(a) The number n n is odd.
The mapping f f is defined for any n n -element subset of the set S S and it pairs all n n -element subsets with odd sums of elements with all n n -element subsets with even sums of elements. This proves that the number of n n -element subsets with even sums of elements is the same as the number of n n -element subsets with odd sums of elements.
(b) The number n n is even.
In this case, the mapping f f can only be defined for those n n -element subsets of the set S S that consist of complete pairs. There are (nn/2) \binom{n}{n/2} such subsets, and all of them have sums of elements with the same parity as the parity of the number n/2 n/2 . The remaining subsets can be paired as (X,f(X)) (X,f(X)) . If n n is divisible by four, then the number of n n -element subsets with even sums of elements is (nn/2) \binom{n}{n/2} more than the number of n n -element subsets with odd sums of elements. If, however, n n is not divisible by four, then the number of n n -element subsets with odd sums of elements is (nn/2) \binom{n}{n/2} more.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.