Maths Olympiad Prep

Library / /4 of 9

Number theory Difficulty 7.9 National Olympiad, round 2 Prove it Singapore

A finite set of distinct positive integers is called a TT-set if each of its members divides the sum of them all. Prove that every finite set of positive integers is a subset of some TT-set.

Solution

Clearly, any set containing only one element is a TT-set. Also, since {1,2,3}\{1, 2, 3\} is a TT-set, any of its subsets is certainly contained in a TT-set.

Now let SS be a finite set of positive integers with at least two elements, and let n (>3)n\ (> 3) be the largest element in SS. Let σ(S)\sigma(S) denote the sum of the elements of SS.

Let T1={1,2,,n}T_1 = \{1, 2, \dots, n\}. Note that σ(T1)=n(n+1)/2\sigma(T_1) = n(n+1)/2. Let T2=T1{n(n+1)/2}T_2 = T_1 \cup \{n(n+1)/2\}. Then σ(T2)=n(n+1)\sigma(T_2) = n(n+1).

Finally we add another n2n-2 integers
(nj)(nj+2)(nj+3)(nj+4)n(n+1),j=2,3,,n1 (n-j)(n-j+2)(n-j+3)(n-j+4)\cdots n(n+1), \quad j=2,3,\dots,n-1
to obtain T3T_3. Again, it is clear that the integers are pairwise distinct and greater than n(n+1)/2n(n+1)/2. Now
σ(T3)=n(n+1)+j=2n1(nj)(nj+2)(nj+3)(nj+4)n(n+1)=n(n+1)+j=2n1[(nj+1)1](nj+2)(nj+3)(nj+4)n(n+1)=n(n+1)+(n+1)!n(n+1)=(n+1)! \begin{aligned} \sigma(T_3) &= n(n+1) + \sum_{j=2}^{n-1} (n-j)(n-j+2)(n-j+3)(n-j+4)\cdots n(n+1) \\ &= n(n+1) + \sum_{j=2}^{n-1} [(n-j+1)-1](n-j+2)(n-j+3)(n-j+4)\cdots n(n+1) \\ &= n(n+1) + (n+1)! - n(n+1) = (n+1)! \end{aligned}
Hence by our construction, T3T_3 is a TT-set, and since ST3S \subseteq T_3, we are done.

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.