Rearangement

[kamil9876]

Let and be 10 dimensional vectors. The components of are the first 10 prime numbers(and there are no repeated components). The components of are the first 10 squares (again, no components repeat). Find a vector and such that is a maximum.  8-)

[evaporade]

It would be easy if the components are orthogonal.

[/0]

[kamil9876]

correct

[kamil9876]

btw, /0 only provided the answer with no proof. So I still strongly encourage further discussion of this problem

[/0]

LOL I just used the rearrangement inequality on Aopswiki to solve it.

But that's a bit lame I guess, I'll try to prove it


Hmmm let's consider a simpler case of two numbers {a,b}, {c,d}, , .

In fact, let , ,



and



Let's assume that , then





And since are both greater than 1, this is must be true, thus ■




Now consider {a,b,c}, {d,e,f}. , How could we pick combinations to maximimise their products?

If we picked , that cannot be the maximum, because

So something bigger will be . But this cannot be the maximum, since

So something bigger will be . This is the maximum since this inequality can't be applied anymore.

This argument can be extended to sets of any size.




This means that with sets , , with ,   ,

The maximum product is





Hehe soz this isn't really a proof, at least it's more like a 'rationale' for my answer. The mathematicians in the audience will probably be laughing.

[kamil9876]

Yep, last week i was browsing wiki and reading a proof of Chebyshev sum inequality, and they used the rearangement inequality. I had a mini orgasm over the elegance of this theorem, so i made it a challenge for myself to come up with a proof. Funnily enough my proof was inspired by a geometrical picture i had of the situation:




Biggest product is .

Proof:

Consider a product that is not the one shown above. In such a product there is in fact what i call a 'tangle'. This is shown in the attatched diagram. Assume we place all our a's on one number line in the usual ascending order, and same for the b's on a number line below. The supposed biggest product is one where the lines do not intersect, however one that is not that product has a tangle. If we were to get rid of that particular tangle, what would happen? Well basically getting rid of the tangle means getting the end and pulling it to the end while keeping the other end at fixed. Do the same for the other line. Now we have a different product, but what is the change in product?:


let

Hence:




Which is positive as .

Therefore, by untangling we make the product bigger. From here it can be shown that the biggest product is the most untangled and hence what we want to prove.

[/0]

Sorry what are these lines in the middle meant to represent? I got lost on that lol

[kamil9876]

and are connected, meaning that they are being multiplied together in our product.

[/0]

ah very nice