Login

Welcome, Guest. Please login or register.

March 29, 2024, 03:05:42 am

Author Topic: --  (Read 6485 times)  Share 

0 Members and 1 Guest are viewing this topic.

FlorianK

  • Victorian
  • Forum Leader
  • ****
  • Posts: 928
  • Respect: +64
--
« on: June 02, 2013, 04:35:43 am »
+3
--
« Last Edit: May 01, 2017, 06:57:59 pm by FlorianK »

kamil9876

  • Victorian
  • Part of the furniture
  • *****
  • Posts: 1943
  • Respect: +109
Re: FlorianK's OlympiadeMath-Thread
« Reply #1 on: June 02, 2013, 12:35:19 pm »
0
Can you give me an example. What is a quadratic number? algebraic expression?
Voltaire: "There is an astonishing imagination even in the science of mathematics ... We repeat, there is far more imagination in the head of Archimedes than in that of Homer."

FlorianK

  • Victorian
  • Forum Leader
  • ****
  • Posts: 928
  • Respect: +64
Re: FlorianK's OlympiadeMath-Thread
« Reply #2 on: June 02, 2013, 06:57:38 pm »
0
--
« Last Edit: May 01, 2017, 06:59:39 pm by FlorianK »

Alwin

  • Victorian
  • Forum Leader
  • ****
  • Posts: 838
  • Respect: +241
Re: FlorianK's OlympiadeMath-Thread
« Reply #3 on: June 02, 2013, 10:48:17 pm »
0
oh stupid me translating wrong :/

I just meant square number, so let's say you have the problem
The sequence an is defined by ao=a1=1 and an+1=14an - an-1 - 4.
Prove that all terms of this sequence are square numbers.

Is it always that I need a unique way for such problems or are their certain methods that I can use to proof that something is a square number?

and also without a calculat how can I proof that for example 824464 is a square number?

Firstly, congrats on getting in!! I could never manage more than a distinction in the AMIO comps :P

q1: use induction im pretty sure. You COULD use matrix methods, but that would be overly complicated when you go to diagonalise it.

q2: er... break 824464 down into it's prime factors? although I can see your point, since 824464=2^4×227^2  (6 prime factors, 2 distinct). A bit hard to find 227 as a prime factor. Someone will know an easy way =D
2012:  Methods [48] Physics [49]
2013:  English [40] (oops) Chemistry [46] Spesh [42] Indo SL [34] Uni Maths: Melb UMEP [4.5] Monash MUEP [just for a bit of fun]
2014:  BAeroEng/BComm

A pessimist says a glass is half empty, an optimist says a glass is half full.
An engineer says the glass has a safety factor of 2.0

kamil9876

  • Victorian
  • Part of the furniture
  • *****
  • Posts: 1943
  • Respect: +109
Re: FlorianK's OlympiadeMath-Thread
« Reply #4 on: June 05, 2013, 07:28:52 pm »
0
Quote
q1: use induction im pretty sure. You COULD use matrix methods, but that would be overly complicated when you go to diagonalise it.

Induction will not work, the reason is that if we started with different that are square numbers, the sequence need not be made up of square numbers.

E.g: gives which isn't square.

Also, matrix methods may not be so useful as is NOT a linear function of and (i.e there is a constant term -4).

I tried calculating the generating function but, if I havn't made a mistake, it doesn't look too nice either.
« Last Edit: June 05, 2013, 07:30:51 pm by kamil9876 »
Voltaire: "There is an astonishing imagination even in the science of mathematics ... We repeat, there is far more imagination in the head of Archimedes than in that of Homer."

Alwin

  • Victorian
  • Forum Leader
  • ****
  • Posts: 838
  • Respect: +241
Re: FlorianK's OlympiadeMath-Thread
« Reply #5 on: June 05, 2013, 08:40:34 pm »
0
Induction will not work, the reason is that if we started with different that are square numbers, the sequence need not be made up of square numbers.

E.g: gives which isn't square.

