# Decrease distance between max and min

Let $a:=(a_1,a_2,\ldots,a_n) \in \mathbb{Z}^n$ and $k \in \mathbb{N}^*$, with

$$f: \begin{cases} \hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\ \hfill ((a_1,a_2,\ldots,a_n), k) \hfill & \mapsto (b_1,b_2,\ldots,b_n)\\ \end{cases}$$

$f$ satisfies the following constraints:

1. $(\forall b_{i=1,2,\ldots,n}\in \mathbb{Z})(\exists! a_{j=1,2,\ldots,n}\in \mathbb{Z}): b_i= a_j \pm k$
2. $b_{\max} - b_{\min} \le a_{\max} - a_{\min}$

The task is to find a function $f$(or an algorithm) that satisfies the listed constraints. Could anyone give some hints how can I deal with this problem?

Examples:

Example 1: $$f((1,7),4)=(5,3)$$ First constraint: $$5 = 1 + 4$$ $$3 = 7 - 4$$

Second constraint: $$5 - 3 \le 7 - 1$$

Example 2: $$f((1,2,3,4,5,6,7),5)=(6,7,\ldots,12)$$ First constraint: $$6 = 1 + 5$$ $$7 = 2 + 5$$ $$\vdots$$ $$12 = 7 + 5$$ Second constraint: $$12 - 6 \le 7 - 1$$

I tried to solve this problem algorithmically. The following is an implementation using JAVA

public class MinDiff
{
public static void main(String[] args)
{
int A[] = {1,7};
int k = 4;
System.out.println("Input a:=" + Arrays.toString(A) + ", k:=" + k);
int d = find(A, k);
System.out.println("Output a´:=" + Arrays.toString(A));
System.out.println("Maximum difference is " + d);
}

private static int find(int a[], int k)
{
Arrays.sort(a);

int n = a.length;
System.out.println("Maximum difference is " + (a[n - 1] - a[0]));

if (k >= a[n - 1] - a[0])
{
for (int i = 0; i < n; i++)
a[i] += k;
return a[n - 1] - a[0];
}

a[0] = a[0] + k;
a[n - 1] = a[n - 1] - k;

int max = Math.max(a[0], a[n - 1]);
int min = Math.min(a[0], a[n - 1]);

for (int index = 1; index < n - 1; index++)
{
if (a[index] < min)
a[index] += k;
else if (a[index] > max)
a[index] -= k;
else if ((a[index] - min) > (max - a[index]))
a[index] -= k;
else
a[index] += k;

max = Math.max(a[index], max);
min = Math.min(a[index], min);
}

return  max - min;
}


The above implementation fail to give a solution for the following input: $$a:=(1,2,\ldots,7) \text{ and } k:=5$$

Generally I´m interedted in the following questions: Let $a:=(a_1, a_2, \ldots, a_n) \in \mathbb{Z}^n \text{ and } k \in \mathbb{N}^*$

• What is the minimal distance that can we achieve? Could we answer this question a priori?
• Could we also a priori answer the following question: Does $k$ lead $a$ to an increase or decrease(the $2^{th}$ constraint)

• 3. I can't tell what constraint 1 is trying to say. What does the notation $\forall b_{i=1,2,\ldots,n}\in \mathbb{Z}$ mean? I know what the notation $\forall b \in \mathbb{Z}$ means, but I have no idea how to interpret that subscript. Can you rephrase, without using that notation in the subscript? 4. Also, can you elaborate what $\exists!$ means? I can think of two different meanings (there is a single value for $a_j$ that makes the statement valid; or, out of all of $a_1,\dots,a_n$, there is a single $j$ such that $a_j$ makes the statement valid). Please edit to clarify. Thank you! – D.W. May 29 '16 at 22:55
• 4. If I understand correctly, there is no $f$ that satisfies all of the constraints. What is the value of $f((1,1,1),42)$ supposed to be? There seems to be no acceptable value for $f$ on this input. What about $f((0,20),10)$? Again, there seems to be no acceptable output for this input. – D.W. May 29 '16 at 22:59