The Student Room Group

The Proof is Trivial!

Scroll to see replies

Original post by Jkn

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)


I don't know really. It didn't feel too imposing and the people were really friendly when I went to look. The ducks were a big attraction too :tongue:. I have to say I'm not interested in the REALLY pure stuff which crops up here, but I do like a good maths puzzle.
Reply 601
Original post by Mladenov
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.

Is the "IMO SL" the IMO? ;0 Haven't been able to find any TSTs (except the UK's) but they seem pretty beyond me, for now anyway, I think I'd be lucky to find one I could do amongst 5 papers! None the less it would be nice to see some of the reopen TSTs if they're a little easier (perhaps you could quote the sources) so post away! Also a few BMO1/BMO2-level questions would be appreciated :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.

Hmm that sounds interesting, is that what you do? Do you have to pay? In my country we have schools like that that cost tens of thousands of pounds (or more!) per year to attend (though they are non-specialist) but in a few years they are introducing maths academies, similar to what you have now perhaps, that train students in problem solving and train students for STEP in the same way students are coached towards A-Levels.

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

When I said when the sequence could decrease I was aiming to account for the cases where an+1an>1 a_{n+1}-a_{n} >1 (and aimed to note that tho was irrelevant).
(Reading through this part does seem horribly sloppy!) By successive terms equaling integers I meant that the difference between n and an a_n was always as integer. I lack the tools to explain what I mean rigorously but I thought the general idea seemed fairly intuitive:

Consider the values of the sequence where bn b_{n} supposedly "passes by" an integer r. As the sequence can only ever increase by fractions (bounded by an upper-bound that is inversely proportional to an a_{n} as n approaches infinity - and also fractions) this would require successive terms of bnb_{n} to equal two rational numbers above and below which would, in turn, imply that gcd(an,n)<an gcd(a_{n},n)<a_{n} (not co-prime, my bad!) for successive terms of n as n moves past r. This is a contradiction as, to "pass by" the integer would clearly require divisibility for one of the adjacent terms (i.e. r).

I'll attempt to formalise the last bit: clearly an=an+1a_{n}=a_{n+1} as it "passes by" the value of r. So let an=an+1=x a_{n}=a_{n+1}=x. This implies nx<r<n+1x \frac{n}{x} <r <\frac{n+1}{x} which implies rx rx is not an integer (as its between n and n+1) therefore the inequality is not strict and r does infact equal either of the two (i.e. is in bn b_{n}). This is contrary to our assumption. Therefore no such r exists. QE"mother-****ing"D.

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:

It was staring us in the face the whole time! :biggrin: AM-GM is overkill in so many situations! Plus you don't tend to learn anything new about the equation. I see it as a subsidiary 'implicit' method, just like induction (though, of course, these methods are highly useful if all you need to do is 'prove' or 'solve'), wouldn't you agree? :smile:
(edited 10 years ago)
Reply 602
Original post by bananarama2
I don't know really. It didn't feel too imposing and the people were really friendly when I went to look. The ducks were a big attraction too :tongue:. I have to say I'm not interested in the REALLY pure stuff which crops up here, but I do like a good maths puzzle.

Mm I couldn't agree more. I went to Trinity on my open day and, although it was nice to see the setting to a lot of books I read, I realised it wasn't for me (packed with tourists, too big, admissions process too biased towards private schools, etc, etc...) Emmanuel on the other hand :biggrin: Even so, it's nice to have physicists with a general interest in mathematics itself.

It's literally such a small world isn't it! Are you considering the masters in E&T.Phys? :smile:
Reply 603
Problem 82**

We have not done any combinatorics.

Let nZ+n\in \mathbb{Z^{+}} and AZA \subset Z are such that:
i) each element aAa \in A can be represented as a=b+ca=b+c, where b,cAb,c \in A;
ii) if a1,a2,..,akAa_{1},a_{2},..,a_{k} \in A and knk \le n, then 0ikai0\displaystyle \sum_{0 \le i \le k} a_{i} \not= 0.
Then, we have card(A)2n+2card (A) \ge 2n+2.


Problem 83**

Let xx, aa, and bb be positive integers such that xa+b=abbx^{a+b}=a^{b}b. Then a=xa=x and b=xxb=x^{x}.
Original post by Jkn
Mm I couldn't agree more. I went to Trinity on my open day and, although it was nice to see the setting to a lot of books I read, I realised it wasn't for me (packed with tourists, too big, admissions process too biased towards private schools, etc, etc...) Emmanuel on the other hand :biggrin: Even so, it's nice to have physicists with a general interest in mathematics itself.

