ATAR Notes: Forum

VCE Stuff => VCE Mathematics/Science/Technology => VCE Subjects + Help => VCE Mathematics => Topic started by: kamil9876 on May 29, 2009, 07:38:52 pm

Title: Rearangement
Post by: kamil9876 on May 29, 2009, 07:38:52 pm: Let $a$ and $b$ be 10 dimensional vectors. The components of $a$ are the first 10 prime numbers(and there are no repeated components). The components of $b$ are the first 10 squares (again, no components repeat). Find a vector $a$ and $b$ such that $a.b$ is a maximum. 8-)
Title: Re: Rearangement
Post by: evaporade on May 30, 2009, 08:54:16 pm: It would be easy if the components are orthogonal.
Title: Re: Rearangement
Post by: /0 on May 31, 2009, 06:35:29 pm: $\mathbf{a} = 2\mathbf{e_1}+3\mathbf{e_2}+5\mathbf{e_3}+7\mathbf{e_4}+11\mathbf{e_5}+13\mathbf{e_6}+17\mathbf{e_7}+19\mathbf{e_8}+23\mathbf{e_9}+29\mathbf{e_{10}}$

$\mathbf{b}= 1\mathbf{e_1}+4\mathbf{e_2}+9\mathbf{e_3}+16\mathbf{e_4}+25\mathbf{e_5}+36\mathbf{e_6}+49\mathbf{e_7}+64\mathbf{e_8}+81\mathbf{e_9}+100\mathbf{e_{10}}$
Title: Re: Rearangement
Post by: kamil9876 on May 31, 2009, 08:01:07 pm: correct
Title: Re: Rearangement
Post by: kamil9876 on June 01, 2009, 12:23:54 pm: btw, /0 only provided the answer with no proof. So I still strongly encourage further discussion of this problem :)
Title: Re: Rearangement
Post by: /0 on June 01, 2009, 02:55:18 pm: 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}, $a \leq b$ , $c\leq d$ .

In fact, let $b = ma$ , $d = nc$ , $m,n \geq 1$

$\Rightarrow ac + bd = ac + (ma )( nc)=ac(1+mn)$

and

$ad + b c = a(nc) + (ma)c = ac(m+n)$

Let's assume that $ac+bd \geq ad + bc$ , then $1+mn\geq m+n$

$\Rightarrow mn-m-n+1 \geq 0$

$\Rightarrow (m-1)(n-1) \geq 0$

And since $m, n$ are both greater than 1, this is must be true, thus $ac+bd \geq ad + bc$ ■

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

If we picked $ae+bf+cd$ , that cannot be the maximum, because $bd + cf \geq bf + cd$

So something bigger will be $ae+bd+cf$ . But this cannot be the maximum, since $ad+be \geq ae+bd$

So something bigger will be $ad+be+cf$ . 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 $\{a_1,a_2,a_3,...,a_n\}$ , $\{b_1,b_2,b_3,...,b_n\}$ , with $a_1 \leq a_2 \leq... \leq a_n$ , $b_1 \leq b_2 \leq ... \leq b_n$ ,

The maximum product is $a_1b_1+a_2b_2+...a_nb_n$

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.
Title: Re: Rearangement
Post by: kamil9876 on June 01, 2009, 06:39:19 pm: 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:

$a_1<a_2<...<a_n$
$b_1<b_2<...<b_n$

Biggest product is $a_1b_1+...a_nb_n$ .

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 $a_i$ end and pulling it to the $a_j$ end while keeping the other end at $b_k$ fixed. Do the same for the other line. Now we have a different product, but what is the change in product?:

$\Delta=b_m(a_i-a_j)+b_k(a_j-a_i)$
let $\Delta_a=a_i-a_j>0$

Hence:

$\Delta=b_m\Delta_a-b_k\Delta_a$
$=\Delta_a(b_m-b_k)$

Which is positive as $b_m-b_k>0$ .

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.
Title: Re: Rearangement
Post by: /0 on June 01, 2009, 06:59:35 pm: Sorry what are these lines in the middle meant to represent? I got lost on that lol
Title: Re: Rearangement
Post by: kamil9876 on June 01, 2009, 07:19:35 pm: $a_i$ and $b_k$ are connected, meaning that they are being multiplied together in our product.
Title: Re: Rearangement
Post by: /0 on June 01, 2009, 07:22:19 pm: ah very nice :D