The Proof is Trivial!

Scroll to see replies

Nope, I meant

x^{3}y

. From AM-GM we have

\displaystyle \sum_{cyc} x^{4} \ge \sum_{cyc} x^{2}y^{2}

and

\displaystyle \sum_{cyc} (x^{4}+x^{2}y^{2}) \ge 2\sum_{cyc} x^{3}y

, the second is also trivially true, and hence

\displaystyle \sum_{cyc} x^{4} \ge \sum_{cyc} x^{3}y

. It is a consequence of AM-GM, yet not a direct result.

Oh I see, I assumed you meant it was a direct result!

Problem 76 is wrong in this form (I thought

c \le a+b

).

Edit: We have to bound

c

; I can try to find the best possible

c

Arghhh I'm so sorry! It was a typo :s-smilie:

I have corrected it now! (the first term is (a+b+c) !!!! :s-smilie:

Reply 581

Mladenov

Solution 76

We have

(a+b+c)(a+b-c)(a+c-b)(b+c-a)=((a+b)^{2}-c^{2})(c^{2}-(a-b)^{2})

.
If

c^{2}\ge (a+b)^{2}

the inequality is clearly true.
If

(a-b)^{2} < c^{2} < (a+b)^{2}

, AM-GM yields

\displaystyle ((a+b)^{2}-c^{2})(c^{2}-(a-b)^{2}) \le \frac{(4ab)^{2}}{2^{2}}\le (a^{2}+b^{2})^{2}

.
If

c^{2}\le (a-b)^{2}

the inequality is again trivially true.

(edited 10 years ago)

Reply 582

Jkn

Original post by Mladenov

Solution 76

We have

(a+b+c)(a+b-c)(a+c-b)(b+c-a)=((a+b)^{2}-c^{2})(c^{2}-(a-b)^{2})

.
If

c^{2}\ge (a+b)^{2}

the inequality is clearly true.
If

(a-b)^{2} < c^{2} < (a+b)^{2}

, AM-GM yields

\displaystyle ((a+b)^{2}-c^{2})(c^{2}-(a-b)^{2}) \le \frac{(4ab)^{2}}{2^{2}}\le (a^{2}+b^{2})^{2}

.
If

c^{2}\le (a-b)^{2}

the inequality is again trivially true.

Nicely done. I attempted to see if there was a way without using AM-GM etc.. Simplify and shift all terms to one side of the equation and form a quadratic in

a^2+b^2

. The roots turn out to be

(a^2+b^2)=c^2 +/- \sqrt{-(a^2-b^2)^2}

which I concluded implied there were no real roots (is this correct?) and hence demonstrated that there exists a single a positive value of the expression.

Reply 583

Jkn

Original post by Mladenov

Problem 80

Let

(a_{n})_{n\ge1}

be an increasing sequence of positive integers. Suppose also that

\displaystyle \lim_{n\to \infty} \frac{a_{n}}{n}=0

. Then, the sequence

\displaystyle b_{n} = \frac{n}{a_{n}}

contains all positive integers.

a_{n}

is an increasing sequence of positive integers, then surely it must be true that

a_{n} \geq n

(as the smallest such sequence is 1, 2, 3, ...) and hence

\displaystyle \lim_{n\to \infty} \frac{a_{n}}{n}=0

cannot hold in such a case. Have I missed something crucial?

Reply 584

Mladenov

Original post by Jkn

...

Your idea would probably work, but if

a=b

c^{2} \pm \sqrt{-(a-b)^{2}}

is a real number, provided that

c

is real.

Original post by Jkn

...

My dear friend, why do you think that

(a_{n})_{n\ge 1}

is a strictly increasing sequence? I have never uttered this.

Reply 585

Jkn

Original post by Mladenov

Your idea would probably work, but if

a=b

c^{2} \pm \sqrt{-(a-b)^{2}}

is a real number, provided that

c

is real.

(still nice to do things without standard inequality techniques) :smile:

Solution 76 (2)

RHS=

(a+b+c)(a+b-c)(a+c-b)(b+c-a)=((a+b)^{2}-c^{2})(c^{2}-(a-b)^{2})

=c^2((a+b)^2+(a-b)^2)-(a^2-b^2)^2-c^4

Let f(a,b,c)=LHS-RHS=

(a^2+b^2)^2-2c^2(a^2+b^2)+(c^4+(a^2-b^2)^2)

f(a,b,c) had roots when

a^2+b^2=2c^{2} \pm \sqrt{-(a-b)^{2}}

If a doesn't equal b the equation has no real roots and so a trivial numerical example shows that there exists a,b,c such that f(a,b,c) is positive and hence must be positive for all values (i.e. f(1,0,0)=2).

In the case a=b,

f(a,b,c)=(2a^2)^2+(c^2)^2-4a^2c^2=(2a^2-c^2)^2 \geq 0

Hence true for all a,b,c.

My dear friend, why do you think that

(a_{n})_{n\ge 1}

is a strictly increasing sequence? I have never uttered this.

Right okay, it just seemed odd that 1,1,1 or 1,2,2 constitutes 'increasing' ;O

Btw, how old are you and (if you're not at uni already) which one are you going to? :smile:

(edited 10 years ago)

Reply 586

Mladenov

Original post by Jkn

...

Yup, your solution is now fine. :tongue:

Edit: After I have scrutinized your solution, I would suggest you write

c^{2}=d

and consider the expression as a polynomial of degree

2

with respect to

d

. In this way, you will be able to elude from coefficients, which depend on the "variable".

Original post by Jkn

Right okay, it just seemed odd that 1,1,1 or 1,2,2 constitutes 'increasing' ;O

If it was strictly increasing, the problem would be incorrect, as you found out.

Original post by Jkn

Btw, how old are you and (if you're not at uni already) which one are you going to? :smile:

Spoiler

(edited 10 years ago)

Reply 587

Jkn

Original post by Mladenov

Yup, your solution is now fine. :tongue:

Edit: After I have scrutinized your solution, I would suggest you to write

c^{2}=d

and consider the expression as a polynomial of degree

2

with respect to

d

. In this way, you will be able to elude from coefficients, which depend on the "variable".

Hmm I suppose that would be neater but I've given it some thought and I do believe the expression is valid (correct me if I'm wrong) because the quad. formula is being used merely as a rearrangement in this case. I suppose for clarification you could use the fact that the assumption that f(a,b,c)=0 leads to a contradiction (a not equaling b) and combining it with the fact that with the property that it is continuous.

Spoiler

Oh right, don't you have to be 18 or under to participate in the IMO? I always really enjoyed 'competition'-style maths though, but didn't qualify for BMO2 this year (our equivalent 'last 40'-ish exam) which is annoying because, since I've learn AM-GM type stuff and loads of algebraic tricks I can now do loads of the BMO2 questions!

I take it you are you not going to university this year then if you're still unsure (is it typical to start uni past 18/19 in your country?) I'm certain you'd get into Cambridge btw if that's where you wanted to go. Apply to Emmanuel (always 1st or 2nd in the tompkins table), that's where my offer is ;D

Reply 588

Mladenov

Original post by Jkn

Yup, the expression is valid in this case; I do not want to be punctual, I just said what I would do with your idea. :tongue:

Original post by Jkn

"The contestants must have been born less than twenty years before the day of the second contest paper".
I have done many problems from BMO2, FST(First Selection Test), and NST(Next Selection Test). In my view, BMO2 is not too difficult; the letter tests are challenging though.
For mathematical olympiads the theory is a must, but, I believe, problem solving is of much more import - it teaches you many interesting tricks, which are crucial.

Original post by Jkn

I take it you are you not going to university this year then if you're still unsure (is it typical to start uni past 18/19 in your country?) I'm certain you'd get into Cambridge btw if that's where you wanted to go. Apply to Emmanuel (always 1st or 2nd in the tompkins table), that's where my offer is ;D

Yes, we typically finish high school at the age of 19. I consider University of Cambridge, and Lycée Louis le Grand

\Rightarrow

ENS (french is simply killing me :biggrin:

).
By the way, congratulations on your offer!

(edited 10 years ago)

Reply 589

bananarama2

Original post by Jkn

...

You got into Emma :O :biggrin:

So did I for a different subject :biggrin:

Reply 590

Jkn

Original post by Mladenov

Yup, the expression is valid in this case; I do not want to be punctual, I just said what I would do with your idea. :tongue:

Oh okay. That's what I've actually started to love about maths. Ever since I've broken free from curriculum maths and explored pure maths a bit more, I've found that there are so many different ways to do problems that it becomes extremely creative and people tend to have almost a 'mathematical personality' that's expressed in their solutions. Sort of like an art form :smile:

Hmm, perhaps thats why britain does so poorly (I assume you are not allowed to have attended a university).
Wow, very impressive! How about IMO and other international competitions?

I've found that you need to have been exposed to that level of problem-solving before you can start scratching the surface with it. Unfortunately this means that vast majority of people that qualify for BMO2 and hence the national team come in clumps from the elite private schools :/ My teachers don't know anyones thats ever even done BMO1 and I didn't either until I visited Cambridge and Warwick! Luckily though I've been finding STEP questions increasingly easy :smile:

Yes, we typically finish high school at the age of 19. I consider University of Cambridge, and Lycée Louis le Grand

\Rightarrow

ENS (french is simply killing me :biggrin:

).
By the way, congratulations on your offer!

Choose cambridge! For one thing look at the league table difference! And then consider Ramanujan, Newton, Hawking, Hardy, 5 Fields Medelists! :biggrin:

Cheers!

Original post by bananarama2

You got into Emma :O :biggrin:

So did I for a different subject :biggrin:

Oh awesome! I'm gonna go ahead at assume NatSci physics? :biggrin:

(being on a maths thread and all!) Unfortunately for maths students the concept of 'getting in' is non-existent until august :smile:

(edited 10 years ago)

Reply 591

Lord of the Flies

Solution 80

Let the statement

a_n n^{-1}\to 0

(\star)

(\star)\Rightarrow

there must be an integer

m

for which

a_m=m

and

a_{n>m}<n

. Suppose that for some

k

there exists

i\geq m

such that

a_i i^{-1}=k^{-1}

. If we are lucky and

a_i=a_{i+a_i}

then we have

a_{i} (i+a_i)^{-1}=(k+1)^{-1}

and we are done. On the other hand, if

a_i

increases, bearing

a_i<i

and

(\star)

in mind there will be

j>i

such that

a_j j^{-1}=k^{-1}

, which brings us back to our hypothesis. However, by

(\star)

this can only occur finitely many times for any fixed

k

, and hence

a_n

will always contain a constant string which leads to our lucky case. Thus the induction is complete and the sequence

n^{-1}

is a subsequence of

a_n n^{-1}

.

The use of the limit can perhaps be made clearer by noting that

(a_n)

must contain arbitrarily long strings of repeated integers. This is easily shown:

Spoiler

Original post by Jkn

Choose Cambridge! For one thing look at the league table difference! And then consider Ramanujan, Newton, Hawking, Hardy, 5 Fields Medelists! :biggrin:

Hey hey, for maths the ENS is the most prestigious institution in France. Galois, Dieudonné, Weil, Hadamard, Lebesgue, and if my memory is correct, 10 Fields Medalists.

Original post by Mladenov

I consider University of Cambridge, and Lycée Louis le Grand

\Rightarrow

ENS (french is simply killing me :biggrin:

Brilliant plan, either way - I have a couple friends at LLG and they are enjoying it a lot. Be prepared for a lot of non-mathematical things if you do an MP*.

(edited 10 years ago)

Reply 592

bananarama2

Original post by Jkn

Oh awesome! I'm gonna go ahead at assume NatSci physics? :biggrin:

(being on a maths thread and all!) Unfortunately for maths students the concept of 'getting in' is non-existent until august :smile:

Sort of, yeh :tongue:

Well I still have to me my offer it's just considerably easier than yours. From your posts on here I have every confidence in you though :biggrin:

Reply 593

Felix Felicis

Solution 28

Original post by Indeterminate

...

Saw this question still lying around and thought I'd give it a shot :ninja:

Is the solution for this meant to be neat by the way Indeterminate? xD Whatever route I go down, I get some nasty algebraic mess xD

28 Solution

(edited 10 years ago)

Reply 594

Jkn

Original post by Lord of the Flies

Hey hey, for maths the ENS is the most prestigious institution in France. Galois, Dieudonné, Weil, Hadamard, Lebesgue, and if my memory is correct, 10 Fields Medalists.

Oh I didn't know that :O
Your insurance?

Original post by bananarama2

Sort of, yeh :tongue:

Well I still have to me my offer it's just considerably easier than yours. From your posts on here I have every confidence in you though :biggrin:

Awesome, what made you choose emmanuel specifically? Oh thanks :smile:

Same goes for you! I know few science students interested in pure maths (though I myself have a great interest in theoretical physics)

Original post by Mladenov

...

Few more you may be interested in:

Solution 76 (3) (absolutely no idea how I only just noticed this! *facepalm*)

LHS-RHS=

(a^2+b^2-c^2)^2+(a^2-b^2)^2 \geq 0

Solution 76 (4)

Comparing with Heron's formula,

4A = \sqrt{RHS}

, where A is the area of a triangle of sides a, b and c. So RTP:

a^2+b^2 \geq 4A

Maximum area of a triangle occurs when

\frac{dA}{dQ}=0

where Q is an arbitrarily chosen angle between, in this case, and a and b. So

\frac{d}{dQ} \frac{1}{2} ab \sin{Q} = \frac{1}{2} ab cos{Q} = 0

. This implies

Q= \frac{\pi}{2}

and so

4A=2ab

.

Therefore, as

(a-b)^2 \geq 0

, the inequality holds. Note that the result is not bounded for values that satisfy the triangle inequality because the construction is hypothetical and has only relied on unbounded results. Also note that the value of Q is not bounded by

0 \leq Q \leq \pi

as any such value would give the same value for sin(0) (though the inequality is trivial for c>a+b etc..)

QED.

(any more solutions?)

------------------------------------------------

Problem 81

Find the smallest positive integer

n

such that

n

can be uniquely expressed as the sum of two distinct cubes in two distinct ways. Justify your answer.

(edited 10 years ago)

Reply 595

Jkn

Original post by Mladenov

Problem 80

Let

(a_{n})_{n\ge1}

be an increasing sequence of positive integers. Suppose also that

\displaystyle \lim_{n\to \infty} \frac{a_{n}}{n}=0

. Then, the sequence

\displaystyle b_{n} = \frac{n}{a_{n}}

contains all positive integers.

I'll take a crack at it!

Solution 80

Considering the difference between successive terms we get...

\frac{n+1}{a_{n+1}} - \frac{n}{a_n} \leq \frac{1}{p}

, for some positive integer p, which rearranges to

a_{n}(a_{n+1}-p) \geq pn(a_{n}-a_{n+1} \leq 0

which holds for

a_{n+1} \geq p

(as the right hand side is less than or equal to zero by virtue of being an increasing sequence).

This implies each successive term on

b_{n}

can differ by, at most, successive terms of the harmonic series (though not equal for

a_{n+1}>1

). We also know that the series is divergent (as is the harmonic series).

Assume there exists an integer r such that

b_{n} \not= r

for all n. As successive terms cannot differ by more than an integer, this would require such a value of r to be 'passed by' as the sequence increases (if the sequence were to decrease it would have to increase again afterwards and so the same argument would apply then) which would require that

gcd(a_{n},n) =1

for successive values of

b_{n}

as it moves past the integer 'r' which is trivially untrue as the difference between each term is always an integer. As the sequence increases to infinity, no such r can exist and thus we have a contradiction.

Therefore

b_{n}

must contain all positive integers.

Edit: crap just saw LOTF's solution

(edited 10 years ago)

Reply 596

Lord of the Flies

Original post by Jkn

Oh I didn't know that - your insurance?

I would need to do a prépa first (the most famous being LLG, which Mladenov mentioned). I am not interested in doing this for several reasons. I will definitely apply later on though (the undergrad degree will replace the prépa)

Reply 597

Jkn

Original post by Lord of the Flies

WTAF that looks weird! So what level are the universities you go to after the prépa, like masters degrees? Are they more prestigious and exclusive than onbridge/ivy-league? Soo confused!

Reply 598

Zephyr1011

Solution 80

Assume that there is some positive integer x such that

x\neq b_n\;\forall n

.

Assume that

a_{xy}>y-1

for some positive integer y. Then, as

a_{xy}

is a positive integer, and if

a_{xy}=y,\; b_{xy}=x

, therefore,

a_{xy}\neq y

, and so

a_{xy}>y

. Therefore, as a is an increasing sequence,

a_{x(y+1)}>(y+1)-1

. Therefore, if

a_{xy}>y-1,\; a_{x(y+1)}>(y+1)-1

To check the base cases:

If

a_x=1,\; b_x=x

, Therefore

a_x\neq1

, and as

a_n\in\mathbb{N}

and

a_n>0\;\forall n,\; a_n>1\;\forall n\geq x

. Therefore

a_{2x}>2-1

.

Therefore, by induction,

a_{xy}>y-1,\; \forall y

. If

a_{xy}=y

, then

b_{xy}=x

, therefore

a_{xy}\neq y

and so

a_{xy}>y, \; y\in\mathbb{N}

Let

c_n

be a new sequence, where

c_{xy}=y+1\; \forall y\in\mathbb{N}

and

c_{xy+z}=c_{xy}\; \forall z<x

and

\geq 0

. Clearly

a_n\geq c_n \forall n

\lim_{n\to \infty} c_n=\frac{n}{x}+1

. Therefore,

\lim_{n\to \infty} \dfrac{c_n}{n}=\dfrac{\frac{n}{x}+1}{n}=\dfrac{1}{x}

. As

a_n\geq c_n,\;\lim_{n\to\infty}a_n\geq \lim_{n\to\infty}c_n

. Therefore

\lim_{n\to\infty}a_n\geq \frac{1}{x}

and so

\lim_{n\to\infty}a_n\neq 0

. There is a contradiction. Therefore there is no integer x which is not contained in b. Therefore b contains all positive integers.

Edit:Oh, while I was typing this several other people beat me to it.

(edited 10 years ago)

Reply 599

Mladenov

Original post by Jkn

Hmm, perhaps thats why britain does so poorly (I assume you are not allowed to have attended a university).
Wow, very impressive! How about IMO and other international competitions?

No, you are not allowed to attend university. I have done all IMO SL problems from 1990 to 2010 (with several exceptions of course - see, for instance, SL 2003, A6). I am planning to do SL 2011 as a mock before our TST. The Iranian TST is very challenging, I would say it is more difficult than the Chinese TST. Another good source of problems is the All-Russian MO (especially combinatorics and geometry). For inequalities - Vietnamese TST; number theory - almost everywhere(I am biased here). The French TST is somewhat tough. Our NMO and TST are also not easy. I can post some problems if you want. But just look at, for example, the Italian TST, or the German TST - these are warm-ups. I will not even mention Spain, Portugal, and the rest. In Europe, broadly speaking, olympiad mathematics is abandoned.

Original post by Jkn

I've found that you need to have been exposed to that level of problem-solving before you can start scratching the surface with it. Unfortunately this means that vast majority of people that qualify for BMO2 and hence the national team come in clumps from the elite private schools :/ My teachers don't know anyones thats ever even done BMO1 and I didn't either until I visited Cambridge and Warwick! Luckily though I've been finding STEP questions increasingly easy :smile:

In my country there are high schools which emphasize on olympiad mathematics and this makes the difference. The students at these schools study, generally speaking, mathematics and languages.
The best students sometimes work with professors.

Original post by Lord of the Flies

Solution 80

Let the statement

a_n n^{-1}\to 0

(\star)

(\star)\Rightarrow

there must be an integer

m

for which

a_m=m

and

a_{n>m}<n

. Suppose that for some

k

there exists

i\geq m

such that

a_i i^{-1}=k^{-1}

. If we are lucky and

a_i=a_{i+a_i}

then we have

a_{i} (i+a_i)^{-1}=(k+1)^{-1}

and we are done. On the other hand, if

a_i

increases, bearing

a_i<i

and

(\star)

in mind there will be

j>i

such that

a_j j^{-1}=k^{-1}

, which brings us back to our hypothesis. However, by

(\star)

this can only occur finitely many times for any fixed

k

, and hence

a_n

will always contain a constant string which leads to our lucky case. Thus the induction is complete and the sequence

n^{-1}

is a subsequence of

a_n n^{-1}

.

The use of the limit can perhaps be made clearer by noting that

(a_n)

must contain arbitrarily long strings of repeated integers. This is easily shown:

Spoiler

My compliments, very elegant method. :tongue:

This fact is quite interesting, and I found it very useful - I know several olympiad problems which are trivial if one knows this.
I shall post my solution, since it uses one rather beneficial technique, when it comes to sequences.

Spoiler

Original post by Jkn

I'll take a crack at it!

Solution 80

Assume there exists an integer r such that

b_{n} \not= r

gcd(a_{n},n) =1

for successive values of

b_{n}

I cannot understand your argument. Could you please explain?
Your approach makes me think of the density of sequences of integers.

Original post by Jkn

Solution 76 (3) (absolutely no idea how I only just noticed this! *facepalm*)

LHS-RHS=

(a^2+b^2-c^2)^2+(a^2-b^2)^2 \geq 0

Excellent. I would have never even thought that this might be the case.
Regarding the geometric interpretation - I also suspected something, but AM-GM seemed more reliable. :biggrin:

Original post by Lord of the Flies

Brilliant plan, either way - I have a couple friends at LLG and they are enjoying it a lot. Be prepared for a lot of non-mathematical things if you do an MP*.

I would choose MPSI and then MP*(I think, if I am good enough, they will select me to do MP* after the first year. Is this so?). By the way, as far as I know, there is no programme which offers more mathematics, is there? Notwithstanding, it seems quite exciting that general topology is taught in the first year; the course in linear algebra goes quite deeply - polylinear algebra in the end of the first year. :tongue:

To qualify for LLG, I ought to finish first or second on the examination, which takes place each year in May. There are roughly 50 students from my country who take the exam.
Here are the problems from 2010. The examination is 4 hours.

Spoiler