It's literally such a small world isn't it! Are you considering the masters in E&T.Phys? :smile:


Even at interview Emma seemed inviting and friendly. Well Physics is written in maths :biggrin:

I actually applied to do Chemical Engineering in my second year, but I have a choice and I can't choose between Physics and Chem Eng.
Reply 605
Original post by bananarama2
Even at interview Emma seemed inviting and friendly. Well Physics is written in maths :biggrin:

I actually applied to do Chemical Engineering in my second year, but I have a choice and I can't choose between Physics and Chem Eng.

Talking to other people I met at the STEP residential I went on over easter, the general consensus was that ours was fairly brutal! I think everyone came out shaking :L Whilst I was there though our DOS came to see us though (which I don't think he was supposed to!) and somehow he remembered me :biggrin:

Tell that to my physics teacher, he having none of it! I don't think he understands tautologies either :frown: The other day we were were doing radioactivity equations for medicine and he said something ridiculous like the fundamental things that are conserved are "Energy-mass and baryon number" and I was like "well what's baryon number then it's a concept independent of both energy and mass?" and he took a big sigh and was like "*facepalm* baryon number is a third" ?!?!?! :L

I was actually planning to apply for physics until halfway through last year!
Original post by Jkn
Talking to other people I met at the STEP residential I went on over easter, the general consensus was that ours was fairly brutal! I think everyone came out shaking :L Whilst I was there though our DOS came to see us though (which I don't think he was supposed to!) and somehow he remembered me :biggrin:

Tell that to my physics teacher, he having none of it! I don't think he understands tautologies either :frown: The other day we were were doing radioactivity equations for medicine and he said something ridiculous like the fundamental things that are conserved are "Energy-mass and baryon number" and I was like "well what's baryon number then it's a concept independent of both energy and mass?" and he took a big sigh and was like "*facepalm* baryon number is a third" ?!?!?! :L

I was actually planning to apply for physics until halfway through last year!


My maths interview was alright, although I blanked and I blanked on a chemistry question in my science interview too. I'd met my interviewer at the open day but I don't think he remembered me. Teachers do have a habit of saying what they just said in a slightly different way when you want more detailed information.

Why did you change your mind?
Reply 607
Original post by Jkn
Is the "IMO SL" the IMO? ;0 Haven't been able to find any TSTs (except the UK's) but they seem pretty beyond me, for now anyway, I think I'd be lucky to find one I could do amongst 5 papers! None the less it would be nice to see some of the reopen TSTs if they're a little easier (perhaps you could quote the sources) so post away! Also a few BMO1/BMO2-level questions would be appreciated :smile:

SL=Shortlist

Spoiler



Original post by Jkn
Hmm that sounds interesting, is that what you do? Do you have to pay? In my country we have schools like that that cost tens of thousands of pounds (or more!) per year to attend (though they are non-specialist) but in a few years they are introducing maths academies, similar to what you have now perhaps, that train students in problem solving and train students for STEP in the same way students are coached towards A-Levels.

Yes, it is what I do. Nope, we do not have to pay:tongue:(these schools are public, as almost everything here:biggrin:).


Original post by Jkn
When I said when the sequence could decrease I was aiming to account for the cases where an+1an>1 a_{n+1}-a_{n} >1 (and aimed to note that tho was irrelevant).
(Reading through this part does seem horribly sloppy!) By successive terms equaling integers I meant that the difference between n and an a_n was always as integer. I lack the tools to explain what I mean rigorously but I thought the general idea seemed fairly intuitive:

Consider the values of the sequence where bn b_{n} supposedly "passes by" an integer r. As the sequence can only ever increase by fractions (bounded by an upper-bound that is inversely proportional to an a_{n} as n approaches infinity - and also fractions) this would require successive terms of bnb_{n} to equal two rational numbers above and below which would, in turn, imply that gcd(an,n)<an gcd(a_{n},n)<a_{n} (not co-prime, my bad!) for successive terms of n as n moves past r. This is a contradiction as, to "pass by" the integer would clearly require divisibility for one of the adjacent terms (i.e. r).

I'll attempt to formalise the last bit: clearly an=an+1a_{n}=a_{n+1} as it "passes by" the value of r. So let an=an+1=x a_{n}=a{n+1}=x. This implies nx<r<n+1x \frac{n}{x} <r <\frac{n+1}{x} which implies rx rx is not an integer (as its between n and n+1) therefore the inequality is not strict and r does infact equal either of the two (i.e. is in bn b_{n}). This is contrary to our assumption. Therefore no such r exists. QE"mother-****ing"D.

Right, I see. Now, take it as an advice, not a pedantic remark, you have to prove that bn=1b_{n}=1 for some positive integer nn in order your solution to be complete.

Original post by Jkn
It was staring us in the face the whole time! :biggrin: AM-GM is overkill in so many situations! Plus you don't tend to learn anything new about the equation. I see it as a subsidiary 'implicit' method, just like induction (though, of course, these methods are highly useful if all you need to do is 'prove' or 'solve'), wouldn't you agree? :smile:


I agree, of course. It is a nice idea to delve into the problem, but this is possible only when you have time and interest in the problem.
Reply 608
Original post by bananarama2
My maths interview was alright, although I blanked and I blanked on a chemistry question in my science interview too. I'd met my interviewer at the open day but I don't think he remembered me. Teachers do have a habit of saying what they just said in a slightly different way when you want more detailed information.

Why did you change your mind?

Classic science teachers :')

Well I was only every really interested in theoretical physics and 'the big questions' (sheldon-cooper style, standard) and I met some current student at my open day, one from maths and one from natsci, and they said that maths was 100% the best route into it and that even 'maths with physics' in my first year would hold me back!

That was the first step and since then I've found that the beauty and satisfaction in pure maths is immense and is completely different to everything else I've experienced. Besides, I'm not really fussed about money and I don't want to dedicate my life to coming up with things that makes peoples lives easier, so why not explore the cosmos/ mathematical universe! :smile:
Original post by Mladenov
SL=Shortlist

Spoiler



Yes, it is what I do. Nope, we do not have to pay:tongue:(these schools are public, as almost everything here:biggrin:).

Right, I see. Now, take it as an advice, not a pedantic remark, you have to prove that bn=1b_{n}=1 for some positive integer nn in order your solution to be complete.

I agree, of course. It is a nice idea to delve into the problem, but this is possible only when you have time and interest in the problem.

Cheers! Your MO 3rd round looks bizarrely accessible :O

Oh thats awesome :smile:

But that's fairly trivial because is r=1, rather than n, then n<x<n+1n < x < n+1 :biggrin:
Reply 609
Original post by Jkn

Cheers! Your MO 3rd round looks bizarrely accessible :O

Oh thats awesome :smile:

But that's fairly trivial because is r=1, rather than n, then n<x<n+1n < x < n+1 :biggrin:


The idea was to secure the existence of nn such that bn<rb_{n} < r.

Spoiler


Our third round problems are for the daycare.:biggrin:
Try 4th round problems or TST.
Reply 610
Original post by Mladenov
The idea was to secure the existence of nn such that bn<rb_{n} < r.

Spoiler


Our third round problems are for the daycare.:biggrin:
Try 4th round problems or TST.


*coughcough*pedantic*coughcough*!!! :lol:
I think we all have a higher level of rigour when writing on paper rather than typing latex code into a computer! Someone needs to invent a mathematical keyboard :frown:

If you know of some nice algebra ones then post away!
Reply 611
Original post by Jkn
*coughcough*pedantic*coughcough*!!! :lol:
I think we all have a higher level of rigour when writing on paper rather than typing latex code into a computer! Someone needs to invent a mathematical keyboard :frown:

If you know of some nice algebra ones then post away!


I can't agree more.
That is why I said my remark was rather punctual.

What kind of algebra?

Here is one interesting.

Problem 84**

Let SS be a set of nn elements. Denote by P(S)\mathcal{P}(S) the set of all subsets of SS.
Suppose f:P(S)Z+f: \mathcal{P}(S) \to \mathbb{Z^{+}} satisfies:
i) for every subset AA of SS, we have f(A)=f(SA)f(A)=f(S-A);
ii) for every two subsets AA and BB of SS, we have max(f(A),f(B))f(AB)\max(f(A),f(B)) \ge f(A \cup B).
Then, the number of positive integers mm such that there exists ASA \subseteq S with f(A)=mf(A)=m is less than nn.
(edited 10 years ago)
Reply 612
Original post by Mladenov

