HSC 2015 MX2 Marathon ADVANCED (archive) (5 Viewers)

glittergal96 · Jul 16, 2015

Re: HSC 2015 4U Marathon - Advanced Level

SilentWaters said:
At the very least, therefore, all lines after this will add 1 new intersection to the plane. This is the best case scenario, where we keep adding lines to the intersection shared by the r-1 lines from before (ensuring that each new line intersects with all other lines except for the rth one, which it will have to intersect at a separate point).

Could you explain in more detail why this is true please? Perhaps I am missing something basic, but I don't see how this quoted claim follows.

It is clear that the (r+1)-th line must add an intersection:
[Indeed for it to not do so, it would have to meet every previous line only at prior intersection points. So it must meet the r-th line at one of the (r-1) intersection point it added. But then the only lines through such a point which only meet other lines at prior intersection points are already drawn! (In particular, these are the lines through your "initial" point of intersection, and the r-th line itself).]

What is not clear to me however, is that a subsequent line must also add an intersection, especially if we are not optimal in between, so we lose the "form" of having all lines but one through the initial intersection point.

Eg Why is it out of the question to have a sequence like: 1,0,0,0,4,1,1,2,0,0 (=10 lines 9 int. points)?

marinus96 · Jul 16, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Once we lose the form of having all lines through a single, common intersection point (the initial one), there is no way that subsequent lines can contribute zero intersections to the plane. This is because there is no point on the plane where an added line can intersect all others at once.

So in your example sequence, 1,0,0,0,4,1,1,2,0,0 we can see that at the 5th line, a new intersection has been created, so that on the plane we have a situation where there are:
- 4 intersections shared by 2 lines: (1,5), (2,5), (3,5), (4,5) [where 1,5 denotes the first and the fifth added line]
- 1 intersection shared by 4 lines: (1,2,3,4)

Would it not be sufficient at this point to say that all subsequent lines cannot add 0 int.'s to the plane, since no prior intersection encompasses all previous lines?

glittergal96 · Jul 16, 2015

Re: HSC 2015 4U Marathon - Advanced Level

marinus96 said:
Once we lose the form of having all lines through a single, common intersection point (the initial one), there is no way that subsequent lines can contribute zero intersections to the plane. This is because there is no point on the plane where an added line can intersect all others at once.

So in your example sequence, 1,0,0,0,4,1,1,2,0,0 we can see that at the 5th line, a new intersection has been created, so that on the plane we have a situation where there are:
- 4 intersections shared by 2 lines: (1,5), (2,5), (3,5), (4,5) [where 1,5 denotes the first and the fifth added line]
- 1 intersection shared by 4 lines: (1,2,3,4)

Would it not be sufficient at this point to say that all subsequent lines cannot add 0 int.'s to the plane, since no prior intersection encompasses all previous lines?

Why is it not possible for a new line to meet all other lines over several previously existing int. points rather than "at once"? This possibility would also be the addition of a line without adding int. points.

SilentWaters · Jul 16, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Suppose we set up a system of lines to accommodate this. This would imply at least 2 intersections, each of which are the meeting places for at least 2 lines (one intersection would have lines 1 and 2, and the second, lines 3 and 4). Our sequence would begin with 1,2,3; and after adding 4 lines to the plane we are already dealing with 6 intersections. We don't even have to consider adding the 5th line (which will add zero intersections by passing through [1,2] and [3,4]) to see that this cannot minimize the total number of intersections.

Admittedly, yes, a line which contributes zero intersections can meet all other lines through one point or several. But in looking at the "several" case, we find ourselves over the n quota before we even add the line that will contribute no intersections. That should justify optimizing our interpretation of a zero int. contribution to a line that passes through one point where all other points meet.

glittergal96 · Jul 16, 2015

Re: HSC 2015 4U Marathon - Advanced Level

SilentWaters said:
Admittedly, yes, a line which contributes zero intersections can meet all other lines through one point or several. But in looking at the "several" case, we find ourselves over the n quota before we even add the line that will contribute no intersections. That should justify optimizing our interpretation of a zero int. contribution to a line that passes through one point where all other points meet.

I know that this is intuitively true, but what you have written isn't a proof. You would need to prove that "you would be over the n quota" before we add the line of zero contribution. I am not sure this is any easier than the initial problem really.

glittergal96 · Jul 16, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Okay, I think I figured out a proof. I have to go out now but I can write it up later if people want.

The idea:

Use a stereographic projection (put a unit sphere on the origin and for any given point on the plane, draw a line in 3d space between this point and the north pole of the sphere. the projection maps the point on the plane to the non-pole point on the sphere that this line meets).

Additionally, every line passing through infinity shows up as the image of every line under this projection passing through the north pole. So we might as well stick another point on there and now we have a problem on the sphere.

But the point is the thing we have on the sphere is a graph! And so we can use Euler's formula (with knowledge of the sphere's Euler characteristic, which is easily proven by induction).

