Let $A$ be a set contains $2000$ distinct integers and $B$ be a set contains $2016$ distinct integers. $K$ is the numbers of pairs $(m,n)$ satisfying \[ \begin{cases} m\in A, n\in B\\ |m-n|\leq 1000 \end{cases} \]Find the maximum value of $K$
Problem
Source: Vietnam TST 2016
Tags: combinatorics
Ankoganit
26.03.2016 11:00
Does the following solution work? I am not too sure....... EDIT: thanks rtete for pointing out.
Let $A_1<A_2<A_3<\cdots <A_{2000}$ be the elements of $A$ and $B_1<B_2<\cdots <B_{2016}$ be the elements of $B$. Now we transform $A$ and $B$ in several steps as follows:
$\to$ If in some stage, $A_1\le B_1$, then take the largest $p$ such that $A_1,A_2,\cdots A_p$ form a block of consecutive integers. Then take $A'=\{A_i+1|1\le i\le p\}\cup \{A_i|p<i\le 2000\}$. $B'= B$ in this case.
$\to$ If $A_1>B_1$ instead, then take the largest $p$ such that $B_1,B_2,\cdots B_p$ form a block of consecutive integers. Then $B'=\{B_i+1|1\le i\le p\}\cup \{B_i|p<i\le 2016\}$. $A'=A$ in this case.
After each step, $A'$ and $B'$ become $A$ and $B$ for the next step.
It is easily verified that $K$ never decreases at each step. It is also obvious that after finitely many steps, each of $A$ and $B$ will consist of consecutive numbers and satisfy $A_1=B_1$. Since only differences in values matter, we can take WLOG $A_1=B_1=1$. In that case $A=\{1,2,...,2000\}$ and $B=\{1,2,...,2016\}$. It can be easily calculated that $K=3016880$ in this case. Therefore this is the required maximum.
rterte
28.03.2016 10:20
Set $A=\{9,10,...,2008\}$ and $B=\{1,2,...,2016\}$ gives $K=3016944$
don2001
30.07.2016 15:24
Could you please give me some guidance ? Thank you.
don2001
06.08.2016 19:09
Help me please
gausskarl
07.04.2017 16:49
I think the problem is stated more accurately as follows: Let $K$ be the numbers of ordered pairs...
don2001
31.07.2017 18:53
solution https://math.stackexchange.com/questions/2230079/maximum-number-of-integers-m-n-in-a-times-b-such-that-m-n-leq-1000