Also, matrix methods may not be so useful as is NOT a linear function of and (i.e there is a constant term -4).

I tried calculating the generating function but, if I haven't made a mistake, it doesn't look too nice either.

lol, you HAVE to use a0=1 and a1=1 ... that's your base case lol, then prove for n>2. That's kinda the point of induction... prove the base case.

And the matrix method is:

EDIT OH MY GOD I MADE THE WORST MISTAKE. DON'T EVEN LOOK AT WHAT I WROTE IS IS HORRENDOUS. MEANT TO BE A 3x3 not a 2x2. SORRY
Spoiler




Clearly,


Hence,


Use initial condition a0=a1=1,


Now diagonalise M (using eigenvectors),



Clearly,





RHS = 1/24(12 (7-4 sqrt(3))^n-7 sqrt(3) (7-4 sqrt(3))^n+12 (7+4 sqrt(3))^n+7 sqrt(3) (7+4 sqrt(3))^n | sqrt(3) (7-4 sqrt(3))^n-sqrt(3) (7+4 sqrt(3))^n
-sqrt(3) (7-4 sqrt(3))^n+sqrt(3) (7+4 sqrt(3))^n | 12 (7-4 sqrt(3))^n+7 sqrt(3) (7-4 sqrt(3))^n+12 (7+4 sqrt(3))^n-7 sqrt(3) (7+4 sqrt(3))^n)
(from wolfram alpha, I can't be bothered converting to LaTex :P)

Hence,



I made a mistake somewhere, but I cbbs double checking haha.
Correct method here: Re: FlorianK's OlympiadeMath-Thread

Obviously, this is not factorised to the point n^2 which would prove that it is a square number.
Also, it's a bit ridiculous to try solve it like this by hand :P

If I have time, I'll work out a (hopefully easier) method with induction for you :P
« Last Edit: June 07, 2013, 04:57:04 pm by Alwin »
2012:  Methods [48] Physics [49]
2013:  English [40] (oops) Chemistry [46] Spesh [42] Indo SL [34] Uni Maths: Melb UMEP [4.5] Monash MUEP [just for a bit of fun]
2014:  BAeroEng/BComm

A pessimist says a glass is half empty, an optimist says a glass is half full.
An engineer says the glass has a safety factor of 2.0

kamil9876

  • Victorian
  • Part of the furniture
  • *****
  • Posts: 1943
  • Respect: +109
Re: FlorianK's OlympiadeMath-Thread
« Reply #6 on: June 05, 2013, 10:34:10 pm »
+1
Quote
lol, you HAVE to use a0=1 and a1=1 ... that's your base case lol, then prove for n>2. That's kinda the point of induction... prove the base case.

Yes I know, but my point is that if you had started with different square numbers for and then the result isn't true (even though the base case is! 4 is a square number). Now how would the inductive step go? It would be something like:

Quote
suppose and are square numbers, then ... (some working)... is a square.

But my example shows that in general and being square numbers does not imply is a square number, hence the inductive step won't work in general: there is something special about the choice of and .

So we need something better than just a simple induction.
« Last Edit: June 05, 2013, 10:57:16 pm by kamil9876 »
Voltaire: "There is an astonishing imagination even in the science of mathematics ... We repeat, there is far more imagination in the head of Archimedes than in that of Homer."

kamil9876

  • Victorian
  • Part of the furniture
  • *****
  • Posts: 1943
  • Respect: +109
Re: FlorianK's OlympiadeMath-Thread
« Reply #7 on: June 05, 2013, 10:54:48 pm »
+1
Your mistake with the matrix method is that the the map is NOT linear. I'm pretty sure that it is NOT true that



Think about it this way:

right? Now you want to somehow replace by to get that BUT you CANNOT do this! This is because there is a +4 missing for you to use your recurrence in terms of

 
Edit: In general this recurrence is not linear but what is known as Affine, i.e linear plus a constant. Now if we have a transformation then you can verify that which you can simplify using geometric sequence I guess. You can try modifying your matrix technique with this correction for the term, but like you I believe there should be a simple method given that this is some olympiad high school comp.
« Last Edit: June 05, 2013, 11:08:18 pm by kamil9876 »
Voltaire: "There is an astonishing imagination even in the science of mathematics ... We repeat, there is far more imagination in the head of Archimedes than in that of Homer."

FlorianK

  • Victorian
  • Forum Leader
  • ****
  • Posts: 928
  • Respect: +64
Re: FlorianK's OlympiadeMath-Thread
« Reply #8 on: June 06, 2013, 04:12:16 am »
0
I'm working on that problem atm, I just got to the point that

ao=a1=1 and an+1=14an - an-1 - 4.
Now let:
bo=b1=1 and bn+1=4bn - bn-1

Now I would need to proof that an=(bn

I found this sequence by just plugging in some numbers and realising a sequence in sqrt(a). Now I would just need to proof it, but I don't know how


I believe there should be a simple method given that this is some olympiad high school comp.
?!?
Of course this problem is not taken from an actual IMO paper, because I am just preparing for the selection comp, but IMO questions are incredibly hard and not just simple because it is some olympiade high school comp.

Say that again after you solved this question:

To each vertex of a regular pentagon an integer is assigned in such a way that
the sum of all five numbers is positive. If three consecutive vertices are assigned
the numbers x, y, z respectively and y < 0 then the following operation is
allowed: the numbers x, y, z are replaced by x+y, ¡y, z+y respectively. Such
an operation is performed repeatedly as long as at least one of the five numbers
is negative. Determine whether this procedure necessarily comes to an end
after a finite number of steps.


or this one

Let a and b be positive integers such that ab+1 divides a²+b². Show that (a²+b²)/(ab+1) is the square of an integer.

Alwin

  • Victorian
  • Forum Leader
  • ****
  • Posts: 838
  • Respect: +241
Re: FlorianK's OlympiadeMath-Thread
« Reply #9 on: June 06, 2013, 08:40:27 am »
-4
Off topic
Spoiler
Your mistake with the matrix method is that the the map is NOT linear. I'm pretty sure that it is NOT true that
...
but like you I believe there should be a simple method given that this is some olympiad high school comp.

CAN YOU READ?
Or did you choose not to read the big red edit I put in, or did you want an ego boost and be a smart ass :D

It's supposed to be: (or similar 3x3)



Then diagonalise, raise to power, solve etc.

Off topic
Spoiler
Yes I know, but my point is that if you had started with different square numbers for and then the result isn't true (even though the base case is! 4 is a square number).
So we need something better than just a simple induction.
Have you considered "double induction" where there are 2 assumptions, or 2 inductive steps? or have u just gone, nup not even gonna try it coz i have a much better sleeker method.

And I still don't get why you'd even want to change the initial conditions. It's just like changing the starting numbers for the Fibonacci numbers to a0=a1=2 and hoping you'll still end up with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.... which you clearly won't. So why would you want to start with different numbers in this problem..

now, if YOU have a method, don't let us stop you from posting it up. Just a suggestion :)

And FlorianK, I've seen some (similar) questions on the Melbourne Uni Maths Comps senior papers: http://www.mathscomp.ms.unimelb.edu.au/
I'm supposed to be cramming for my spesh sac (in a couple hours) so no time to help sorry! I'll post again later.
« Last Edit: June 06, 2013, 02:34:07 pm by Alwin »
2012:  Methods [48] Physics [49]
2013:  English [40] (oops) Chemistry [46] Spesh [42] Indo SL [34] Uni Maths: Melb UMEP [4.5] Monash MUEP [just for a bit of fun]
2014:  BAeroEng/BComm

A pessimist says a glass is half empty, an optimist says a glass is half full.
An engineer says the glass has a safety factor of 2.0

kamil9876

  • Victorian
  • Part of the furniture
  • *****
  • Posts: 1943
  • Respect: +109
Re: FlorianK's OlympiadeMath-Thread
« Reply #10 on: June 06, 2013, 11:41:11 am »
+7
Quote
Quote from: kamil9876 on June 05, 2013, 10:54:48 PM

    I believe there should be a simple method given that this is some olympiad high school comp.

?!?
Of course this problem is not taken from an actual IMO paper, because I am just preparing for the selection comp, but IMO questions are incredibly hard and not just simple because it is some olympiade high school comp.

Say that again after you solved this question:

By "simple" I didn't mean that the problem is easy! Of course I understand and appreciate how hard they are, I enjoyed solving such problems myself. By "simple" I really meant a method that does not use any mathematics beyond high school like Matrices.

CAN YOU READ?
Or did you choose not to read the big red edit I put in, or did you want an ego boost and be a smart ass :D
Quote
Have you considered "double induction" where there are 2 assumptions, or 2 inductive steps? or have u just gone, nup not even gonna try it coz i have a much better sleeker method.

Geez, can you please stop being so defensive. I'm sorry for reading your post, if you don't want me to read the working and make absolutely no comments about it then delete that part of the post. After all you did say:

Quote
I might have made a mistake somewhere, but I cbbs double checking haha.

Now the "might" indicates that you don't know where you made a mistake, or that you did indeed make one. I was just trying to tell you where thinking that you may appreciate that - but no, sorry, you would rather me say absolutely nothing.

As for the double induction - Yes that is why I said "simple induction" won't work, but of course I would like to see if there is some stronger induction that could be done.

Quote
So why would you want to start with different numbers in this problem..

Because it shows that straightforward induction won't work (but of course as you mentioned a stronger one may). Please read my other post for an explanation.



« Last Edit: June 06, 2013, 11:44:18 am by kamil9876 »
Voltaire: "There is an astonishing imagination even in the science of mathematics ... We repeat, there is far more imagination in the head of Archimedes than in that of Homer."

kamil9876

  • Victorian
  • Part of the furniture
  • *****
  • Posts: 1943
  • Respect: +109
Re: FlorianK's OlympiadeMath-Thread
« Reply #11 on: June 06, 2013, 12:41:05 pm »
0
Quote
I'm working on that problem atm, I just got to the point that

ao=a1=1 and an+1=14an - an-1 - 4.
Now let:
bo=b1=1 and bn+1=4bn - bn-1

Now I would need to proof that an=(bn)²

I found this sequence by just plugging in some numbers and realising a sequence in sqrt(a). Now I would just need to proof it, but I don't know how

Nice! I still don't know how you found but it does indeed work. You may prove by induction but you need a strong induction like this:

Let P(n) be the statement: and

Then Is clearly true since it just says and . Then assuming P(n), you may derive P(n+1) with some straightforward algebra.

I'm still wondering how you guessed the correctly.
« Last Edit: June 06, 2013, 12:43:33 pm by kamil9876 »
Voltaire: "There is an astonishing imagination even in the science of mathematics ... We repeat, there is far more imagination in the head of Archimedes than in that of Homer."

Alwin

  • Victorian
  • Forum Leader
  • ****
  • Posts: 838
  • Respect: +241
Re: FlorianK's OlympiadeMath-Thread
« Reply #12 on: June 06, 2013, 01:41:34 pm »
0
Put the post in a spoiler since its off topic and pretty rude. Point taken b^3, sorry kamil9876.

Spoiler
Geez, can you please stop being so defensive. I'm sorry for reading your post, if you don't want me to read the working and make absolutely no comments about it then delete that part of the post.

Nah, not being defensive, just again wondering if you can read. I did post what the actual matrix equation should be with 3x3, but of course you chose to conveniently not see it :D And never occurred to you that I left my incorrect working because I intended to go back and change it which is why I put it in a spoiler? Or that I left it to show the process even if the matrices are incorrect, so if anyone chose to do it they could, using the correct 3x3?

As for the double induction - Yes that is why I said "simple induction" won't work, but of course I would like to see if there is some stronger induction that could be done.

Because it shows that straightforward induction won't work (but of course as you mentioned a stronger one may). Please read my other post for an explanation.

Now, I never said "simple induction" did I? You just assumed that because it was someone else's idea ( I have yet to see your method of approaching this problem, nor anything really constructive either), that it would be "simple"? I meant, if I so wanted to, I could use 2 assumption P(k-1) and P(k) times them or raise each to a power then substitute into P(k+1). I haven't tried this yet, redoing the matrices atm so don't leap to the opportunity of being able to attack someone again :D When I said induction in the first place, I meant any sort of induction, if I wanted to I could prove that is irrational using induction, and I'd still call that a proof by induction.

Although, perhaps I'm being a bit harsh on you! after all, your worth while contribution:
Let P(n) be the statement: and

Then Is clearly true since it just says and . Then assuming P(n), you may derive P(n+1) with some straightforward algebra.

I'm still wondering how you guessed the correctly.

You mind actually helping FlorianK then? Afterall, its just some "straightforward algebra". And you're such a nice person, labelling it a "guess". I'm sure your opposed to penicillin too, since that was an accident. Btw, if you were actually curious, you can run the numbers too and come to a similar conclusion.

EDIT: sorry mate, it's just I saw your email when I was coming out of my spesh sac. My fault, sorry. No hard feelings? I'm doing the new matrix method now, I'll post it when I'm done, by all means correct me if I'm wrong - sorry for being a jerk in the other posts^
« Last Edit: June 06, 2013, 01:48:26 pm by Alwin »
2012:  Methods [48] Physics [49]
2013:  English [40] (oops) Chemistry [46] Spesh [42] Indo SL [34] Uni Maths: Melb UMEP [4.5] Monash MUEP [just for a bit of fun]
2014:  BAeroEng/BComm

A pessimist says a glass is half empty, an optimist says a glass is half full.
An engineer says the glass has a safety factor of 2.0

b^3

  • Honorary Moderator
  • ATAR Notes Legend
  • *******
  • Posts: 3529
  • Overloading, just don't do it.
  • Respect: +631
  • School: Western Suburbs Area
  • School Grad Year: 2011
Re: FlorianK's OlympiadeMath-Thread
« Reply #13 on: June 06, 2013, 01:42:53 pm »
+2
Going to go slightly off topic but need to make a point here.
Alwin, you didn't have to be slightly condescending, implying that kamil9876 didn't understand induction, and then have a go at him for apparently trying to get an ego boost. kamil9876 is an older respected member of the community whose contributed a fair bit over the last couple of years, the post wasn't for an ego boost or a direct attack on you, it was actually to point out where you went wrong and try and help you out, unlike the posts coming from the other direction at that point.

Anything else on the matter that's become off topic after this should be taken to pm, or I'll have to split posts from the thread.
2012-2016: Aerospace Engineering/Science (Double Major in Applied Mathematics - Monash Uni)
TI-NSPIRE GUIDES: METH, SPESH

Co-Authored AtarNotes' Maths Study Guides


I'm starting to get too old for this... May be on here or irc from time to time.

b^3

  • Honorary Moderator
  • ATAR Notes Legend
  • *******
  • Posts: 3529
  • Overloading, just don't do it.
  • Respect: +631
  • School: Western Suburbs Area
  • School Grad Year: 2011
Re: FlorianK's OlympiadeMath-Thread
« Reply #14 on: June 06, 2013, 01:44:44 pm »
+1
And you're such a nice person, labelling it a "guess". I'm sure your opposed to penicillin too, since that was an accident. Btw, if you were actually curious, you can run the numbers too and come to a similar conclusion.
Uncalled for, stop bickering and get back to the maths.
2012-2016: Aerospace Engineering/Science (Double Major in Applied Mathematics - Monash Uni)
TI-NSPIRE GUIDES: METH, SPESH

Co-Authored AtarNotes' Maths Study Guides


I'm starting to get too old for this... May be on here or irc from time to time.