Maths Olympiad Prep

Library / /27 of 97

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

An integer n>1n>1 is given . Find the smallest positive number mm satisfying the following conditions: for any set {a,b}\{a,b\} {1,2,,2n1}\subset \{1,2,\cdots,2n-1\} ,there are non-negative integers x,y x, y ( not all zero) such that 2nax+by2n|ax+by and x+ym.x+y\leq m.

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

Solution

Given an integer n>1 n > 1 , we aim to find the smallest positive number m m satisfying the following conditions: for any set {a,b}{1,2,,2n1}\{a, b\} \subset \{1, 2, \ldots, 2n-1\}, there exist non-negative integers x x and y y (not both zero) such that 2nax+by 2n \mid ax + by and x+ym x + y \leq m .

To determine the smallest m m , we analyze the conditions:

1. Consider a=1 a = 1 and b=2 b = 2 . If 2nax+by 2n \mid ax + by , then:
2nx+2y2(x+y)2m. 2n \leq x + 2y \leq 2(x + y) \leq 2m.
This implies mn m \geq n .

2. We now show that mn m \leq n .

- Case 1: If gcd(a,2n)>1\gcd(a, 2n) > 1 or gcd(b,2n)>1\gcd(b, 2n) > 1. Without loss of generality, assume gcd(a,2n)>1\gcd(a, 2n) > 1. Choose x=2ngcd(a,2n) x = \frac{2n}{\gcd(a, 2n)} and y=0 y = 0 . Then:
x+y=2ngcd(a,2n)2n2=n. x + y = \frac{2n}{\gcd(a, 2n)} \leq \frac{2n}{2} = n.

- Case 2: If gcd(a,2n)=1\gcd(a, 2n) = 1 and gcd(b,2n)=1\gcd(b, 2n) = 1. Let c[0,2n1] c \in [0, 2n-1] such that cba1(mod2n) c \equiv ba^{-1} \pmod{2n} . The equation ax+by0(mod2n) ax + by \equiv 0 \pmod{2n} is equivalent to x+cy0(mod2n) x + cy \equiv 0 \pmod{2n} . Choose y=2nc y = \left\lfloor \frac{2n}{c} \right\rfloor and x=2nc2nc x = 2n - c \left\lfloor \frac{2n}{c} \right\rfloor .

- Subcase 2.1: If 2<c<n 2 < c < n , then:
x+yc1+2nc<c1+2nc=(c2)(cn)c+n+1<n+1. x + y \leq c - 1 + \left\lfloor \frac{2n}{c} \right\rfloor < c - 1 + \frac{2n}{c} = \frac{(c-2)(c-n)}{c} + n + 1 < n + 1.
Hence, x+yn x + y \leq n .

- Subcase 2.2: If cn+1 c \geq n + 1 , then:
x+y=2n(c1)2nc=2n(c1)2n(n+11)=n. x + y = 2n - (c-1) \left\lfloor \frac{2n}{c} \right\rfloor = 2n - (c-1) \leq 2n - (n+1-1) = n.
Hence, x+yn x + y \leq n .

In conclusion, the smallest positive number m m that satisfies the given conditions is n n . The answer is n\boxed{n}.

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.