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.

15 comentarios

Dani | 2 de November de 2010 | 09:03

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 )
Trackback | 2 Nov, 2010

Tweets that mention Menor valor | Gaussianos -- Topsy.com
Gulliver | 2 de November de 2010 | 14:43

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.
M | 2 de November de 2010 | 18:07

pues vaya si lo resolvió con rapidez
Trackback | 2 Nov, 2010

Bitacoras.com
RS | 3 de November de 2010 | 02:16

Mínimo(a1a2a3+a4a5a6+a7a8a9)=774

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

Y así hasta 36 resultados.
Lecter | 3 de November de 2010 | 05:47

¿Como se deduce la desigualdad que ocuparon al principio?
¿Alguien sabe?

Saludos!
Dani | 3 de November de 2010 | 06:58

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?
josejuan | 3 de November de 2010 | 10:59

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…
orlin | 3 de November de 2010 | 11:16

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???.
Gulliver | 3 de November de 2010 | 19:11

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.
Dani | 3 de November de 2010 | 19:24

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$ .
Lecter | 4 de November de 2010 | 01: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.
josejuan | 4 de November de 2010 | 20:26

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, …
josejuan | 4 de November de 2010 | 20:30

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