7
$\begingroup$

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?

  • 1
    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 http://math.stackexchange.com/questions/266337/smallest-possible-value-on-fibonacci-function and http://math.stackexchange.com/questions/238677/determining-the-number-n - Calvin Lin Mathematics Challenge Master2012-12-29

2 Answers 2

2

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$

  • 0
    @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.2012-11-14
-1

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