I am pretty sure the resulting inequalities allow us to prove that there must be at least three points of degree 4 in this graph, which implies that there must be at least three int. points of degree 2 in our initial problem. This means that the inductive approach works.

I can write up the inequalities when I get home, but I really have to go now.

shervos · Jul 17, 2015

Re: HSC 2015 4U Marathon - Advanced Level

glittergal96 said:
Okay, I think I figured out a proof. I have to go out now but I can write it up later if people want.

The idea:

Use a stereographic projection (put a unit sphere on the origin and for any given point on the plane, draw a line in 3d space between this point and the north pole of the sphere. the projection maps the point on the plane to the non-pole point on the sphere that this line meets).

Additionally, every line passing through infinity shows up as the image of every line under this projection passing through the north pole. So we might as well stick another point on there and now we have a problem on the sphere.

But the point is the thing we have on the sphere is a graph! And so we can use Euler's formula (with knowledge of the sphere's Euler characteristic, which is easily proven by induction).

I am pretty sure the resulting inequalities allow us to prove that there must be at least three points of degree 4 in this graph, which implies that there must be at least three int. points of degree 2 in our initial problem. This means that the inductive approach works.

I can write up the inequalities when I get home, but I really have to go now.

please post your solution. Are the ideas really motivable by a 4u student though?

Here's something which CAN be done with mere 4u techniques.
Find all real polynomials which satisfy p (x -1) *p (x+1)=p (x^2+1)

glittergal96 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
please post your solution. Are the ideas really motivable by a 4u student though?

Here's something which CAN be done with mere 4u techniques.
Find all real polynomials which satisfy p (x -1) *p (x+1)=p (x^2+1)

Okay sure, sorry about the delay.

For the record, I wouldn't expect many current MX2 students if any to come up with my proof, but I think there is probably some nicer way of doing it (its one of the earlier exercises in an olympiad training collection, so is more about clever application of high school tools than any higher powered techniques).

First, we project from the plane onto the unit sphere sitting on the origin of the plane, by looking at where the line through the centre of this sphere and our point on the plane meets the sphere. This maps points on the plane to pairs of antipodal points on the sphere. (Technically it is only a function onto projective space, but this is not important for us.)

So now we have a sphere with n great circles drawn on it, with some 2m points of intersection (where m is the number of intersection points on the plane). These great circles divide the sphere into polygonal regions, and give us a natural graph structure.

By Euler's formula (which can be proven by induction), we have

V-E+F=2

for this graph.

Now, let's get some notation going:

Let V(k) be the number of intersection points on our original plane with k lines passing through them.
Let F(k) be half of the number of polygonal "faces" on our sphere with k sides. (The numbers of polygonal faces of each degree are even by reflective symmetry.)

Then we have:

$V=2\sum_{k\geq 2} V(k)$

$F=2\sum_{k\geq 3} F(k)$

and we can count edges in terms of faces and vertices in two ways

$E=2\sum_{k\geq 2} kV(k)=\sum_{k\geq 3} kF(k)$

Now Euler's formula implies:

$6=(3V-E)+(3F-2E)\\ = 2\sum_{k\geq 2}(3-k)V(k)+2\sum_{k\geq 3}(3-k)F(k) \\ \leq 2V(2).$

Hence there exist at least three points in our plane with only two lines passing through them. This means that we can use induction in the way Sy outlined to complete the proof.

shervos · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

glittergal96 said:
Okay sure, sorry about the delay.

For the record, I wouldn't expect many current MX2 students if any to come up with my proof, but I think there is probably some nicer way of doing it (its one of the earlier exercises in an olympiad training collection, so is more about clever application of high school tools than any higher powered techniques).

First, we project from the plane onto the unit sphere sitting on the origin of the plane, by looking at where the line through the centre of this sphere and our point on the plane meets the sphere. This maps points on the plane to pairs of antipodal points on the sphere. (Technically it is only a function onto projective space, but this is not important for us.)

So now we have a sphere with n great circles drawn on it, with some 2m points of intersection (where m is the number of intersection points on the plane). These great circles divide the sphere into polygonal regions, and give us a natural graph structure.

By Euler's formula (which can be proven by induction), we have

V-E+F=2

for this graph.

Now, let's get some notation going:

Let V(k) be the number of intersection points on our original plane with k lines passing through them.
Let F(k) be half of the number of polygonal "faces" on our sphere with k sides. (The numbers of polygonal faces of each degree are even by reflective symmetry.)

Then we have:

$V=2\sum_{k\geq 2} V(k)$

$F=2\sum_{k\geq 3} F(k)$

and we can count edges in terms of faces and vertices in two ways

$E=2\sum_{k\geq 2} kV(k)=\sum_{k\geq 3} kF(k)$

Now Euler's formula implies:

