HSC 2014 MX2 Marathon ADVANCED (archive) (4 Viewers)

[mathing]

Re: HSC 2014 4U Marathon - Advanced Level

Wonderful!

For x < 0, define f(x) = af(-x) + bf(-2x)+cf(-3x) (*) for some undetermined constants a,b,c.

It is clear that this will satisfy the differentiability and boundedness assumptions of f for positive x, just by the laws of how differentiation behaves with respect to addition, constant multiplication, and composition. This means that the only thing to worry about is how the definitions of f for positive x and negative x "match up" at 0.

If we let x -> 0- in (*) and use continuity, we get f(0) = (a+b+c)f(0).

Similarly, since we have differentiability, we can differentiate (*) (at least twice) and then use continuity of derivatives to get:

f'(0) = (-a-2b-3c)f'(0).

f''(0) = (a+4b+9c)f''(0).

Now if we choose our a,b,c to satisfy the simultaneous equations:

a+b+c = 1
-a-2b-3c = 1
a+4b+9c = 1

(this is a short exercise in simultaneous equations, but I cbb doing it again right now) then from the earlier discussion the function and its first two derivatives will match up continuously, and we are done.

 

[mathing]

Re: HSC 2014 4U Marathon - Advanced Level

He's on fire today.

Suppose to the contrary that f IS reducible over Z and f = gh is one such expression with deg(g) > n/2 > deg(h). Note that we can assume strict inequality of degrees because their sum is deg(f) = n which is odd. This turns out to be key.

g(aj)h(aj) = -1 for each j, but since both of these polynomials has integer coefficients, both of these factors must be integers. That implies that for each j we either have:

I) g(aj) = 1 h(aj) = -1

or

II) g(aj) = -1 h(aj) = 1.

One of these must occur strictly more often than the other (again as n is odd), and so we have h(x) = c for some c (either 1 or -1, we don't really care) and at least n/2 > deg(h) different values of x. But this is a contradiction, as the definition of reducibility (Sy forgot to mention this ) requires that the two factor polynomials are non-constant, and no non-constant polynomial can assume the same value as many times as (its degree + 1) for the same reason that no non-constant polynomial can have more roots than its degree.

So we are done.

 

[seanieg89]

Re: HSC 2014 4U Marathon - Advanced Level

Just a fun bit of morning procrastination .

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

Not sure if this is what you are looking for but we can apply the tan addition formula to get



You can also see the last fraction is the definition of the two derivatives at u = 0.

Yep this was my method, well done.

Suppose to the contrary that f IS reducible over Z and f = gh is one such expression with deg(g) > n/2 > deg(h). Note that we can assume strict inequality of degrees because their sum is deg(f) = n which is odd. This turns out to be key.

g(aj)h(aj) = -1 for each j, but since both of these polynomials has integer coefficients, both of these factors must be integers. That implies that for each j we either have:

I) g(aj) = 1 h(aj) = -1

or

II) g(aj) = -1 h(aj) = 1.

