HSC 2014 MX2 Marathon ADVANCED (archive) (1 Viewer)

Chlee1998 · Nov 7, 2014

Re: HSC 2014 4U Marathon - Advanced Level

glittergal96 said:
I'll prove the stronger result that

$a|b\Leftrightarrow 2^a-1| 2^b-1$

for positive integers a and b. Note that if this is true, then any common factor of your two quantities must also be a common factor of two distinct primes, and hence can only be 1.

The $(\Rightarrow)$ part was proven in the last page of this marathon. I'll show the other direction now.

We can write b=aq+r uniquely, with q,r non-negative integers and $0\leq r < a$

If $2^a-1|2^b-1$ , then $2^a-1|((2^b-1)-(2^{aq}-1))$ from the $(\Rightarrow)$ result.

So $2^a-1|2^{aq}(2^r-1)$ .

But since the LHS is odd, it is coprime to any power of 2. So we get

$2^a-1 | 2^r-1.$

As the RHS is strictly less than the LHS, this is only possible if the RHS is 0. Ie r=0, which means that $a|b$ as claimed.

On the last page you never provrd that if a is relatively prime to b then 2^a -1 is relatively prime to 2^b -1. All u did was prove that if a divides b then 2^a-1 divides 2^b-1.

glittergal96 · Nov 7, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Chlee1998 said:
On the last page you never provrd that if a is relatively prime to b then 2^a -1 is relatively prime to 2^b -1. All u did was prove that if a divides b then 2^a-1 divides 2^b-1.

I never said that I did?

In the last page I proved the $(\Rightarrow)$ half of the assertion I made in my first displayed equation in my most recent post.

In the rest of my most recent post, I proved the $(\Leftarrow)$ half, and explained why this result implies that a relatively prime to b implies 2^a-1 relatively prime to 2^b-1.

Chlee1998 · Nov 7, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Sorry I mustve misunderstood then. Wait doesnt the strwjght vertical line refer to coprimality???

Kurosaki · Nov 7, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Chlee1998 said:
Sorry I mustve misunderstood then. Wait doesnt the strwjght vertical line refer to coprimality???

I think $a|b$ means a divides b.

Axio · Nov 7, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Kurosaki said:
I think $a|b$ means a divides b.

It means 'is coprime to'.

glittergal96 · Nov 7, 2014

Re: HSC 2014 4U Marathon - Advanced Level

No, a|b means a divides b, at least everywhere where I have seen it used.

Axio · Nov 7, 2014

Re: HSC 2014 4U Marathon - Advanced Level

glittergal96 said:
No, a|b means a divides b, at least everywhere where I have seen it used.

Ah k. I thought you were meaning the upside-down T symbol: http://en.wikipedia.org/wiki/Coprime_integers

Sy123 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

$\\ $Let$ \ a_k \ $and$ \ b_k \ $be non-negative for$ \ k=1,2,\dots, n \\ \\ $Prove that$ \\\\ (a_1 \cdot a_2 \dots a_n)^{\frac{1}{n}} + (b_1 \cdot b_2 \dots b_n)^{\frac{1}{n}} \leq \left((a_1 + b_1) \cdot (a_2+b_2) \dots (a_n + b_n) \right)^{\frac{1}{n}}$

$\\ $You can assume$ \ \frac{1}{n}\sum_{k=1}^{n} x_k^n \geq x_1x_2\dots x_n$

dan964 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

I'd might raise both sides to the 'n' then probs induction for the resulting statement or original statement
n>0

Sy123 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
I'd might raise both sides to the 'n' then probs induction for the resulting statement or original statement
n>0

I don't think that would work

Besides, there's a much more elegant solution!

glittergal96 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Sy123 said:
$\\ $Let$ \ a_k \ $and$ \ b_k \ $be non-negative for$ \ k=1,2,\dots, n \\ \\ $Prove that$ \\\\ (a_1 \cdot a_2 \dots a_n)^{\frac{1}{n}} + (b_1 \cdot b_2 \dots b_n)^{\frac{1}{n}} \leq \left((a_1 + b_1) \cdot (a_2+b_2) \dots (a_n + b_n) \right)^{\frac{1}{n}}$

$\\ $You can assume$ \ \frac{1}{n}\sum_{k=1}^{n} x_k^n \geq x_1x_2\dots x_n$

