Name of this proof (1 Viewer)

[...]

Guys, I'm currently working on my programming assignment and I need to write a report on it.
I need some help for this little maths statement. I remember seeing something like this in Year 8/9, but it was only as a trivial stuff. In here, I actually want to see a proof, or at least know the name of this proof.

Suppose you have a list of numbers, say S. Where S = {1,4,9,16,25,36,49,64}
You have another list of numbers, say T. Where T = {1,2,3,4,5,6,7,8}

An element from S, is multiplied with another element from T. And each element can only multiply the other element from the other list once.
I need to proof, or at least show that in the smallest possible sum of these multiples, is when the largest integer from one set, is multiplied with the smallest integer from the other set.

Any help is appreciated

Thanks

 

[OmegaSTealth]

I'm not quite sure exactly how one would go about this without working out the sums of products of each combination, that is, to actually prove it; but it does seem common sense to me that the smallest sum would be formed by s1*t8+s2*t7+s3*t6+s4*t5+s5*t4+s6*t3+s7*t2+s8*t1, ie when the smallest term of S is multiplied by the largest term of T etc.

The smallest multiples can be made when the smallest elements of each set are multiplied together, so take the first elements of each set and multiply them. Treat the remaining elements in S as a subset of S and the same with T. Now repeat the process, multiplying the smallest elements of each set together, and eventually you get the expression above.

I suppose that this is a proof of sorts; it relies on the assumption that if
a is less than b, and
c is less than d, then
(a+c)<(b+d),
which can be taken as true here coz we're working with natural numbers. Hope this helps!

 

[airie]

By the Rearrangement Inequality, it is proven

I don't know if you can just say that for your question though, as in, if you can just take it that the marker would know about the inequality. I just know that it's often used, mostly in conjunction with others, to solve olympiad questions, and for those you don't need to prove the inequality again.

 

[who_loves_maths]

Guys, I'm currently working on my programming assignment and I need to write a report on it.
I need some help for this little maths statement. I remember seeing something like this in Year 8/9, but it was only as a trivial stuff. In here, I actually want to see a proof, or at least know the name of this proof.

Suppose you have a list of numbers, say S. Where S = {1,4,9,16,25,36,49,64}
You have another list of numbers, say T. Where T = {1,2,3,4,5,6,7,8}

An element from S, is multiplied with another element from T. And each element can only multiply the other element from the other list once.
I need to proof, or at least show that in the smallest possible sum of these multiples, is when the largest integer from one set, is multiplied with the smallest integer from the other set.

Any help is appreciated

Thanks

Hi ... , hope this is still in time to be of some help to you.

From what I can see, there are three ways of (formally) solving this problem: 1) Calculus, 2) Geometry, or 3) Inequalities; all of them beyond HS level mathematics.

Since in mathematics any geometrical solution is usually the most intuitive and less abstract method of problem solving, I will attempt to outline such a proof below:

The key to converting this problem in number theory to a more geometric form is to consider all permutations of the sets T and S as ordered-tuple vectors in n-dimensional space, Rⁿ (in this case, n = 8 for the sample sets you drew up).

Let the vector space which contain the vectors formed from all possible permutations of sets T and S be equipped with the Euclidean norm and Euclidean inner[dot] product of its parent space R⁸.

Let us keep the vector t = (1, 2, ..., 8) fixed (compare this with the set T = {1, 2, ..., 8} and the change of notation) so that we only need to consider all the permutations of the set S = {1, 4, ..., 64} as coordinates that form the variable vector s.

For all general permutation sets S_permt. = {(s₁, ..., s₈)} of S where s_i belongs to S, we observe that under the Euclidean norm ||s|| is constant for any s in S_permt. (this is because the coordinates of s all come from the set S which has eight fixed values).

Since t is fixed, we need to find a vector s such that the sum t₁s₁ + t₂s₂ + ... + t₈s₈ is a minimum.

But the sum t₁s₁ + t₂s₂ + ... + t₈s₈ is precisely the natural Euclidean inner product between vectors t and s in R⁸! (denoted by <t.s> = t₁s₁ + t₂s₂ + ... + t₈s₈)

By definition: <t.s> = ||t||.||s||.Cos(x) , where 'x' is the angle between the vectors. Since both t and s have constant magnitude, then the inner product only varies with the angle between the vectors.

Two vectors, however, form a closed triangle in any Euclidean space with the magnitude of the third side of the triangle, ||t - s||, dependent only on the value Cos(x) (this is a direct deduction from the Cosine Rule) when the size of the other two sides are constant as they are in this case.

Therefore, we have arrived at the following implications: sum minimum ---> inner product minimum ---> Cos(x) minimum ---> x maximum (below pi/2) ---> ||t - s|| maximum.

Under the Euclidean norm, the size of the third triangle side is given by:
||t - s||² = (t₁ - s₁)² + (t₂ - s₂)² + ... + (t₈ - s₈)²
= (s₁ - 1)² + (s₂ - 2)² + ... + (s₈ - 8)²

||t - s|| is a maximum when ||t - s||² is a maximum, which in turn is only maximum when each individual squared term is a maximum (this is a property of the squaring function x |-> x²).

Therefore, ||t - s||²_max = (64 - 1)² + (64 - 2)² + ... + (64 - 8)²

But since we may only permute 64 once, and more importantly that:
(64 - 1)² > (64 - 2)² > ... > (64 - 8)²
then it follows that to achieve a maximum for ||t - s|| it is necessary that the largest element of T, 64, must be paired with the smallest element of S, 1.
[note: this property is really there because, once again, of the properties of the squaring function x |-> x² - namely, that it is concave, related to Jensen's Inequality.]

Then by making a similar inductive argument for all other pairings, we get:

||t - s||²_max = (64 - 1)² + (49 - 2)² + ... + (1 - 8)²

---> <t.s>_min = 1(64) + 2(49) + ... + 8(1) = 533

and this gives the minimum sum of the products of the elements of T and S, as required.


In conclusion, summary:

1) Geometrically, finding the minimum sum of the products of the elements of two sets of real numbers of equal size is equivalent to finding the maximum of the expression:
(t₁ - s₁)² + (t₂ - s₂)² + ... + (t_n - s_n)²
under the assumption that the norm we are working under is that of the Euclidean.

2) The maximum of the above expression and minimum of the sum of products is given when the greatest element of one set is pair with the least element of the other.

3) The above result in 2) holds only because of the concave properties of the function f(x) = x² .

4) Geometry is useful .


Hope this helps explain some things to an extent .


P.S. The method involving 1) Calculus is based on the theory of optimization - it is much easier to exercise if one is familiar with some advanced concepts in multivariable calculus (eg. applying the Lagrangian Multiplier); 2) Inequalities essentially revolves around those such as Jensen's Inequality which is similarly beyond HS level mathematics.

 

[Slidey]

I've seen this before.

http://planetmath.org/encyclopedia/RearrangementInequality.html

Variations on the theme are common in maths olympiads, as airie said.