$6=(3V-E)+(3F-2E)\\ = 2\sum_{k\geq 2}(3-k)V(k)+2\sum_{k\geq 3}(3-k)F(k) \\ \leq 2V(2).$

Hence there exist at least three points in our plane with only two lines passing through them. This means that we can use induction in the way Sy outlined to complete the proof.

you should attempt my problem!

dan964 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

^^
You could take the minimalist approach

For n lines (note n>3)
Note that each line (non-parallel) creates one intersection point with each other line.
The limiting case, is (n-1) lines pass through the same point*, thus creating 1 intersection point
The nth line creates (n-1) intersection points
*as stating all lines must not pass through one given point.

(similar can be done for other cases)

---
<2>
p (x -1) *p (x+1)=p (x^2+1)
couldn't this be expressed as

$p^{2} \times (x^{2}-1)=p(x^{2}+1)$

$p \times (x^{2}-1)=(x^{2}+1)$
$(p-1) \times x^{2} -(p+1)=0$

$x^{2} = \frac{p+1}{p-1}$

$\frac{p+1}{p-1} > 0$ as it is real

shervos · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

dan964 said:
^^
You could take the minimalist approach

For n lines (note n>3)
Note that each line (non-parallel) creates one intersection point with each other line.
The limiting case, is (n-1) lines pass through the same point*, thus creating 1 intersection point
The nth line creates (n-1) intersection points
*as stating all lines must not pass through one given point.

(similar can be done for other cases)

---
<2>
p (x -1) *p (x+1)=p (x^2+1)
couldn't this be expressed as

$p^{2} \times (x^{2}-1)=p(x^{2}+1)$

$p \times (x^{2}-1)=(x^{2}+1)$
$(p-1) \times x^{2} -(p+1)=0$

$x^{2} = \frac{p+1}{p-1}$

what are you talking about. p(x) refers to a polynomial..........not p * (x-1).....

shervos · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

dan964 said:
^^
You could take the minimalist approach

For n lines (note n>3)
Note that each line (non-parallel) creates one intersection point with each other line.
The limiting case, is (n-1) lines pass through the same point*, thus creating 1 intersection point
The nth line creates (n-1) intersection points
*as stating all lines must not pass through one given point.

(similar can be done for other cases)

---
<2>
p (x -1) *p (x+1)=p (x^2+1)
couldn't this be expressed as

$p^{2} \times (x^{2}-1)=p(x^{2}+1)$

$p \times (x^{2}-1)=(x^{2}+1)$
$(p-1) \times x^{2} -(p+1)=0$

$x^{2} = \frac{p+1}{p-1}$

$\frac{p+1}{p-1} > 0$ as it is real

also, ur solution for 1 is not a proper proof, read glittergal's previous posts to silent water and marinus

glittergal96 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
you should attempt my problem!

Sure.

I think the only solutions are the trivial constant ones: 0, 1.

First we note that there are no real roots, as if x is a real root, then $(x+ 1)^2+1=x+(x+1/2)^2+7/4$ is a larger real root. (And a non constant polynomial only has finitely many roots.)

Now let a+ib be a complex root with |b| maximal (again possible because we are working with a finite non-empty set for non-constant polynomials).

Then if a >= 0, we have that (a+ib+1)^2+1 is also a root with imaginary part 2b(a+1), which has modulus > b, contradicting maximality.

Similarly, if a < 0, we have (a+ib-1)^2+1 is a root with imaginary part 2b(a-1), which again has modulus > b, contradiction.

So this reduces the problem to the constant case, which is just solving the equation c^2=c.

I.e. p(x)=0,1.

dan964 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
also, ur solution for 1 is not a proper proof, read glittergal's previous posts to silent water and marinus

no of course it is not a proper proof

glittergal96 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

dan964 said:
no of course it is not a proper proof

What was the purpose of the post then?

shervos · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

$\\ $ Consider a cubic polynomial $ P(x)=x^3+bx^2+cx+d $ .Show that $ |x_i| < 1 $ if and only if $ |bd-c| < 1-d^2 $ and $ |b+d| < |1+c| $where$ x_i$ is a root of the polynomial$$

dan964 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
what are you talking about. p(x) refers to a polynomial..........not p * (x-1).....

whoops

dan964 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

glittergal96 said:
What was the purpose of the post then?

thoughts
maybe another way of attacking the problem.

faisalabdul16 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

dan964 said:
thoughts

most of your answers are either fudged or BS lol...

dan964 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

faisalabdul16 said:
most of your answers are either fudged or BS lol...

that is true

for this thread (about half of the answer, so yes most is correct)
that said I don't post often on this thread for that reason.

HSC 2015 MX2 Marathon ADVANCED (archive) (5 Viewers)

Active Member

New Member

Active Member

Member

Active Member

Active Member

Member

Active Member

Member

what

Member

Member

Active Member

what

Active Member

Member

what

what

Wot

what

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