One of these must occur strictly more often than the other (again as n is odd), and so we have h(x) = c for some c (either 1 or -1, we don't really care) and at least n/2 > deg(h) different values of x. But this is a contradiction, as the definition of reducibility (Sy forgot to mention this ) requires that the two factor polynomials are non-constant, and no non-constant polynomial can assume the same value as many times as (its degree + 1) for the same reason that no non-constant polynomial can have more roots than its degree.

So we are done.

Yes this was also my solution, nice.

 

[RealiseNothing]

Re: HSC 2014 4U Marathon - Advanced Level

Consider a chessboard (so 8 columns and 8 rows).

The columns are labelled from left to right, 1 through to 8.

The rows are labelled from top to bottom, A through to H.

A knight/horse starts on square A1.

A horse moves in an L shaped manner, so it goes two squares in one direction, then one square perpendicular to the original direction.

After 4000 moves (hello post #4000), what are the possible squares that the knight/horse can be on?

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

Consider a chessboard (so 8 columns and 8 rows).

The columns are labelled from left to right, 1 through to 8.

The rows are labelled from top to bottom, A through to H.

A knight/horse starts on square A1.

A horse moves in an L shaped manner, so it goes two squares in one direction, then one square perpendicular to the original direction.

After 4000 moves (hello post #4000), what are the possible squares that the knight/horse can be on?

Can the Knight go to the position it was the previous move?

i.e. A1 to B3 to A1 again

If this is so, I am pretty sure it can go on all squares of the board, because at some point in the moving, say I want my end position to be (x,y). I can just go to (x-1,y-2), once I get there, I'll just alternate between (x-1,y-2) and (x,y) until the moves become 4000

 

[aDimitri]

Re: HSC 2014 4U Marathon - Advanced Level

what if on the 4000th move you end up on (x-1, y-2), rather than on(x,y)?

EDIT:
I did a drawing and tried it out a bit, and i'm fairly positive there is no combination of moves to remedy this. If you hit (x,y) on an odd move, i don't think you can get there on the 4000th?

 

[seanieg89]

Re: HSC 2014 4U Marathon - Advanced Level

Can the Knight go to the position it was the previous move?

i.e. A1 to B3 to A1 again

If this is so, I am pretty sure it can go on all squares of the board, because at some point in the moving, say I want my end position to be (x,y). I can just go to (x-1,y-2), once I get there, I'll just alternate between (x-1,y-2) and (x,y) until the moves become 4000

Well, the colour of the square the knight is on after the 4000th move is fixed, so we can rule out half of the board.

Your idea basically shows that it can be any of the squares of the correct colour though.

 

[aDimitri]

Re: HSC 2014 4U Marathon - Advanced Level

Following that logic, my solution is any square the same colour as A1

 

[aDimitri]

Re: HSC 2014 4U Marathon - Advanced Level

Well, the colour of the square the knight is on after the 4000th move is fixed, so we can rule out half of the board.

Your idea basically shows that it can be any of the squares of the correct colour though.

Well thats exactly what I got I was just a minute late

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

Well, the colour of the square the knight is on after the 4000th move is fixed, so we can rule out half of the board.

Your idea basically shows that it can be any of the squares of the correct colour though.

Following that logic, my solution is any square the same colour as A1

Well thats exactly what I got I was just a minute late

I have made a program to simulate this in Java.

It seems we can get squares of different colour to A1, its just that my 'strategy' will guarantee every square same colour as A1, but there may be more solutions using different strategies

If you have ECLIPSE or another Java compiling program, feel free to run my code:

http://pastebin.com/shbHjTKA

I am pretty sure my code is correct, though there may be some malfunction, I will keep debugging

For example:

(0,0) -> (1,2) -> (3,3) -> (5,4)

Which is different to (0,0)

 

[RealiseNothing]

Re: HSC 2014 4U Marathon - Advanced Level

I have made a program to simulate this in Java.

It seems we can get squares of different colour to A1, its just that my 'strategy' will guarantee every square same colour as A1, but there may be more solutions using different strategies

If you have ECLIPSE or another Java compiling program, feel free to run my code:

http://pastebin.com/shbHjTKA

I am pretty sure my code is correct, though there may be some malfunction, I will keep debugging

For example:

(0,0) -> (1,2) -> (3,3) -> (5,4)

Which is different to (0,0)

As a knight, it goes from black to white to black to white etc. There is no other way for it to move.

And (0,0) is a different colour to (5,4), but you only used 3 moves, not an even number as is 4000.

 

[aDimitri]

Re: HSC 2014 4U Marathon - Advanced Level

As a knight, it goes from black to white to black to white etc. There is no other way for it to move.

And (0,0) is a different colour to (5,4), but you only used 3 moves, not an even number as is 4000.

Yep exactly what I was going to say. It always alternates colours so there is absolutely no way it can get from white to black in an even number of moves.

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

As a knight, it goes from black to white to black to white etc. There is no other way for it to move.

And (0,0) is a different colour to (5,4), but you only used 3 moves, not an even number as is 4000.

Yes that is true, my bad

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

Also in case anyone is interested, if we take the additional condition that one cannot go back on the move the next turn, i.e.

(0,0) -> (1,2) -> (0,0) is invalid

We still get the whole half of the board (according to my generated diagrams)

 

[RealiseNothing]

Re: HSC 2014 4U Marathon - Advanced Level

Also in case anyone is interested, if we take the additional condition that one cannot go back on the move the next turn, i.e.

(0,0) -> (1,2) -> (0,0) is invalid

We still get the whole half of the board (according to my generated diagrams)

I wonder if we can prove that mathematically.

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

I wonder if we can prove that mathematically.

I think we can still make the same argument as before, but instead of alternating between 2, we alternate between 4 instead.

Since 4000/4 is an integer, we can still arrive on everything using a '4-cycle'

What would be interesting is that if instead of 4000, we have a prime number.

If it is prime, i don't think we can have this sort of 'cycle'

 

[RealiseNothing]

Re: HSC 2014 4U Marathon - Advanced Level

I think we can still make the same argument as before, but instead of alternating between 2, we alternate between 4 instead.

Since 4000/4 is an integer, we can still arrive on everything using a '4-cycle'

What would be interesting is that if instead of 4000, we have a prime number.

If it is prime, i don't think we can have this sort of 'cycle'

Yer I was thinking of using a prime number when I made the question, but I wanted 4000 to go with the post count.

btw how's 1902 going?

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

Using Prime numbers gives all the board:

Black blocks are blocks where the knight has not ended
Red blocks are blocks where the knight has ended.
The number of iterations shows how many times it has been done, and shows the various positions it has ended.

The number of moves is set at 19 (prime)

10 iterations:

20 iterations:

100 iterations:

1000 iterations (ignore black dot in corner, I think its just my program, I think, not sure why its there)

EDIT: This works with most odd numbers that I'm trying, I don't think its something special with primes

 

[Sy123]

Re: HSC 2014 4U Marathon - Advanced Level

Yer I was thinking of using a prime number when I made the question, but I wanted 4000 to go with the post count.

btw how's 1902 going?

I haven't gotten around to grounding myself well yet, I still don['t know what eigenvectors/values are