Maths Olympiad Prep

Library / /14 of 37

Number theory Difficulty 6.5 National olympiad Find the answer

Let m,nm,n be positive integers. Find the minimum positive integer NN which satisfies the following condition. If there exists a set SS of integers that contains a complete residue system module mm such that S=N| S | = N, then there exists a nonempty set ASA \subseteq S so that nxAxn\mid {\sum\limits_{x \in A} x }.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let m m and n n be positive integers. We aim to find the minimum positive integer N N which satisfies the following condition: If there exists a set S S of integers that contains a complete residue system modulo m m such that S=N |S| = N , then there exists a nonempty set AS A \subseteq S so that nxAx n \mid \sum_{x \in A} x .

First, let d=gcd(m,n) d = \gcd(m, n) , and write m=ad m = ad and n=bd n = bd . The answer depends on the relationship between bd bd and ad(d+1)2 \frac{ad(d+1)}{2} .

The minimum positive integer N N is given by:
N={1if bdad(d+1)2,bdad(d1)2otherwise. N = \begin{cases} 1 & \text{if } bd \leq \frac{ad(d+1)}{2}, \\ bd - \frac{ad(d-1)}{2} & \text{otherwise}. \end{cases}

The answer is: \boxed{\begin{cases}
1 & \text{if } bd \leq \frac{ad(d+1)}{2}, \\
bd - \frac{ad(d-1)}{2} & \text{otherwise}.
\end{cases}}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.