Note that multiplying both $a_i$ and $b_i$ by some $r>0$ scales both sides of the equation by $r^{1/n}$ .

Hence we may assume wlog that $a_i+b_i=1$ for each i.

Then by AM-GM

$\left(\prod_i a_i\right)^{1/n}+\left(\prod_i b_i\right)^{1/n}\leq \frac{1}{n}\left(\sum_i a_i + \sum_i (1-a_i)\right)=1=RHS.$

dan964 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

I was thinking of comparing areas under the graph x^1/n (for x>0) using upper/lower rectangles and trapeziums after applied the AM-GM assumption to the LHS.

dan964 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

glittergal96 said:
Note that multiplying both $a_i$ and $b_i$ by some $r>0$ scales both sides of the equation by $r^{1/n}$ .

Hence we may assume wlog that $a_i+b_i=1$ for each i.

Are you multiplying each term, or just a single term?
If the former... $(ra_1ra_2ra_3ra_4...ra_n)^1/n = (r^n)^1/n)*(a_1a_2a_3a_4...a_n)^1/n$
(same with b)
which scales the LHS by r??

dan964 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
Are you multiplying each term, or just a single term?
If the former... $(ra_1ra_2ra_3ra_4...ra_n)^1/n = (r^n)^1/n)*(a_1a_2a_3a_4...a_n)^1/n$
(same with b)
which scales the LHS by r??

never mind it is the latter.
what is "wlog" in the second line...

Kurosaki · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
never mind it is the latter.
what is "wlog" in the second line...

Without loss of generality.

dan964 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Kurosaki said:
Without loss of generality.

when and where you use?

glittergal96 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
when and where you use?

The meaning is literal.

We can assume (blah) and a proof of the claim under the assumption of (blah) implies that the claim is true even without the (blah) assumption.

In other words (blah) was just assumed to make the proof more concise.

Sy123 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

glittergal96 said:
Note that multiplying both $a_i$ and $b_i$ by some $r>0$ scales both sides of the equation by $r^{1/n}$ .

Hence we may assume wlog that $a_i+b_i=1$ for each i.

Then by AM-GM

$\left(\prod_i a_i\right)^{1/n}+\left(\prod_i b_i\right)^{1/n}\leq \frac{1}{n}\left(\sum_i a_i + \sum_i (1-a_i)\right)=1=RHS.$

Nice proof!

Here is mine:

$\\ \frac{(a_1 a_2 \dots a_n)^{1/n} + (b_1 b_2 \dots b_n)^{1/n}}{((a_1+b_1)\dots(a_n + b_n))^{1/n}} \\ \\ = \left(\frac{a_1}{a_1+b_1} \dots \frac{a_n}{a_n+b_n} \right)^{1/n} + \left( \left(1 - \frac{a_1}{a_1+b_1} \right) \left(1 - \frac{a_2}{a_2 + b_2} \right) \dots \left(1-\frac{a_n}{a_n + b_n} \right) \right)^{1/n}$

$x_k = \frac{a_k}{a_k + b_k}$

$\\ \Rightarrow (x_1 x_2 \dots x_n)^{1/n} + ((1-x_1)(1-x_2)\dots (1-x_n))^{1/n} \\ \\ \leq \frac{1}{n} \sum x_k + \frac{1}{n} \sum (1-x_k) = 1 \\ \\ \square$

FrankXie · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Try this one:
Given that $a>0, b>0$ and $a^3+b^3=2$. Without using calculus prove that $a+b\leq2$.

Chlee1998 · Nov 10, 2014

Re: HSC 2014 4U Marathon - Advanced Level

FrankXie said:
Try this one:
Given that $a>0, b>0$ and $a^3+b^3=2$. Without using calculus prove that $a+b\leq2$.

These problems belong in another thread, which is just called the 4u marathon. anyways, a^3 + b^3 can be factoed to (a+b)(a^2-ab + b^2) =2

But from AM GM, a^2 + b^2 > 2ab > ab (for a,b>0). Hence the second factor is positive.
Thus (a+b) multiplied by a positive number equals to 2, meaning that a+b is less than 2.

HSC 2014 MX2 Marathon ADVANCED (archive) (1 Viewer)

Member

Active Member

Member

True Fail Kid

=o

Active Member

=o

This too shall pass

what

This too shall pass

Active Member

what

what

what

True Fail Kid

what

Active Member

This too shall pass

Active Member

Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)