Maximum of the difference

Question

What is the maximum value of $f(… f(f(f(x_{1} – x_{2}) – x_{3})-x_{4}) … – x_{2012})$ where $x_{1}, x_{2}, … , x_{2012}$ are distinct integers in the set ${1, 2, 3, …, 2012}$ and $f$ is the absolute value function?

Answer 1

I am solving with respect to the general case that is $$\max_{\substack{ {x_i\in\{1,2,...,n\}\\ x_i\ne x_j,\ i\ne j}}} f(… f(f(f(x_{1} – x_{2}) – x_{3})-x_{4}) … – x_{n}), \quad f(x)=|x|$$

Since we are looking for a maximum solution, then it is sufficient to distribute the numbers $$1,2,3,...,n$$ in an order so that we get a maximum value for any value of $n$ and that order is what I explained below.

Consider the case where $\forall k=1,2,\ ...,\ n-1$ we have $x_k=n-k$ and $x_n=n$ i.e $x_1=n-1$, $x_2=n-2$, $x_3=n-3$ $ , ..., $ $x_k=n-k$ $, ...,$ $ x_{n-1}=1$ but $x_n=n$.

So that for $n=8$ for example, we compute the value of $f(f(f(f(f(f(f(7-6)-5)-4)-3)-2)-1)-8)$

Let $f_1=x_1$, $f_2=(x_{1} – x_{2})$, $f_3=(f(x_{1} – x_{2}) – x_{3})$, $...,$ $f_{n }=f(… f(f(f(x_{1} – x_{2}) – x_{3})-x_{4}) … – x_{n})$

