-1
$\begingroup$

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$

Axel Kemper's wise idea simplified this problem.

From his answer, I'll calculate the value of $K$ by hand.

$K$ = number of lattice points $(m,n)$ in the intersection area

Intersection area = area of rectangle - area of two triangles at left upper and right lower corner

Since lines n=m+1000 and n=m-1000 are parallel to line n=m, so the two triangles are right isoceles triangles which there are 1007 points on triangle leg (from -1 to -1007 for left upper triangle).

Number of lattice points in rectangular area = $2000\cdot2016$.

Number of lattice points in two right isoceles triangles = $2\cdot (1007+1006+...+1) = 1007\cdot1008$

$K = 2000\cdot2016 - 1007\cdot1008 = 3,016,944$

$\endgroup$
4
$\begingroup$

Without the constraint $|m-n|\leq 1000$, the potential $(m, n)$ pairs would form a rectangular area of points in a 2D $(m, n)$ diagram. You can stretch the rectangle by introducing gaps in the values in $A$ and $B$. The most compact form of the rectangle with a maximum of pair points per area would result if the integer sets $A$ and $B$ do not have any gaps.

Constraint $|m-n|\leq 1000$ can be represented by the area delimited by two parallel lines $n = m + 1000$ and $n = m - 1000$.

The intersection between the above described gap-less rectangle and the inequality area is maximized if the center of the rectangle is located along the middle line $n = m$. Therefore, we can assume $n = m = 0.5$ as center. This results in $A = \{-999, -998, ... 999, 1000\}$ and $B = \{-1007, -1006, ... 1007, 1008\}$.

It should now be not too difficult to calculate the number of pairs in the intersection area. Iterate $m$ from minimum to maximum and sum up the number of allowed values for $n$, depending on $m$.

My computer tells me: $K = 3016944$

$\endgroup$
  • $\begingroup$ Thank you, Axel. Does gap-less mean "consecutive integers" ? $\endgroup$ – carat Apr 12 '17 at 17:29
  • $\begingroup$ @carat Yes, consecutive is the correct term. $\endgroup$ – Axel Kemper Apr 12 '17 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.