Maths Olympiad Prep

Library / /27 of 49

, 2022

Number theory Difficulty 6.3 National Olympiad Prove it Bulgaria

Let n2n \ge 2 be a fixed positive integer. The set MM consists of 2n23n+22n^2 - 3n + 2 positive rational numbers. Prove that there exists an nn-element subset AA of MM with the following property: for every kNk \in \mathbb{N}, 2kn2 \le k \le n, the sum of arbitrary kk (not necessarily distinct) elements of AA is not an element of AA.

Solution

Without loss of generality we can consider the elements of MM as positive integers, as we can multiply them by the gcd\gcd of their denominators, which does not affect the problem statement.

The arithmetic progression {(2n1)q+n}q=1\{(2n-1)q+n\}_{q=1}^{\infty} contains infinitely many primes, due to the Dirichlet theorem and ((2n1),n)=1((2n-1), n) = 1. Let us fix a prime p=(2n1)q+np = (2n-1)q+n, larger than all the elements of MM, i.e., MM becomes a set of residues modulo pp. Consider the following set of residues:

P={p+n12n1,p+3n22n1,,2p12n1}, P = \left\{ \frac{p+n-1}{2n-1}, \frac{p+3n-2}{2n-1}, \dots, \frac{2p-1}{2n-1} \right\},

for which the numerator of every successive fraction exceeds the previous one by 2n12n-1. According to the choice of pp, all elements in PP are positive integers. Moreover
2p+n12n1=2p12n1+1andn2p12n1=p+pn2n1. 2 \cdot \frac{p+n-1}{2n-1} = \frac{2p-1}{2n-1} + 1 \quad \text{and} \quad n \cdot \frac{2p-1}{2n-1} = p + \frac{p-n}{2n-1}.

This means that the sum of arbitrary (at least 2 and at most nn, not necessarily distinct) elements of PP modulo pp, is not an element of PP!

Note that P=2p12n1pn2n1=p+n12n1|P| = \frac{2p-1}{2n-1} - \frac{p-n}{2n-1} = \frac{p+n-1}{2n-1}. Let M={m1,m2,,m2n23n+2}M = \{m_1, m_2, \dots, m_{2n^2-3n+2}\}. For each i=1,2,,2n23n+2i = 1, 2, \dots, 2n^2-3n+2, the numbers {mi1,mi2,,mi(p1)}\{m_i \cdot 1, m_i \cdot 2, \dots, m_i \cdot (p-1)\} form a permutation of {1,2,,(p1)}\{1, 2, \dots, (p-1)\} (mod pp), i.e., exactly p+n12n1\frac{p+n-1}{2n-1} of them are elements of PP! Thus, there exists k{1,2,,p1}k \in \{1, 2, \dots, p-1\}, such that among the numbers {km1,km2,,km2n23n+2}\{k \cdot m_1, k \cdot m_2, \dots, k \cdot m_{2n^2-3n+2}\} at least
(2n23n+2)p+n12n1p1>2n23n+22n1>n1 \frac{(2n^2 - 3n + 2) \cdot \frac{p+n-1}{2n-1}}{p-1} > \frac{2n^2 - 3n + 2}{2n-1} > n-1
are elements of PP modulo pp. It is easy to check, that the corresponding elements {mj}\{m_j\} (at least nn in number) of MM, satisfying kmjPk \cdot m_j \in P (mod pp), fulfill the problem statement. In particular, so does every their subset of exactly nn elements.

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.