# Maximum of the difference

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?

-
Seeing that the indices go up to the current year, I can't help but think this is a question from a recent competition. Could you please provide some context when you ask questions like this, so that we can be sure it's not an ongoing competition? – Arthur Nov 11 '12 at 11:51
The above question is posted as a Challenge problem on Brilliant.org, which offers weekly problem sets to test student's problem solving abilities. John Chang has been posting questions on math.stackexchange.com and expecting others to solve the problems for him. He has posted more of our questions at math.stackexchange.com/questions/266337/… and math.stackexchange.com/questions/238677/… - Calvin Lin Mathematics Challenge Master – Calvin Lin Dec 29 '12 at 1:10

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$$

-
I’m confused by your notation – I think you’ve overloading subscript too much. Inside your definition of $f$, I thought that the $x_1$, $x_2$, etc. were just numbered placholders. But in the first paragraph, you seem to define a new meaning of subscript. When you define $x_k$, are you defining a new notation, or are you claiming that $x_1$, etc. in your definition of $f$ always follow that pattern? And does your definition of $x_k$ apply to terms like “$n_4$”, or does the first variable have to be $x$? … – Rory O'Kane Nov 14 '12 at 1:42
… I think your explanation would be clearer if it were written with different notation. You could use function notation (change $x_k$ to $d(x, k)$), or you could expand $x_k$ into $(n-k)$ if your new notation is just for conciseness. – Rory O'Kane Nov 14 '12 at 1:43
(Though I don’t understand this explanation, its general solution at the end gives solutions for $f_1$ through $f_{10}$ that match the solutions given by my brute-force solver. So that general solution is probably correct.) – Rory O'Kane Nov 14 '12 at 1:50
@RoryO'Kane I used the notation $n_4$ and $k_4$ so i won't have to write $\mod 4$ every time and it actually simplified my generalization. I've edited the solution, check to see if you understand it better. – user31280 Nov 14 '12 at 5:34

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) )

-