What kind of algebra?

Not necessarily algebra, just one */** problems. I haven't done set theory, am-gm, etc... formally and so my understanding of them is likely to be very limited (and most people on here can probably empathise). :smile: (though it is nice to 'have a go')

Having said that it is nice with problems like 80 where we collective produce 4 radically different, yet equally valid, solutions :smile:
(edited 10 years ago)
Reply 613
Original post by Jkn
Not necessarily algebra, just one */** problems. I haven't done set theory, am-gm, etc... formally and so my understanding of them is likely to be very limited (and most people on here can probably empathise). :smile: (though it is nice to 'have a go')

Having said that it is nice with problems like 80 where we collective produce 4 radically different, yet equally valid, solutions :smile:


I understand.
I am not acquainted with the A level content, so I hope that this is suitable.

Problem 85*

How many common terms have the following arithmetic progressions:
2,7,12,17,..2,7,12,17,.. and 2,5,8,11,..2,5,8,11,.., if they have the same number of terms - 121121?

Problem 86*

Solve in integers:
1+x+x2=yn1+x+x^{2}=y^{n}, where n2n \ge 2 is even number.
Reply 614
Original post by Mladenov

Problem 85*

How many common terms have the following arithmetic progressions:
2,7,12,17,..2,7,12,17,.. and 2,5,8,11,..2,5,8,11,.., if they have the same number of terms - 121121?