Using the following notation where $0\le n_4,k_4\le3$ $$\quad\quad \quad\quad\quad n\equiv n_4 \mod 4 \quad\quad\quad\text { and }$$ $$k \equiv k_4 \mod 4$$ we have the following pattern depending on the value of $n$ (it's preferable to work out some cases to verify what I wrote below). $$\boxed{\begin{array}{ll} f_1=n-1\\ f_2=1 \\ f_3=n- 4 \\ f_4=0 \end{array}} $$ $$ \boxed{f_{n-k}=\left\{\begin{array}{ll}1 \quad \quad \quad \quad \quad \quad\text { if } (n_4,k_4)=\{(0,2),(1,3),(2,0),(3,1)\} \\0 \quad \quad \quad \quad \quad \quad\text { if } n_4=k_4\\f_{n-k-4}+4 \end{array}\right.}$$ $$ \boxed{\begin{array}{ll}f_{n- 4 }=\left\{\begin{array}{ll}0 \quad\text { if } n_4= 0 \quad \\4 \quad\text { if } n_4= 1 \quad \\1 \quad\text { if } n_4= 2 \quad \\3 \quad\text { if } n_4= 3 \quad \end{array}\right.\\f_{n-3}=\left\{\begin{array}{ll}3 \quad\text { if } n_4= 0 \quad \\1 \quad\text { if } n_4= 1 \quad \\2 \quad\text { if } n_4= 2 \quad \\0 \quad\text { if } n_4= 3 \quad \end{array}\right.\\ f_{n-2}=\left\{\begin{array}{ll}1 \quad\text { if } n_4= 0,1 \\0 \quad\text { if } n_4= 2 \quad \\2 \quad\text { if } n_4= 3 \quad \end{array}\right.\\ f_{n-1}=\left\{\begin{array}{ll}0 \quad\text { if } n_4= 0,1 \\1 \quad\text { if } n_4= 2,3 \end{array}\right.\end{array}}$$

And lastly $$f_n=|f_{n-1}-x_n| = |f_{n-1}-n|=\left\{\begin{array}{ll}n&\text { if } n_4= 0,1 \\n-1&\text { if } n_4= 2,3 \end{array}\right.$$

$$2012\equiv 0 \mod 4 \quad \implies \quad f_{2012}=2012$$

Answer 2

I don’t know the answer, but I wrote some code that might help. My code is too slow to calculate the actual answer, with $2012$ in the problem. But if you replace $2012$ with the numbers $1$ through $10$, the answers to those 10 problems are [1, 1, 2, 4, 5, 5, 6, 8, 9, 9]. Maybe you can see a pattern in those solutions.

This CoffeeScript code calculates the answer with brute-force, trying all possible permutations and recording the maximum value. One function it provides is maximumValueForSetSize, which would return the answer if called with 2012 as the argument. But it runs in $O(n!)$ time, far too slowly to practically provide the answer to your problem. However, another function, maximumValuesForSetsUpTo, can provide data points for the results. It also runs in $O(n!)$ time, but this is reasonable because the function is still useful for small values of $n$. I used that function to calculate the 10 answers that I included above.

Here is the code. You can run it from this JS Bin. Scroll to the “useful calculations” section at the bottom and change the numbers if you want to experiment.

# environment setup

# this is CoffeeScript (http://coffeescript.org/)
# and I'm using the Underscore.js library (http://underscorejs.org/)

log = console.log

testFunctionUsingTestCases = (fun, funName, testCases) ->
  for testCase in testCases
    expectedResult = _(testCase).first()
    callArguments = _(testCase).rest()
    actualResult = fun.apply(undefined, callArguments)

    if ! _.isEqual(actualResult, expectedResult)
      log("test failed for function "+funName+" - arguments, expected, and actual:", callArguments, expectedResult, actualResult)
      return
  log("all tests passed for function "+funName)


# defining evaluatePermutation

absOfDifference = (num1, num2) ->
  Math.abs(num1 - num2)

# Big O: O(n) for n = permutation size
evaluatePermutation = (permutation) ->
  current = _(permutation).first()
  for number in _(permutation).rest()
    current = absOfDifference(current, number)
  return current
evaluatePermutationTestCases = [
  [1, [1]]
  [1, [1, 2]]
  [2, [1, 2, 3]]
  [2, [2, 1, 3]]
  [0, [3, 1, 2]]
  [0, [3, 2, 1]]
  [2, [1, 2, 3, 4]]
  [4, [1, 3, 2, 4]]
  [2, [2, 1, 3, 4]]
]
testFunctionUsingTestCases(evaluatePermutation, "evaluatePermutation", evaluatePermutationTestCases)


permute = `function(input) {
    var permArr = [],
    usedChars = [];
    function main(input){
        var i, ch;
        for (i = 0; i < input.length; i++) {
            ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length == 0) {
                permArr.push(usedChars.slice());
            }
            main(input);
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr
    }
    return main(input);
};` # from http://stackoverflow.com/a/11509565/578288

# Big O: O(n)
setWithSize = (size) ->
  [1..size]

# Big O: O(n!)
permutationsOfSetWithSize = (size) ->
  return _.compose(permute, setWithSize)(size)
permutationsOfSetWithSizeTestCases = [
  [[ [1] ], 1]
  [[ [1, 2],[2, 1] ], 2]
  [[ [1, 2, 3],[1, 3, 2],[2, 1, 3],[2, 3, 1],[3, 1, 2],[3, 2, 1] ], 3]
]
testFunctionUsingTestCases(permutationsOfSetWithSize, "permutationsOfSetWithSize", permutationsOfSetWithSizeTestCases)


# defining maximumValueForSetSize

# Big O: O(n*m) for n = num of permutations, m = permutation size
# evaluatePermutation is O(m)
# map is O(n)
# max is O(n)
maximumValueUsingPermutations = (permutations) ->
  return _.max( _(permutations).map(evaluatePermutation) )

# Big O: O(n!)
# maximumValueUsingPermutations is O(n^2)
# permutationsOfSetWithSize is O(n!)
maximumValueForSetSize = (size) ->
  return _.compose(maximumValueUsingPermutations, permutationsOfSetWithSize)(size)
maximumValueForSetSizeTestCases = [
  [1, 1]
  [1, 2]
  [2, 3]
]
testFunctionUsingTestCases(maximumValueForSetSize, "maximumValueForSetSize", maximumValueForSetSizeTestCases)


# defining maximumValuesForSetsUpTo

# Big O: O(n!)
maximumValuesForSetsUpTo = (maxSize) ->
  for size in [1..maxSize]
    maximumValueForSetSize(size)
maximumValuesForSetsUpToTestCases = [
  [[1, 1], 2]
  [[1, 1, 2], 3]
]
testFunctionUsingTestCases(maximumValuesForSetsUpTo, "maximumValuesForSetsUpTo", maximumValuesForSetsUpToTestCases)


# useful calculations

maxSize = 5
log("maximum values for sets of sizes up to #{maxSize}:", maximumValuesForSetsUpTo(maxSize) )

# this takes too long to run - estimated over a year
#idealSize = 2012
#log("maximum value for set of size #{idealSize}:",  maximumValueForSetSize(idealSize) )