Máximo de la diferencia

Question

¿Cuál es el valor máximo de $f(… f(f(f(x_{1} – x_{2}) – x_{3})-x_{4}) … – x_{2012})$ donde $x_{1}, x_{2}, … , x_{2012}$ son enteros distintos en el conjunto ${1, 2, 3, …, 2012}$ y $f$ es la función de valor absoluto?

Answer 1

Estoy resolviendo con respecto al caso general que es $$\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|$$

Como buscamos una solución máxima, basta con distribuir los números $$1,2,3,...,n$$ en un orden tal que obtengamos un valor máximo para cualquier valor de $n$ y ese orden es el que explico a continuación.

Consideremos el caso en el que $\forall k=1,2,\ ...,\ n-1$ tenemos $x_k=n-k$ y $x_n=n$ es decir $x_1=n-1$ , $x_2=n-2$ , $x_3=n-3$ $ , ..., $ $x_k=n-k$ $, ...,$ $ x_{n-1}=1$ pero $x_n=n$ .

De modo que para $n=8$ por ejemplo, calculamos el valor de $f(f(f(f(f(f(f(7-6)-5)-4)-3)-2)-1)-8)$

Dejemos que $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})$

Utilizando la siguiente notación donde $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$$ tenemos el siguiente patrón en función del valor de $n$ (es preferible elaborar algunos casos para verificar lo que escribí a continuación). $$\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}}$$

Y por último $$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

No sé la respuesta, pero he escrito un código que podría ayudar. Mi código es demasiado lento para calcular la respuesta real, con $2012$ en el problema. Pero si se sustituye $2012$ con los números $1$ a través de $10$ las respuestas a esos 10 problemas son [1, 1, 2, 4, 5, 5, 6, 8, 9, 9] . Quizás puedas ver un patrón en esas soluciones.

Este código CoffeeScript calcula la respuesta con fuerza bruta, probando todas las permutaciones posibles y registrando el valor máximo. Una función que proporciona es maximumValueForSetSize que devolverá la respuesta si se llama con 2012 como argumento. Pero se ejecuta en $O(n!)$ tiempo, demasiado lento para dar prácticamente la respuesta a su problema. Sin embargo, otra función, maximumValuesForSetsUpTo puede proporcionar puntos de datos para los resultados. También se ejecuta en $O(n!)$ tiempo, pero esto es razonable porque la función sigue siendo útil para valores pequeños de $n$ . Utilicé esa función para calcular las 10 respuestas que incluí arriba.

Aquí está el código. Usted puede ejecutarlo desde esta papelera JS . Desplázate hasta la sección de "cálculos útiles" en la parte inferior y cambia los números si quieres experimentar.

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