Menor valor

Vamos con el problema de esta semana. A ver si después de este fin de semana largo tenemos la cabeza lo suficientemente centrada como para resolver con rapidez:

Determinar el menor valor posible que toma la expresión

a_1\cdot a_2\cdot a_3+a_4\cdot a_5\cdot a_6+a_7\cdot a_8\cdot a_9

siendo a_1,\ldots,a_9 una permutación de 1,2,3,\ldots,9.

A por él.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

13 Comentarios

  1. Por la desigualdad aritmetico geometrica
    a_1a_2a_3+a_4a_5a_6+a_7a_8a_9\geq 3(a_1a_2\cdots a_9)^{\frac{1}{3}}=3(9!)^{\frac{1}{3}}>213
    por lo tanto la expresion siempre toma valor mayor o igual que 214.
    Por otra parte 1\cdot 8\cdot 9+2\cdot 5 \cdot 7 + 3 \cdot 4 \cdot 6 = 214 , de modo que este es valor pedido.

    (jajajaj hacia tiempo que no cogia uno de estos a tiempo 🙂 )

    Publica una respuesta
  2. Además esos productos que ha encontrado Dani son los únicos que minimizan la expresión. Si buscamos otros tres productos de tres números que sumen 214 y su producto sea  9! , a partir de la desigualdad

     a_4 a_5 a_6 + a_7 a_8 a_9 \ge 2(a _4 a_5 a_6 a_7 a_8 a_9)^{\frac{1}{2}} ,

    se puede encontrar que

     a_1 a_2 a_3 ( 214 - a_1 a_2 a_3)^2 - 4 \cdot 9! \ge 0 ,

    y lo mismo para los demás productos.

    Analizando el polinomio se puede ver que los únicos valores posibles de los productos  a_1 a_2 a_3 ,  a_4 a_5 a_6 y  a_7 a_8 a_9 son 70 y 72 y los valores que ha encontrado Dani son los únicos que pueden dar esos productos.

    Publica una respuesta
  3. Mínimo(a1a2a3+a4a5a6+a7a8a9)=774

    147+258+369
    147+259+368
    147+268+359
    147+269+358

    Y así hasta 36 resultados.

    Publica una respuesta
  4. ¿Como se deduce la desigualdad que ocuparon al principio?
    ¿Alguien sabe?

    Saludos!

    Publica una respuesta
  5. Lecter, puedes ver varias pruebas aqui: http://es.wikipedia.org/wiki/Desigualdad_de_las_medias_aritmética_y_geométrica
    aunque no es de las mas bonitas. Hay mas en la wiki inglesa y hay una demostracion usando teoria de la medida que es fantastica. Si a alguien le interesa la cuento.

    Creo que es interesante preguntarse la siguiente generalizacion: Si fijamos n \in \mathbb{N} y d un divisor de n , cual es el minimo valor que puede alcanzar la expresion:
    \sum_{k=0}^{d-1} \Big(\prod_{j=1}^{\frac{n}{d}}\sigma (j+k\frac{n}{d}) \Big)
    tomando \sigma \in S_n ?

    Una vez mas por la desigualdad aritmetico geometrica vemos que nunca va a poder ser menor que d(n!)^{1/d}, pero no esta nada claro que se pueda alcanzar el valor entero inmediatamente mayor (o igual) que esta cota…

    alguna idea?

    Publica una respuesta
  6. El problema me recuerda al “subset sum”, se trata de hacer que todos los sumandos tengan el mismo valor (el más parecido posible).

    Creo que es un problema de combinatoria…

    Aunque en este caso los elementos que intervienen son conocidos (de 1 a n), igual hay una propiedad por ahí…

    ——————————

    Si d=1 o d=n o n es primo (d=1 o n) la solución es trivial (todo sumas o todo productos).

    En otro caso, para obtener soluciones únicas podemos ordenar los sumandos por aquel que tiene el menor número al mayor, y dentro de cada sumando por el menor número al mayor.

    Así, por ejemplo, usando fuerza bruta tenemos:

    SOLVE( 4, 2 ) := 10
    1 * 4 + 2 * 3
    SOLVE( 6, 2 ) := 28
    1 * 6 + 2 * 5 + 3 * 4
    SOLVE( 6, 3 ) := 54
    1 * 4 * 6 + 2 * 3 * 5
    1 * 5 * 6 + 2 * 3 * 4
    SOLVE( 8, 2 ) := 60
    1 * 8 + 2 * 7 + 3 * 6 + 4 * 5
    SOLVE( 8, 4 ) := 402
    1 * 4 * 6 * 8 + 2 * 3 * 5 * 7
    1 * 5 * 6 * 7 + 2 * 3 * 4 * 8
    SOLVE( 9, 3 ) := 214
    1 * 8 * 9 + 2 * 5 * 7 + 3 * 4 * 6
    SOLVE( 10, 2 ) := 110
    1 * 10 + 2 * 9 + 3 * 8 + 4 * 7 + 5 * 6
    SOLVE( 10, 5 ) := 3810
    1 * 3 * 7 * 9 * 10 + 2 * 4 * 5 * 6 * 8
    1 * 4 * 6 * 8 * 10 + 2 * 3 * 5 * 7 * 9
    1 * 5 * 6 * 7 * 9 + 2 * 3 * 4 * 8 * 10
    SOLVE( 12, 2 ) := 182
    1 * 12 + 2 * 11 + 3 * 10 + 4 * 9 + 5 * 8 + 6 * 7
    SOLVE( 12, 3 ) := 594
    1 * 11 * 12 + 2 * 8 * 9 + 3 * 5 * 10 + 4 * 6 * 7
    1 * 11 * 12 + 2 * 7 * 10 + 3 * 6 * 9 + 4 * 5 * 8
    1 * 11 * 12 + 2 * 8 * 10 + 3 * 6 * 9 + 4 * 5 * 7
    SOLVE( 12, 4 ) := 2348
    1 * 7 * 10 * 11 + 2 * 4 * 8 * 12 + 3 * 5 * 6 * 9
    1 * 6 * 11 * 12 + 2 * 5 * 8 * 10 + 3 * 4 * 7 * 9
    1 * 7 * 9 * 12 + 2 * 5 * 8 * 10 + 3 * 4 * 6 * 11
    SOLVE( 12, 6 ) := 43776
    1 * 3 * 7 * 8 * 11 * 12 + 2 * 4 * 5 * 6 * 9 * 10
    1 * 4 * 5 * 9 * 10 * 12 + 2 * 3 * 6 * 7 * 8 * 11
    1 * 4 * 6 * 7 * 11 * 12 + 2 * 3 * 5 * 8 * 9 * 10
    1 * 4 * 7 * 8 * 9 * 11 + 2 * 3 * 5 * 6 * 10 * 12
    1 * 5 * 6 * 8 * 9 * 10 + 2 * 3 * 4 * 7 * 11 * 12

    y vemos que (por ejemplo) el problema N=10, d=2 es difícil, porque ha obligado a hacer la partición 10 + 18 + 24 + 28 + 30, que se aleja mucho del punto de partida 22 + 22 + 22 + 22 + 22.

    Lo peor es que según aumenta el número de sumandos, las particiones son mucho mayores…

    ———————————-

    Igual hay un método directo, pero me da que sólo queda optimizar el algoritmo para generar las soluciones…

    Publica una respuesta
  7. Veo que la suma geométrica es menor que la aritmética. Pero de donde se saca que es el mínimo valor??. Por definicion, si se tiene un conjunto de sumandos su valor mínimo va a ser su media geométrica???.

    Publica una respuesta
  8. Siempre es interesante ver otras maneras de resolver el problema, se me ocurre una que es más laboriosa, pero tiene algunas ventajas: Permite deducir los valores que minimizan la suma y además demostrar que los valores que encuentra Dani son únicos salvo permutaciones triviales. Por otra parte es un método entretenido, donde hay que recurrir a la lógica, tipo Sodoku, tanteando hasta llegar a la solución final.

    El método se basa en una propiedad que ha de cumplir la solución. Supongamos que tenemos dos de los sumandos de la solución  x \cdot a \cdot b y  y \cdot c \cdot d , con  x > y . Como forman parte de la solución minimizadora, la suma no disminuirá cuando permutemos  x e  y .

     y \cdot a \cdot b + x \cdot c \cdot d - x \cdot a \cdot b + y \cdot c \cdot d =  (x-y) (c \cdot d - a \cdot b) \ge 0

    y por tanto  c \cdot d \ge a \cdot b .

    A  a \cdot b que es el producto de las dos variables que están en el mismo terceto que  x , le voy a llamar producto complementario de  x . Dada la propiedad de arriba, si ordenamos las variables individuales en orden creciente, los productos complementarios estarán ordenados en orden decreciente. Por ejemplo para la solución que encuentra Dani   1 \cdot 8 \cdot 9 + 2 \cdot 5 \cdot 7 + 3 \cdot 4 \cdot 6  , las variables y sus productos complementarios son:

    \begin{array}{rrrrrrrrr } 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 72 & 35 & 24 & 18 & 14 & 12 & 10 & 9 & 8 \end{array}

    Con esta propiedad ya es únicamente cuestión de ir haciendo deducciones lógicas. Por ejemplo para demostrar que el 9 va en el mismo producto que el 1, podemos empezar suponiendo que no es así y llegar a una contradicción.

    Supongamos que el 9 y el 1 van en productos diferentes. Por un lado  1 \cdot a_1  \cdot a_2 y por otro  9 \cdot b_1  \cdot b_2 , con  a_1 > a_2 . Como  9 > a_1 ,  b_1 \cdot b_2 \le a_2 \le 7 el único producto que puede acomodar  b_1 \cdot b_2 es  2 \cdot 3 . Por otro lado haré una comprobación similar entre el segundo producto  9 \cdot 2 \cdot 3 y el tercero  c_1 \cdot c_2 \cdot c_3 . El producto complementario de 3 es 18, luego el producto complementario de  c_1 ha de ser menor o igual que este valor, sin embargo ya no quedan números para el tercer producto que puedan dar un producto complentario menor o igual que 18. Luego la premisa de que 9 y 1 van en productos diferentes es falsa.

    Siguiendo con las deducciones se puede demostrar que 8 va en el mismo producto que 1 y 9, y que 7 y 5 van en el mismo producto que 2. Es un puro entretenimiento de lógica.

    Publica una respuesta
  9. Pues si que es interesante porque la “solucion minimizadora” la encontre a ojo tanteando para que los tres productos fuesen lo mas parecidos posibles, pero si tuviesemos una expresion mas complicada seria imposible proceder de esta manera y habria que recurrir a un algoritmo como el que acabas de mostrar (evidentemente el algoritmo de probar todas las cominaciones es una locura- requiere un numero de computaciones que crece desorbitadamente con n).
    Me pregunto si serias capaz de generalizar este algoritmo para el problema que he propuesto y si el numero de computaciones necesarias puede acotarse de manera razonable (por ejemplo polinomica) con n.

    Publica una respuesta
  10. Gracias, bueno yo conocía la demostración por inducción, pero no es de las mas sutiles que digamos jaja, saludos y nuevamente gracias.

    Publica una respuesta
  11. Con el resultado de @Gulliver se prueba que para todas las expresiones en que los sumandos están formados por dos multiplicandos, su solución es única (salvo permutaciones de términos y de multiplicandos dentro de cada término) y además, son de la forma:

    S(N)=\sum_{i=1}^{\frac{N}{2}}i(N-i+1)=1N+2(N-1)+\cdot \cdot \cdot +\frac{N}{2}(N-\frac{N}{2}+1)

    es decir

    S(N)=\allowbreak \frac{1}{12}N\left( N+1\right) \left( N+2\right)

    (es claro que N debe ser par para poder agrupar por parejas).

    Así, para cada N existe una expresión para el mínimo buscado, para agrupaciones de 1 cifras, N cifras y 2 cifras.

    Ya sólo falta el resto de divisores de N, ja, ja, …

    Publica una respuesta
  12. Conjetura:

    Para N cifras (de 1 a N) agrupadas en términos de d multiplicandos, existe una permutación con valor mínimo de la forma:

    1a_{1}+2a_{2}+\cdot \cdot \cdot +\frac{N}{d}a_{\frac{N}{d}}

    Publica una respuesta

Trackbacks/Pingbacks

  1. Tweets that mention Menor valor | Gaussianos -- Topsy.com - [...] This post was mentioned on Twitter by gaussianos and Ciencia Tecnología, redes sociales web. redes sociales web said: #hispaciencia…
  2. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Vamos con el problema de esta semana. A ver si después de este fin…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *