An integer $n>1$ is given . Find the smallest positive number $m$ satisfying the following conditions： for any set $\{a,b\}$ $\subset \{1,2,\cdots,2n-1\}$ ,there are non-negative integers $ x, y$ ( not all zero) such that $2n|ax+by$ and $x+y\leq m.$
Problem
Source: China Shanghai ,Mar 12, 2017
Tags: number theory, algebra, China TST
math90
12.03.2017 20:31
The answer is $n$.
Consider $a=1$, $b=2$. If $2n\mid ax+by$, then
$2n\leq x+2y\leq 2(x+y)\leq 2m$
Hence $m\geq n$.
It remains to show that $m\leq n$.
Let $a,b\in\{1,2,\cdots,2n-1\}$ be fixed.
Case 1: $\gcd(a,2n)>1$ or $\gcd(b,2n)>1$.
WLOG $\gcd(a,2n)>1$. Choose $x=\frac{2n}{\gcd(a,2n)}$, $y=0$. Then $x+y=\frac{2n}{\gcd(a,2n)}\leq\frac{2n}{2}=n$.
Case 2: $\gcd(a,2n)=1$ and $\gcd(b,2n)=1$.
Let $c\in[0,2n-1]$ such that $c=ba^{-1}\pmod{2n}$. The equation $ax+by\equiv 0\pmod{2n}$ is equivalent to $x+cy\equiv 0\pmod{2n}$.
Choose $y=\lfloor\frac{2n}{c}\rfloor$, $x=2n-c\lfloor\frac{2n}{c}\rfloor$. Since $a\neq b$ we have $c\geq 2$. Also $c\nmid 2n$, since $c>1$ and $\gcd(c,2n)=1$. In particular $c\notin\{1,2,n\}$.
Case 2.1: $2<c<n$. We have
$x+y\leq c-1+y<c-1+\frac{2n}{c}=\frac{(c-2)(c-n)}{c}+n+1<n+1$. Hence $x+y\leq n$.
Case 2.2: $c\geq n+1$. We have
$x+y=2n-(c-1)\lfloor\frac{2n}{c}\rfloor=2n-(c-1)\leq 2n-(n+1-1)=n$. Hence $x+y\leq n$.
In total, we conclude that $m\leq n$.
sqing
13.03.2017 10:20
math90 wrote:
The answer is $n$.
Consider $a=1$, $b=2$. If $2n\mid ax+by$, then
$2n\leq x+2y\leq 2(x+y)\leq 2m$
Hence $m\geq n$.
It remains to show that $m\leq n$.
Let $a,b\in\{1,2,\cdots,2n-1\}$ be fixed.
Case 1: $\gcd(a,2n)>1$ or $\gcd(b,2n)>1$.
WLOG $\gcd(a,2n)>1$. Choose $x=\frac{2n}{\gcd(a,2n)}$, $y=0$. Then $x+y=\frac{2n}{\gcd(a,2n)}\leq\frac{2n}{2}=n$.
Case 2: $\gcd(a,2n)=1$ and $\gcd(b,2n)=1$.
Let $c\in[0,2n-1]$ such that $c=ba^{-1}\pmod{2n}$. The equation $ax+by\equiv 0\pmod{2n}$ is equivalent to $x+cy\equiv 0\pmod{2n}$.
Choose $y=\lfloor\frac{2n}{c}\rfloor$, $x=2n-c\lfloor\frac{2n}{c}\rfloor$. Since $a\neq b$ we have $c\geq 2$. Also $c\nmid 2n$, since $c>1$ and $\gcd(c,2n)=1$. In particular $c\notin\{1,2,n\}$.
Case 2.1: $2<c<n$. We have
$x+y\leq c-1+y<c-1+\frac{2n}{c}=\frac{(c-2)(c-n)}{c}+n+1<n+1$. Hence $x+y\leq n$.
Case 2.2: $c\geq n+1$. We have
$x+y=2n-(c-1)\lfloor\frac{2n}{c}\rfloor=2n-(c-1)\leq 2n-(n+1-1)=n$. Hence $x+y\leq n$.
In total, we conclude that $m\leq n$.
Thanks.
smy2012
13.03.2017 13:32
math90 wrote:
The answer is $n$.
Consider $a=1$, $b=2$. If $2n\mid ax+by$, then
$2n\leq x+2y\leq 2(x+y)\leq 2m$
Hence $m\geq n$.
It remains to show that $m\leq n$.
Let $a,b\in\{1,2,\cdots,2n-1\}$ be fixed.
Case 1: $\gcd(a,2n)>1$ or $\gcd(b,2n)>1$.
WLOG $\gcd(a,2n)>1$. Choose $x=\frac{2n}{\gcd(a,2n)}$, $y=0$. Then $x+y=\frac{2n}{\gcd(a,2n)}\leq\frac{2n}{2}=n$.
Case 2: $\gcd(a,2n)=1$ and $\gcd(b,2n)=1$.
Let $c\in[0,2n-1]$ such that $c=ba^{-1}\pmod{2n}$. The equation $ax+by\equiv 0\pmod{2n}$ is equivalent to $x+cy\equiv 0\pmod{2n}$.
Choose $y=\lfloor\frac{2n}{c}\rfloor$, $x=2n-c\lfloor\frac{2n}{c}\rfloor$. Since $a\neq b$ we have $c\geq 2$. Also $c\nmid 2n$, since $c>1$ and $\gcd(c,2n)=1$. In particular $c\notin\{1,2,n\}$.
Case 2.1: $2<c<n$. We have
$x+y\leq c-1+y<c-1+\frac{2n}{c}=\frac{(c-2)(c-n)}{c}+n+1<n+1$. Hence $x+y\leq n$.
Case 2.2: $c\geq n+1$. We have
$x+y=2n-(c-1)\lfloor\frac{2n}{c}\rfloor=2n-(c-1)\leq 2n-(n+1-1)=n$. Hence $x+y\leq n$.
In total, we conclude that $m\leq n$.
Mine the same
siddigss
13.03.2017 16:36
I hope this one is correct ! Let $a,b\in\{1,...,2n-1\}$ be different. If one of them is even, say $a$, we simply take $x=n,y=0$. Assume that both $a$ and $b$ are odd. The set $\{(k,k)|0\leq k< n\}\cup\{(k,k+1)|0\leq k\leq n-1\}\cup\{(k,k+2)|0\leq k\leq n-2\}$ has $3n-1>2n$ pairs, therefore there are pairs $(k,k')$ and $(r,r')$ such that $ka+k'b\equiv ra+r'b\pmod{2n}$. If $k=r$, we are done by taking $x=0,y=|k'-r'|$. If $k=r+1$ and $r'>k'$, we must have $r'-k'=1$, so we have $x-y\equiv 0\pmod{2n}$ which is impossible. In other cases we have $k> r$ and $k'\geq r'$. Let $s=k-r$ and $t=k'-r'$. Note that $0<s<n$ and $0\leq t\leq n$. If $s+t\leq n$, we are done by taking $x=s,y=t$. Otherwise we take $x=n-s,y=n-t$. This proves that $m\leq n$ if $a$ and $b$ are not allowed to be equal! If they are allowed, then $m=2n$ ( We simply take $a=b=1$ and find $2n|x+y\leq m$)