Maths Olympiad Prep

Library / /41 of 121

Combinatorics Difficulty 5.7 AIME, harder Prove it India

Problem:

Let nn be a positive integer. Call a nonempty subset SS of {1,2,,n}\{1,2, \ldots, n\} good if the arithmetic mean of the elements of SS is also an integer. Further let tnt_{n} denote the number of good subsets of {1,2,,n}\{1,2, \ldots, n\}. Prove that tnt_{n} and nn are both odd or both even.

Solutions — 2

Solution 1

Solution:

We show that TnnT_{n}-n is even. Note that the subsets {1},{2},,{n}\{1\},\{2\}, \cdots,\{n\} are good. Among the other good subsets, let AA be the collection of subsets with an integer average which belongs to the subset, and let BB be the collection of subsets with an integer average which is not a member of the subset. Then there is a bijection between AA and BB, because removing the average takes a member of AA to a member of BB; and including the average in a member of BB takes it to its inverse. So Tnn=A+BT_{n}-n=|A|+|B| is even.

Solution 2

Solution:

Let S={1,2,,n}S=\{1,2, \ldots, n\}. For a subset AA of SS, let Aˉ={n+1aaA}\bar{A}=\{n+1-a \mid a \in A\}. We call a subset AA symmetric if Aˉ=A\bar{A}=A. Note that the arithmetic mean of a symmetric subset is (n+1)/2(n+1)/2. Therefore, if nn is even, then there are no symmetric good subsets, while if nn is odd then every symmetric subset is good.

If AA is a proper good subset of SS, then so is Aˉ\bar{A}. Therefore, all the good subsets that are not symmetric can be paired. If nn is even then this proves that tnt_{n} is even. If nn is odd, we have to show that there are odd number of symmetric subsets. For this, we note that a symmetric subset contains the element (n+1)/2(n+1)/2 if and only if it has odd number of elements. Therefore, for any natural number kk, the number of symmetric subsets of size 2k2k equals the number of symmetric subsets of size 2k+12k+1. The result now follows since there is exactly one symmetric subset with only one element.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.