Solution 85

Sequences are 5n+2,3m+2 5n+2, 3m+2 for non-negative integers n and m. As each term has at most 121 terms so the largest common terms is min(5(120)+2,3(120)+2)=363min(5(120)+2,3(120)+2)=363.

Equating the two sequences gives 5n=3m 5n=3m so 5m,3n 5|m, 3|n . This implies common sequence=15q+215q+2 for some non-negative integer p. As max(15q+2)=363,15q+2362 max(15q+2)=363, 15q+2 \leq 362 so 0q24 0 \leq q \leq 24 .

Therefore there are 25 solutions to the original equations.
(really mladenov?)
Reply 615
Original post by Mladenov

Problem 86*

Solve in integers:
1+x+x2=yn1+x+x^{2}=y^{n}, where n2n \ge 2 is even number.


Solution 86

Let n=2mn=2m for some positive integer m.

x(x+1)=y2m1x(x+1)=y^{2m}-1 so y is odd. Solving the quadratic gives... x=1±4y2m32 x=\frac{-1±\sqrt{4y^{2m}-3}}{2} and, as y is odd this is an integer if and and if 4y2m3=q2 4y^{2m}-3=q^2 for some integer q.

Rearranging we get (2ymq)(2ym+q)=3(2y^m-q)(2y^m+q)=3. As 3 is prime the possible factors are (±1,±3), (±3,±1).

This gives ym=y^m=±1 (taking note of the parity of m) and hence yn=1y^n=1 is the only solution.

Substituting back in gives x(x+1)=0x(x+1)=0. Therefore all possible solutions are:

(x,y)=(0,±1) or (-1,±1)
(edited 10 years ago)
Reply 616
Nice. I will give you something different.

Check your solutions to problem 86. You have missed solutions and (1,1)(1,1) is not a solution, for example.

Problem 87*

A group of boys and girls went to a dance party. It is known that for every pair of boys, there are exactly two girls who danced with both of them; and for every pair of girls there are exactly two boys who danced with both of them. Prove that the numbers of girls and boys are equal.
(edited 10 years ago)
Reply 617
Original post by Mladenov
Nice. I will give you something different.

Check your solutions to problem 86. You have missed solutions and (1,1)(1,1) is not a solution, for example.

Whoops randomly put 1 and -1 instead of 0 and -1 (copied it wrong from the paper i did it on :lol:) Should be fine now!

I'll give it a go when I get some time!
(edited 10 years ago)
Reply 618
Original post by Mladenov

Problem 86*

Solve in integers:
1+x+x2=yn1+x+x^{2}=y^{n}, where n2n \ge 2 is even number.


Spoiler

(edited 10 years ago)
Reply 619
Just remembered a really nice STEP question I did while ago and thought of this...

Problem 88*

P(N)P(N) is defined as the largest product that can be made from positive integers that add up to N.

i.e. P(N)=max(a1a2...an):N=a1+a2+...+anP(N)=max(a_{1}a_{2}...a_{n}) : N= a_{1}+a_{2}+...+a_{n}.

Prove the Goldbach Conjecture

Spoiler



Problem 89*

Find the smallest prime number NN such that the following is true:

The largest prime factor of N-1 is A;
The largest prime factor of A-1 is B;
The largest prime factor of B-1 is 7.
(edited 10 years ago)

Quick Reply

Latest